How to get the best price on ebay and get cheap gas. Optimal stopping strategies.

There are a lot of problems in the real world about perceiving the correct chance. Studies show that we humans are biased by fast decisions and that we are sometimes not exploring the problem domain long enough to take the best decision. This blog post will show you the optimal decision to pay the best price for an auction on ebay and to find the best gas station if you are driving a known route.

Problem description

Assume that you have to take a certain decision about a certain thing. In our example it will be about buying a certain pair of shoes. You do not know how expensive the pair is. The only thing that you know is that there are currently 10 running auctions on ebay starting at 1$. In average these shoes are sold for $300. You want to pay the cheapest price for these shoes but you also want to win the auction. So you are going to observe the prices for these shoes. The goal is to have an optimal strategy to buy them the cheapest.

Naive strategy

Just always bid $300 and hope that your get the shoes.

Optimal strategy

These kind of problems are called optimal stopping problems. Very famous examples are the secretary problem or the house selling problem. So the problem is that I have a sequence of events E₁ … E_n and my tasks is to select the optimal event E_m. In our case the events are the auction of the shoes and n = 10 because we have 10 auctions. The optimal auction is the auction with the minimal buying price for the shoes.

There are two big questions:

1. At which auctions should I take part?
2. How much should I bid?

The optimal strategy is to observe ⌈10/e ⌉ = 4 auctions and afterwards bid the minimum bid that won the auctions for these 4 auctions. If you don’t win with this bid buy them at the last auction for whatever price is required. This strategy can be derived from the odds algorithm.

To check how good this strategy is. I wrote a small R script which can be seen here:

# Optimal stopping simulation for ebay auctions

mean <- 300
sd <- 50

# we have 10 auctions
auctions <- 10
# how many simulations runs
simulationRuns <- 100

naiveBid <- 300
wins <- 0
paid <- c()
# runs the amount of simulations
for (i in rep(1, simulationRuns)) {
    # generate end prices of auctions (normally distributed)
    winningBids <- rnorm(auctions, mean, sd)
    myBid <- naiveBid
    # if there is an aucton with a winningBid that is smaller then myBid. I
    # won at least one auction.
    if (length(winningBids[myBid > winningBids]) > 1) {
        wins <- wins + 1
        paid <- append(paid, myBid)
        # buy the shoes in the last auction for the given price + 1 cent
    } else {
        wins <- wins + 1
        paid <- append(paid, winningBids[auctions] + 0.01)
    }
}
print(paste("Auctions won: ", wins, " mean paid:", mean(paid)))

## [1] "Auctions won:  100  mean paid: 302.02"

wins <- 0
paid <- c()
# runs the amount of simulations with optimized incentergy strategy (odd
# algorithm)
for (i in rep(1, simulationRuns)) {
    # generate end prices of auctions (normally distributed)
    winningBids <- rnorm(auctions, mean, sd)
    # the amount of auctions to observice
    observeAuctions <- ceiling(auctions/exp(1))
    # get the minimum bid in the first auctions/exp(1)
    minBid <- min(winningBids[1:observeAuctions])
    # If there is an auction that we won with our minimal bid
    if (minBid > min(winningBids[(observeAuctions + 1):auctions])) {
        wins <- wins + 1
        paid <- append(paid, minBid)
        # buy the shoes in the last auction for the given price + 1 cent
    } else {
        wins <- wins + 1
        paid <- append(paid, winningBids[auctions] + 0.01)
    }
}
print(paste("Auctions won:", wins, " mean paid:", mean(paid)))

## [1] "Auctions won: 100  mean paid: 280.343467275289"

The first algorithm corresponds to the naive strategy it just bids $300 all the time if this is not enough if just buys the shoes on the last of the 10 auctions.

The second strategy uses the odds algorithm.

Conclusion

As you can see the second strategy buys in average the pairs of shoes for $20 less. So this is nearly 7% saving by just choosing the right strategy.

If you are interested in using such strategies for your marketing feed and for real time bidding please get in touch with us.