Lowest Unique Bid Auctions

gavel

A lowest unique bid auction operates under the following three main rules:

  • Whoever bids the lowest unique positive amount wins.
  • If there is no unique bid then no one wins.
  • No participant can see bids placed by other participants.
  •  

    LowestUniqueBidAuction

    As it turns out there are real sites out there that offer this type of auction, see e.g bidbudgie. Their income is usually generated by attracting lots of bidders and placing a charge for making bids. This way they are able to give away iPhones, Xboxes, Laptops and other expensive items for a tiny nominal amount and also make a profit provided enough people participate. In an article I read somewhere a gold bullion worth more than 1,000£ was sold away for only 1p because no one else bid that amount thinking it was “too obvious” (perhaps one of the best marketing gimmicks the auction company could ever wish for).

    A natural question is: Are there any good strategies for participating in this auction?

    On the face of it, this doesn’t look vastly different from any old lottery – you are paying a fee to choose a number on which you may or may not win.
    One obvious difference is that this game has no proclaimed randomizing device such as would be found in a lottery to select between numbers, or as is the function of a deck in a card game or a die in a dice game. Instead chance is introduced exclusively via uncertainty about bids of other participants (i.e imperfect information). Therefore it seems more natural to take a game theoretic view rather than a purely probabilistic one since participants would want to take into account the strategy of others and adjust their choice accordingly. So instead of assuming a bidding distribution to model the situation we should be looking to understand what the distribution should be given some equilibrium state where everyone is reluctant to change their strategy because it would decrease their expected payoff.

    Let’s make a game theoretic definition that distinguishes between two different kinds of strategies.

    A pure strategy defines a specific move or action that a player will follow in every possible attainable situation in a game. Such moves may not be random, or drawn from a distribution, as in the case of mixed strategies (gametheory.net)

    A pure strategy in this game is very simple since there is only one attainable situation in the game, and that is the choice of a unique fixed number k.
    [Alternatively one can view this as a mixed strategy choosing k with probability 100%]
    To simplify the discussion a bit let us make the assumption that only one bid per person is allowed so that we may assume bids are placed independently of each other. We will discuss the general case briefly at the end of this post.

    Let us first consider whether there can be a “magic number” which you could always select beforehand to maximize your chances of winning the auction.
    In other words we are asking whether an optimal pure strategy exists.
    Suppose an optimal pure strategy did exist.
    Then every other player would want to adopt the same strategy since it is optimal.
    But that means they will all choose the same number and are therefore guaranteed to lose the auction.
    So any strategy choosing a different number would be better, and so the original strategy couldn’t have been optimal since we have found a better strategy.
    This is a contradiction.
    Hence there can be no optimal pure strategy.

    So having ruled out the existence of good pure strategies we turn our attention to mixed strategies. These strategies make choices from random distributions, i.e consist of some convex combination of pure strategies.

    We want a strategy that somehow describes how rational participants should play this auction. One such definition is that of a Nash Equilibrium.
    Informally a set of strategies is a Nash equilibrium if no player can do any better by unilaterally changing his or her strategy.

    Let’s digress for a bit to discuss this concept and its potential weaknesses.

    Game Theory Digression:

    You may have seen the movie A Beautiful Mind featuring actor Russel Crowe which is a portrayal of the life of Nobel Laureate John Nash who invented this equilibrium.
    In the movie it is (wrongly) illustrated by how a group of guys have nothing to gain by all hitting on the prettiest woman in the bar. If they all go for the prettiest woman then they would all supposedly block each other.
    Thus no one gets lucky with the pretty woman nor with any of the friends she came with since no one likes to be deemed second choice. But if they all go straight for her less attractive friends then they would all stand a better chance at achieving their objective (only a guy could have invented this analogy:-).
    However the Nash Equilibrium says the complete opposite in this case, that everyone should go for the pretty woman (assuming pure strategies). Whoever deviates from the strategy where no one goes for the pretty woman would actually improve, which cannot happen in an equilibrium state. The only strategy from which no one can improve is the strategy where everyone hits on the prettiest woman and presumably get rejected, despite mutual cooperation yielding a better outcome as is the situation described in the movie. Of course there are a whole series of unfounded social assumptions behind this analogy, like the fact that the women at the bar would automatically settle for the first (and only) guy that approaches them etc…


     
    The situation described in the movie may possibly be viewed as a slightly twisted, more generalized version of the two player prisoner dilemma which is a classical problem in Game Theory. This game was actually played by the two final contestants in a British game show called ‘Golden Balls’ (< Insert immature joke >).
    See below clips for interesting extracts from two different episodes.

    In the second clip the contestant is essentially betting that greed is a stronger incentive than retaliation.
    By announcing his intentions to steal and then offering to split the money afterwards, he is protecting himself from getting backstabbed i.e the burden of trust has been transferred to the other contestant. The second contestant has no reason to disbelieve the stealing intentions since if the first contestant did the opposite and decided not to steal, that would only be to the benefit of the second contestant. The second contestant is thus presented with a choice of not winning anything, or potentially winning half by trusting that the first contestant will split the money after the show.
    In effect the first contestant wants to switch from playing the prisoners dilemma to playing the ultimatum game where the other contestant has every incentive to accept any positive amount from a game theoretic standpoint, yet alone a 50/50 offer.
    Of course the second contestant doesn’t have to accept playing this game.
    If he wanted to get out of his currently dominated position, he would have had at least two rebuttals.
    One is to immediately turn the game into deadlock by offering the same ultimatum back.
    The second more bolder move would be to instead play the familiar chicken game by undercutting the previous offer by e.g saying, “I am now fully committed to steal as well and will give you only 40% of the money if you cooperate, are you prepared to continue playing or do you want to cut your losses?”. Note that this game could easily deteriorate as each of the contestants offer smaller and smaller cuts of the jackpot, until they are both left with nothing and forced to steal.
    Things would be much easier if the oral agreement of splitting the money after the show was legally binding, but I reckon it can’t be in the context of the game show.

     
     

    So now back to our auction.
    To simplify discussion again we shall only be looking for symmetric mixed strategy Nash equilibria i.e an equilibrium where everyone chooses the same strategy in such a way that anyone deviating from it would be worse off. We shall also require that only a countable number of bids are allowed, otherwise the auction gets ridiculous.
    Online the convention seems to be that the smallest increment allowed is 1 cent (or 1p if it is a UK auction).

    IndiscreteLowestUniqueBidAuction

    Finding the symmetric mixed strategy Nash equilibrium:

    Suppose S = (S_1,S_2,S_3,S_4,.....) is a mixed strategy where S_i represents the probability of bidding i cents.

    Then S_i \geq 0\;\; \forall i and \sum \limits_{i=1}^{\infty} S_i = 1.

    Suppose you plus n other people are participating in a lowest unique bid auction where everyone is using the same equilibrium strategy S.

    Denote by \mathbb{P}(win|j) your probability of winning by bidding j cents.
    Qualitatively \mathbb{P}(win|j) is given by the probability that there is no unique person bidding less than j cents and no other person bidding exactly j cents.

    By the partitioning rule \mathbb{P}(win|S) = \sum \limits_{j=1}^{\infty} S_j \; \mathbb{P}(win|j).

    If \exists j' s.t \mathbb{P}(win|S) < \mathbb{P}(win|j')\; then adjusting the distribution so that S_{j'} = 1 is an even better strategy than S but that is not allowed since S is assumed to be a Nash Equilibrium.

    Therefore \mathbb{P}(win|S) \geq \mathbb{P}(win|j)\; \forall j.

    Let j^* be such that \mathbb{P}(win|j^*) = \max \limits_{j}\; \mathbb{P}(win|j).

    Since 0 \leq S_j \leq 1\; \forall j it follows that \mathbb{P}(win|S) \leq \mathbb{P}(win|j^*).
    If \exists j' s.t S_{j'} > 0 and \mathbb{P}(win|j') < \mathbb{P}(win|j^{*}) then adjusting the distribution by moving the positive weight over from S_{j'} to S_{j^{*}} would yield yet another improvement upon S which cannot happen by Nash equilibrium assumption.

    Therefore we must have \mathbb{P}(win|j) = \mathbb{P}(win|j^{*}) \; \forall j.

    We have left to find an explicit expression for \mathbb{P}(win|j).
    As we said earlier \mathbb{P}(win|j) is given by the probability that there is no unique person bidding less than j cents and no other person bidding exactly j cents.

    There are two parts to work out.
    One is the probability that n-k people will choose a number greater than j which is easy to find, it is just equal to (1- \sum \limits_{i=1}^{j} S_i)^{n-k}.
    The second is that remaining k people will choose a number less than j such that there is no unique bidder.
    This is somewhat more awkward since we first need to look at all possible combinations of k people choosing a number less than j, a thing which is generated by \left ( \sum \limits_{i=1}^{j-1} S_i \right )^k, and then remove all combinations with unique bidders (i.e terms with S_i‘s of power 1), which we obtain via \sum \limits_{i=1}^{j-1} S_i\left ( \sum \limits_{ r = 1, r \neq i}^{j-1} S_r \right )^{k-1}.

    In all we obtain the following rather nasty looking expression
    \mathbb{P}(win|j) = (1- \sum \limits_{i=1}^{j} S_i)^{n} + \sum \limits_{k=1}^{n} \left( \begin{array}{c} n \\ k \end{array} \right) \left [ (1- \sum \limits_{i=1}^{j} S_i)^{n-k} \left ( \left ( \sum \limits_{i=1}^{j-1} S_i \right )^k - \sum \limits_{i=1}^{j-1} S_i\left ( \sum \limits_{ r = 1, r \neq i}^{j-1} S_r \right )^{k-1} \right ) \right ]

    So to find the equilibrium strategy S = (S_1,S_2,S_3,S_4,.....) we should solve the infinite non-linear equation system:
    \begin{cases} \sum \limits_{i=1}^{\infty} S_i = 1 \\ S_i \geq 0\;\; \forall i \\ \mathbb{P}(win|i) = \mathbb{P}(win|j)\;\; \forall i,j \end{cases}

    In the minimal non-trivial auction with yourself and two other participants (i.e n=2) we would get
    \mathbb{P}(win|j) = \left (1 - \sum \limits_{i=1}^j S_i \right )^2 + \sum \limits_{i=1}^{j-1} S_i^2.

    This means that either both other participants choose any number greater than j or both choose the same number less than j. We can use Wolfram Alpha to compute an approximate solution to a finite truncation of this system which gives: S_1 \approx 0.457784, S_2 \approx 0.251643, S_3 \approx 0.145286, S_4 < 0.145286.
    Unfortunately 4 variables is as far as you get before you run out of allotted (free) compute resources on the site. I should probably need to use Mathematica, Maple or some other math package to take a serious stab at computing a good distribution. Provided these numbers are ballpark accurate we could draw the conclusion that you should choose the least possible bid a little less than half the time and the next least bid approximately a quarter of the time in a rational auction with three people. Computing further points on the distribution I’m guessing there exists a tiny positive probability of even choosing one million in this equilibrium strategy which may seem rather surprising, both from a utility perspective and from an auction winning perspective. However on the former point we have not accounted for actually paying the bid in case we win, we are only concerned with winning the auction.

     

    Within most lowest unique bid auctions in the real world you are allowed to place multiple bids. Perhaps it might be interesting to discuss some potential heuristics for participating in such an auction.

    On the auction site I mentioned earlier (bidbudgie.co.uk) they auction MacBook Pro Laptops and charge 3£ per bid. They claim the laptop is worth 1,889£ (according to RRP). That means they need to attract at least 630 bids to make a profit assuming 1,889£ is what they paid for the laptop (which is probably not entirely true). Looking at it’s current status on the site at the time of writing, I see there are 234 bids already from 57 unique bidders after 37% of the auction time has elapsed.

    The site lets you know your rank in the auction if your bid is unique (meaning if you still have a chance at winning). The site also gives you the opportunity to buy information such as whether your bid is too high or too low in relation to the current winning bid, which costs 20p.
    This means you can locate the current winning bid using binary search for under 10x(3£ + 0.2£) assuming winning bid is under 10.24£.

    Looking at the tips & tricks page on the site I can see that they have a recommended strategy which is to place bids according to some arithmetic progression, say 0.13p, 0.23p, 0.33p, … , 1.13£. Then starting from your lowest unique bid you have an idea in what range the winner is currently in. You can then for example place multiple bids from 1p up to your lowest unique bid to eliminate all other players making you the current winner. Of course if you are the only person employing this strategy it may not be very expensive in comparison to the prize. However if everyone is doing this (which presumably is what the site wants) then playing this game can get very expensive and you might get carried away.

    Let’s look at another crude strategy.
    Suppose you are willing to invest 300£ in buying this laptop which would still save you 1,589£ if you win.
    Moreover let’s say you pick all bids from 1p to 1£.
    How likely is it that you will win this auction if there are 1000 bids placed on the laptop and everyone except you bids no more than once?

    In a paper entitled Equilibrium strategy and population-size effects in lowest unique bid auctions [Pigolotti et al (2012)] the effects of the number of participants is investigated on the symmetric Nash Equilibrium. The paper establishes that provided the number of bidders in the auction varies according to a Poisson distribution then the number of bids on each number is also Poisson in a symmetric Nash Equilibrium. When compared to real data it was found that in the region of 200 bidders this model approximates the empirical distribution fairly well and that the winning chances are evenly spread among all numbers. This means the auction behaves like a lottery for this region. For a larger number of participants they found the data begins to deviate from the model and starts following an exponential distribution because players fail to adapt to the optimal strategy and so the winning chances are highly dependent on the number of participants. On page 4 they display a very interesting log distribution contrasting the empirical winning number from theoretical.

    Reading the graph it appears the winning amount should be somewhere around 80p to 1£ with 1000 participants, both from a theoretical standpoint and typically according to the empirical data (if I am interpreting it correctly). So placing a series of bids in that region for the laptop may not be such a terrible investment in an auction with a moderate number of participants where you are the most aggressive bidder.

    Advertisements
    This entry was posted in Game Theory, Uncategorized and tagged , , , , , , , . Bookmark the permalink.

    2 Responses to Lowest Unique Bid Auctions

    1. Pingback: Active Math Game: Rock | DeniseGaskins.com

    2. Heiman says:

      Lowest and unique bid of 29,990

    Leave a Reply

    Fill in your details below or click an icon to log in:

    WordPress.com Logo

    You are commenting using your WordPress.com account. Log Out / Change )

    Twitter picture

    You are commenting using your Twitter account. Log Out / Change )

    Facebook photo

    You are commenting using your Facebook account. Log Out / Change )

    Google+ photo

    You are commenting using your Google+ account. Log Out / Change )

    Connecting to %s