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.

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:

- 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.
- 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.
- 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.
- 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.

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.

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:

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.

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 :

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:

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.

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

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.

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.

Acoustic FeaturesAcoustic ModelsArtificial IntelligenceASRaudio featuresAudio FingerprintsAudio signal processingAudio time and frequency indicatorsBigDataBigTableBlind Audio Source SeparationCassandraComputation VisionComputer VisionEdge DetectionGMMGrammarHadoopHMMImage ProcessingInformation RetrievalKeyword spottingLanguage ModellingLatent Dirichlet AllocationLatent Semantic AnalysisLexiconMAPMapReduceMFCCNoise ReductionPhone RecognitionPLPProbalistic Latent Semantic AnalysisShifted Delta CepstralSimilarity MeasuresSpeech EnhancementSpeech ProcessingSupervised automatic learningSVMSVM and GMM classificationsText MiningUBMvideo boundariesvideo featuresWiener Filter