Abstract: In this mini-blog post, we look at the Vickrey auction and its properties, using mathematical analysis.
For the sake of connecting this to tabletop games, let us assume that, for one reason or another, you came into the extremely rare first edition printing of Cosmic Encounter, pictured to the right. And, being the good-natured person that you are, you want to give it to the person who wants it the most. Finally, you are incredibly busy and don’t have much time to spend dealing with this. How would you decide whom to give the game to?
The first thought you have is to simply ask people how much they would like the item and give it to whoever said they want it the most. However, after thinking about it, you realize that people would have no reason to act truthfully. Thus you decide that you should have people pay for it (see important note). But how much should the person pay? The obvious answer is to have the person pay the bid they submitted. Unfortunately, this has issues.
Let’s say for instance that one bidder, A, really wants the item and is willing to pay $300 for it. Let us also assume (for one reason or another) that A knows that the only other bidder B, bid 125$. What is the best bid for A? Well because A pays their bid, the best bid is the lowest bid that wins the item, in this case, $126. This is not, unfortunately, what their actual valuation of the item is, as they would pay $300 for it. Thus, it can be unclear which bidder actually wants the item the most, and thus our objective becomes much harder/impossible.
To solve this problem, we will use the Vickrey auction, a generalization of the VCG-mechanism. In this, auction bidders pay the value of the second-highest bid, or what they would have needed to match to win the item. This makes it so that players are incentivized to bid their actual valuations, as they can’t be punished for doing so, like in the scenario above. To see this we will consider all possible cases, where v is the “true valuation” and b is their stated bid.
- The Bidder overbids their valuation – Doing so can result in three different outcomes. If the bidder was already the highest bidder, that the outcome does not change, thus doing so is not beneficial. In the second case, the bidder was not winning but now is. In this case, they are worse off, since they must now pay more than the item is worth to them. This is because the second-highest bid must be greater than v, otherwise, they would have already won the item. In the third case, they are not winning the item, and up-bidding still does not win them the item. Thus, nothing changes.
- The Bidder underbids their valuation – Like the other bid strategy, this can result in three different outcomes. If the bidder was already the highest, and they are still the highest bidder, nothing is gained or lost. The same can be said if the bidder was not the highest, as they still win nothing and pay nothing. In the third case, however, they may end up losing the item, even though they would have paid more for it. In this case, v becomes the second-highest bid, losing the item, even though the bidder’s valuation for it was greater than b. Thus, their net utility goes down than if they bid truthfully.
With all the cases considered, we can now see that bidding truthfully is a “dominant strategy” or one in which you can fair no worse by being truthful. In the literature, this is often referred to as DSIC or dominant-strategy incentive-compatible. With this proof, we can now (mostly) be assured that the biggest Cosmic Encounter fan gets the item.
Important Note: One of the common assumptions made in economics (at least in my limited experience, I do not have a background in economics) is that utility or how much benefit a person would derive from a good or service is directly correlated with how much they are willing to pay for it. This assumption, (again in my limited experience) can lead to some nasty and inaccurate arguments, that I take issue with. Take for instance a homeless person during winter in New York. For said homeless person, the coat may provide life-saving warmth and thus has a very high utility. While for a New York socialite, the coat may simply be another coat that happens to catch their eye. Unfortunately, the homeless person will be unable to pay for the coat, thus if using the Vickrey auction to distribute the good, it will likely go to the socialite, despite not having a higher utility for the good. I have seen arguments in a similar vein for things like removing rent control and did not wish to discuss utility without bringing up this often faulty assumption.