Going once, going twice… game theory?

Chris Bishop

17 August 2017

• Click to share on X (Opens in new window)
• Click to share on Facebook (Opens in new window)
• Click to share on Reddit (Opens in new window)
• Click to share on LinkedIn (Opens in new window)
• Click to share on Threads (Opens in new window)
• Click to share on Mastodon (Opens in new window)

There’s been some buzz in the world of high art. Back in May, a Basquiat painting (untitled, of course) was sold at auction for $110 million. It set a record for the most expensive painting by an American artist, and also the most expensive work of art created after 1980. It didn’t quite reach the heights of the most expensive painting ever sold at auction. That honour belongs to Picasso’s Les Femmes d’Alger (Version O), which sold for a cool $180 million.

I don’t have millions to delve into the world of art dealership, but I was thinking: is there a way to apply mathematics to give me an edge over the billionaires that currently rule the historic auction houses in London and New York?

To start with, I need to know what sort of auction I’m dealing with. We can categorise each auction into one of four types.

• Ascending bid or English auctions. This is the type of auction that we’re accustomed to. The seller will gradually raise the price until only one bidder remains. The item is then sold to the final bidder.
• Descending bid or Dutch auctions. With roots in the tulip auctions of the 1600s in the Netherlands, this type of auction starts the bidding at an artificially high price, and then gradually lowers the price until the first bid is made. At this point, the bidder wins the auction (and the tulip!)
• First-price sealed auctions. Bidders submit sealed bids to the seller simultaneously and the highest bid wins the item.
• Second-price sealed auctions. Bidders submit sealed bids to the seller simultaneously, as above, and the highest bidder wins the item. However, in this format, the winner only has to pay as much as the second highest bid.
  

  Flickr user CEDIM NEWS, CC BY 2.0

Notice that we can further group these types of auctions together. In a Dutch auction, none of the buyers $i$ know any other of the other buyers’ valuations of the object. So, as the auction is running, all we learn is that none of the buyers value the object at the current price. Each buyer has a price $b_i$ where they are willing to bid, and so the highest such $b_i$ wins the auction. This is equivalent to a first-price sealed auction, so in this way we can group auction types 2 and 3 together.

Can we group English auctions with second-price sealed auctions? As the auctioneer gradually increases the price, bidders drop out, until the final bidder pays the price at where the second-to-last bidder drops out. In this way, they’re pretty good models of each other!

How much should I bid?

This is the key question we have to ask if we want to get the most bang for our buck in an auction. Each bidder $i$ has their own valuation for the object, which we will call $v_i$, and of course only the winning bidder pays the price of the bid, $p$. The value the winning bidder gets out of the object is called their utility, which is $v_i-p$. We also note that all non-winners have a utility of zero. If two or more bidders submit the same value for a winning bid, the winner is chosen at random.

Let’s start with a simpler version of an auction. In this case, we’re in the auction house, trying to get our hands on a Picasso, and the auction is a second-price sealed auction. What strategy should we employ to get the most utility out of this auction?

We have $\{ v_1, v_2, \dots, v_n\}$ for all other $n$ bidders, and we know our own valuation $V$. In this situation, the only thing that’s going to affect our bid is the largest one of those $v_i$ given. Let’s call this largest bid $m$. What should our bid, $b$, be?

If $m>V$, we can do four things.

• Bidding $b<V$ results in us losing the auction. Our utility is then zero.
• Bidding $V<b<m$ results in us losing again. We still have a utility of zero.
• Bidding $b=m$ results in us being tied for the top bid. If we lose, we have a utility of zero. If we win, $V – p < 0$, which results in a negative utility.
• Bidding $b>m$ results in us definitely winning, but also ensures a negative utility.

If $m=V$, we can do three things.

• Bidding $b<V$ results in us losing and a zero utility.
• Bidding $b=m$ results in us being tied for the top bid. If we lose, we have zero utility. If we win, $V – p = 0$ in this case, so we still have a zero utility.
• Bidding $b>m$ results in us definitely winning, but once again guarantees a negative utility.

If $m<V$, we have five options.

• Once again, if we bid $b<m$, we lose the auction.
• Bidding $b=m$ means we are tied for the top bid. If we lose, our utility is zero. If we win, our utility is $V – p > 0$, a positive utility.
• If we bid $m<b<V$, we definitely win the auction and have a positive utility as above.
• If we bid $b=V$, we once again definitely win the auction and have the same positive utility.
• Finally, if we bid $b>V$, we have the same result as above.

We can see from all of these case-by-case scenarios that there is no strategy that does better than bidding $b=V$, in other words, bidding your valuation of the object. There may be other courses of action that are just as good, but there is nothing better than bidding our valuation. This is called a weakly dominant strategy. Since this is the same for all bidders, we reach an equilibrium where everybody bids their valuation for the object, and we have the case where those who value the object highest will win the auction.

So I don’t think I’d stand much chance in an English auction or a second-price auction against the artisanal elite. Is there a way to gain an advantage in a first-price sealed auction?

Focusing on the payoff

Once again, we look at the utility we stand to gain. If I’m competing against one other person for the Basquiat, and we both have to submit sealed bids without knowing each other’s valuation of the painting, how do I maximise my potential utility?

Firstly, we aren’t going to bid more than what we think the painting is worth. This would result in $V – p < 0$, and we’d have a negative utility, or we’d lose, and have a utility of zero. Should we bid exactly our valuation, as we did in an English auction? In this case, if we win or lose, we’d end up with zero utility. So, we’re hoping to find a number below our valuation that’s going to give us a positive or zero utility, which will be our strategy.

The correct answer is that both parties should bid exactly half their valuations. If I value the object at $V$ and my opponent values it at $W$, our bids should be $V/2$ and $W/2$ respectively. Assuming our valuations are drawn over a continuous uniform distribution over $[0,1]$, let’s examine the proof.

We make a bid of $x$. We know our opponent is going to make a bid of $f(W) = W/2$. If we win (i.e. $x > f(W)$), our utility is $V-x$. The probability of us winning is $f^{-1}(x) = 2x$. If we lose, our utility is zero. The probability of this happening is $1 – f^{-1}(x)$. So, our expected utility is: 

$$U(x) =  f ^{-1}(x)(V-x)$$

We achieve maximum utility when $U’(x) = 0$.

Differentiating using both the product rule and the chain rule, we have

$$U’(x) =  -f^{-1}(x)+(V-x)\frac{1}{f ’(f^{-1}(x))}$$

When $U’(x) = 0$,

$$f^{-1}(x) = (V-x)\frac{1}{(f ’(f^{-1}(x))}$$

Setting $x = f(V)$, as we want $x$ to be related to our valuation, we have

$$V = (V-f(V))\frac{1}{f'(V)}$$

$$Vf'(V) = V – f(V)$$.

Solving this differential equation, we get $f(V) = V/2$.

Overall, looking at the utility gained seems to be the best way to approach an auction. Auctions are efficient because whoever values the object highest, normally ends up taking the painting home with them. There are some strategies you can employ to make sure you don’t overbid, but it’s difficult to win against someone who really wants to hang something on their bedroom wall. So, the next time you go and buy a masterpiece, remember to be certain on your valuation and bid with confidence, knowing mathematics has your back.

Chris Bishop

Chris Bishop is a second year Mathematics with Economics student at UCL with a keen interest in applying mathematics in optimisation problems in real-world scenarios.

All articles by Chris