Game Theory

Auctions as Games

An auction is a simple economic activity, that is frequently used to sell art, houses, or indeed any kind of things on the internet. The behavior of buyers and sellers at auctions can be analyzed in game theoretic terms.

Types of Auctions

To keep the discussion simple, we assume here that an auction involves one seller who wishes to sell one item, and many bidders. Each bidder has a (private) true value for the item, which is the amount they are prepared to pay for it.

One distinguishes four main types of auctions.

  1. Ascending Bid Auction (aka English Auction): In real time, the seller gradually raises the price, bidders drop out one by one, until the last remaining bidder wins the auction at the current price.

  2. Descending Bid Auction (aka Dutch Auction): In real time, the seller gradually lowers the price, until the first bidder accepts the price and wins the auction.

  3. First Price Sealed-Bid Auction. The bidders submit sealed bids simultaneously, the highest bidder wins and pays their bid as price.

  4. Second Price Sealed-Bid Auction. The bidders submit sealed bids simultaneously, the highest bidder wins and pays the second highest bid as price.

In contrast to the games we studied earlier, in an auction the sellers and buyers generally have no good estimate of the buyers’ strategies, i.e., their true values. However, some auction formats can be used to elicit bids that reveal the true values.

Let us suppose for the moment that all true values are known, and that the seller is trying to sell an item which they value at $x$. Any buyer with a true value of $y > x$ can generate a surplus of $y - x$. This surplus can be maximized by the seller if they announce the highest of the buyers’ true values as the price of the item. So in that case there is actually no need for an auction, announcing the price will suffice. The seller has the power to commit to a mechanism in the form of a fixed price.

If, on the other hand, the buyer with the highest true value had the power to commit to a mechanism, she could simply announce the second highest true value (or a little bit more) as the price she would be willing to pay. The seller would still be willing to sell, and now some of the surplus goes to the buyer (as she gets the item for less than she was prepared to spend).

For the following analysis, we assume that the true values are not known, but that they are private and independent.

Then, a descending bid auction is effectively a first price sealed-bid auction. The bidders learn nothing about each other’s true values in the process.

And an ascending bid auction is effectively a second price sealed-bid auction. For an optimal strategy, the bidders should use their true values as their bids.

Second Price Auction as a Game

When an auction is described as a game, the players are the bidders $N = \{1, 2, \dots, n\}$, each having a true value $v_i$, $i \in N$. Player $i$’s strategy is their actual bid $b_i$ (as a function of $v_i$).

Player $i$’s payoff in a second price sealed-bid auction is

  • $0$ if their bid $b_i$ is not winning the auction,
  • $v_i - b_k$ if their bid $b_i$ wins, and $b_k$ is the second highest bid.

(One can assume a fixed ordering among the bidders to break ties if necessary.)

Claim. Truthful bidding ($b_i = v_i$) is a dominant strategy.

In order to justify the claim, one needs to show that no deviation from the current bid $b_i = v_i$ would improve player $i$’s payoff, regardless of which strategy everyone else uses.

There are two cases to consider, either raising or lowering the bid. The key argument in both cases is that the bid only affects whether one wins or loses the auction, but not how much needs to be paid in the case of winning.

  • Suppose player $i$ raises their bid to $b_i’ > v_i$. This will only have an effect if it moves player $i$ from losing to winning, that is if $b_i’$ is larger than $b_k$, the previous highest bid. But then $b_k > b_i = v_i$ and $b_k$ is now the second highest bid. Player $i$’s payoff thus changes from $0$ (not winning) to $v_i - b_k < 0$, which is not an improvement.

  • Suppose player $i$ lowers their bid to $b_i’’ < v_i$. This will only have an effect it moves player $i$ from winning to losing, that is if $b_i’’$ is smaller than $b_k$, the previous second highest bid. But then $b_i = v_i > b_k$. Player $i$’s payoff changes from $v_i - b_k > 0$ to $0$, which is not an improvement either.

This shows that $b_i = v_i$ is indeed an optimal strategy, even if other players are not playing their optimal strategies, and even if they are not aware of their optimal strategy.

First Price Auction as a Game

First price sealed-bid auctions are more difficult to analyze since here a bid affects both the price and whether or not the auction is won.

Nonetheless, a first price sealed-bid auction can be described as a game as before, where the players are the bidders, each with a true value $v_i$, and a bidding strategy $b_i$ (as a function of $v_i$).

Now player $i$’s payoff in a first price sealed-bid auction is

  • $0$ if their bid $b_i$ is not winning the auction,
  • $v_i - b_i$ otherwise.

Obviously, truthful bidding here results in a $0$ payoff, regardless of whether the auction is won or lost. A bidding strategy that enables a positive payoff therefore needs to shade the bid downward, to a value $b_i$ such that $v_i - b_i > 0$. In choosing $b_i$, player $i$ is faced with a trade-off: choosing $b_i$ too close to $v_i$ leads to a smaller payoff, choosing $b_i$ too far away from $v_i$ decreases the chances of winning.

In the case of $2$ bidders, both using the same strategy $s$ to determine their bid $b_i = s(v_i)$, it can be shown that the strategy

leads to an equilibrium, i.e., $b_1 = \frac12 v_1$ and $b_2 = \frac 12 v_2$ are best responses to each other.

A similar, but more complex argument yields

as a strategy that produces equilibrium bids in the case of $n$ bidders.