Publications

Auction Theory

The auction process is a set of trading rules in economic theory, relating to a very old procedure. As long ago as A.D. 193, the Praetorian Guard sold the Roman Empire by auction. Auctions can take place with the physical presence of buyers and sellers, or electronically. Nowadays, auctions are used in various fields: selling of companies, houses, cars, radio spectrum licenses, assets, etc. More recently, this process has been used in the field of online advertising through Real Time Bidding (RTB) systems. Here, we present some of the main principles of auctions while focusing on the particular case of Independent Private Value (IPV) auctions, which will be explained.

Main types of auction

We assume that the seller auctions off only one object to a set of buyers. In this context, there are four main types of auction:

  1. English auction, also known as Open Ascending-bid auction: for this type of auction, the price of the object rises incrementally according to the price given by the buyers/bidders until only one of the bidders is interested in buying the object at his bid value. The winning buyer then obtains the object by paying the amount of his bid to the seller.
  2. Dutch auction, or Open Descending-bid auction, which is rarely used and works in the opposite way: the price of the object is set at a high level, and this price is incrementally decreased until one bidder accepts to buy the item at the price reached.
  3. First price sealed-bid auction: the bidders simultaneously submit their sealed bids, and the highest bidder wins the item by paying the value of his bid to the seller. This type of bidding is used in foreign exchange, for example.
  4. Second-price sealed-bid auctions or Vickrey auctions: all the bidders submit a sealed bid. The highest bidder wins the object and pays the value of the second-highest bid. This type of auction process was established by William Vickrey, winner of the Nobel Prize in Economics in 1996. The second-price sealed-bid auction is usually applied in Real Time Bidding (RTB) in online advertising. It is also used by eBay.

The last two types of auction are characterized as “sealed” because during the auction process none of the bidders knows the bid values of the others.

Otherwise, auctions can be classified into two main groups:

  • Private value (PV) model: the value given by each bidder to the item being auctioned off does not depend on the information held by the other bidders about the other bidders
  • Common value (CV) model: in this case, the bidders have information about the item being auctioned off, and this information is interdependent.

Private Real-Time Bidding

In the RTB process, the bidders do not have information about the bid values of the other bidders; hence we will focus on PV model cases. Moreover, the values are independent, hence this is the particular case of Independent Private Value (IPV). Bidders’ valuations are independent and identically distributed (i.d.d.). This property of an Auction is also qualified as a “symmetric model”, since the distributions of bidders’ values is identical. For the sake of simplicity, in the following steps, we will consider the case where there is only one winner and where there is no constraint on the bidders’ budgets.

First-Price sealed-bid (FPSB) Auctions

We introduce the notion of payoff. Denoting  the value of an auctioned-off object given by a bidder  and  his bid; when the bidder  is the winner, his payoff or profit is =.

More generally, the payoff is defined as follows:

First-Price sealed-bid Auction Strategy

Considering a FPSB where we denote by  the value of a given bidder and  his bid. The bidder’s expected profit or expected utility is defined as follows:

where  is the probability that bid wins.

How to find an optimal strategy in FPSB?

Obviously, the optimal strategy is the one that leads to maximum expected profit. Let us suppose that there are a total of  bidders. Moreover we assume that the bidder  whose bid is  and the other bidders  follow a strictly increasing and differentiable equilibrium strategy denoted . At equilibrium, the bids have the same distribution  which is differentiable increasing, and we speak of equilibrium strategy when all the bidders use the same strategy.

The equilibrium strategy  is such that . If this were not the case, the winner of such a bid would lose money (his profit would be negative: ).

Let us denote  the event “Bidder  wins”. The probability that the bidder  wins is:

We remember the notion of the cumulative distribution function (CDF): given a random variable  whose probability distribution is , the CDF is defined by .

Since the distribution of bids at equilibrium is , the probability 

The bids are i.i.d., so: 

We can observe that the events “” and the event “” are equivalent. Hence

Since B is strictly increasing and continuous, thus , where  denotes the inverse function of :

The expected utility of the bidder  when he wins is consequently:

The profit  is maximized by solving the optimization problem with respect to :

According to the first order condition, the maximum is reached when

For the sake of readability we will denote   which is the CDF of  . Since the bid function  is strictly increasing and continuous,  is also the CDF of  ; this is true because

The equation (1) becomes:

where  is the distribution of  because we remember that  is its CFD. At equilibrium , hence equation (1) becomes:

Equation (2) leads to:

We can observe that equation (3) can be rewritten as follows:

Finally, according to the mathematical expectation definition

Otherwise

Considering two functions   and , if we set  and , hence   and ,  and equation (4) can be rewritten as follows:

Finally

The variable  is called degree of “shading” which represents the difference between a bid and the value of an object.

In the particular case of uniform distribution of values on the interval :

Second-Price sealed-bid (SPSB) Auctions

We are still in the IPV context and there is no restriction on the bidders’ budget. We remember that in a second-price sealed-bid auction, the winner buys the object at the second-highest bid price. The bidders’ payoffs are defined by:

Some Definitions

In game theory [2], considering two strategies  and :

  •  strictly dominates  means that using the strategies  always provides a better outcome than using 
  •  weakly dominates  means that using the strategies  there is at least one set of opponent actions for which the payoff provided by the strategy  is greater than the strategy  one. For the other opponent actions the payoff for both strategies is equal.
  •  is a strictly dominant strategy if its payoff is higher than the payoff of all the other strategies.
  •  is a weakly dominant strategy if, for the same player, this strategy dominates some of the other strategies or is equivalent to the some of the other strategies.

Propriety: Dominance of Truthful bidding

In a second-price sealed-bid auction, the bidding strategy  is a weakly dominant strategy.

Demonstration

Consider a bidder  participating in a Second Price Bidding with  other bidders. Denote  and  respectively any bidder’s value and bid . We then introduce the variable .

First, we suppose that . We can consider three main cases:

1)     , in this case the bidder wins and his profit is , bidding  while yielding the same profit

2)     , in this case the bidder loses, while bidding  allows him to win

3)     , in this case the bidder loses, while bidding  yields the same result

Thus, bidding less than  does not increase the profit when a bidder wins, and so it is better to bid the value  than a value inferior to .

Now, let us assume that  . We can consider three main cases:

4)     , in this case the bidder wins and his profit is , while bidding  yields the same profit

5)     , in this case the bidder wins but his profit  is negative, while bidding  avoids money loss

6)     , in this case the bidder loses and if he bids  the result is identical.

Hence it is better to bid  than a value higher than .

To summarize, neither the fact of bidding higher than the value nor bidding lower than the value is better than bidding exactly the value.

To conclude, in an SPSB Auction, bidding  is a weakly dominant strategy.

The Expected Payment by a winning bidder [3]

Using the annotations of the previous sections, the probability that a bidder  with a bid  wins is .

We have already shown that  

And the expected payment is 

References

[1] http://www.gametheory.net/dictionary/WeaklyDominantStrategy.html

[2] Game Theory Evolving: A Problem-Centered Introduction to Modeling Strategic Interaction. Second Edition February 15, 2009.

[3] V. Krishna. Auction Theory. Academic Press, 2002.

You may also like
Keyword Spotting
Automatic Speech Recognition (ASR)