Auctions

From Theory

Suppose two players are bidding for an object whose true value for player 1 is $75 and for player 2 is $50. What bidding strategy should the players use? Observe that (51,50) is a Nash equilibrium for this game. Another Nash equilibrium is (50,49). Second price auction is a mechanism which provides incentive for the players to bid their true value, simplifying the auction process. In a second price auction, the highest bidder gets the object but at the cost of the second highest bid. We use our example about 2 players bidding over an object described above and observe that bidding the true value is a dominant strategy. Let us look from player 1's perspective. If she bids above $75, say $80 then if any other player bids between the true value and her bid, she has to pay more for the object than its value to her. Thus it is clearly not in her interest to bid above the true value she has for the object. Similary if she bids below the value, say $65, then any bid by the other player between $65-$75 would give the object to the other player. It is clearly in her best interest to bid her true value for the object. In second price auctions, it is dominant strategy for all players to bid their true value.

[edit]

Mechanism Design

We consider a game with $N$ players, and each player has a set of types $T i$ . Let $T = T_1 \times \cdots \times T_N$ . Let ${\mathcal O}$ be the set of outcomes, and a utility function for each player $u_i : T_i \times {\mathcal O} \rightarrow {\mathbb R}$ .

Mechanism : A mechanism ${\mathcal M}$ is defined as a pair $(A, g)$ where $A = A_1 \times \cdots \times A_N$ is the set of action profiles and $g : A \rightarrow {\mathcal O}$ .

A strategy for player $i$ can be defined as a function from its types to actoins, i.e. $s_i : T_i \rightarrow A_i$ . We restrict ourselves to pure strategies only. We can extend the utility function to strategies as follows $u_i(g, t = (t_1, \ldots, t_N), s) = u_i(t_i, g_1(s_1(t_1),\ldots,s_N(t_N))$

We now look at mechanisms for auctions. What might be meaningful outcome for an auction? A plausible idea for defining a meaningful outcome could be that the person who is willing to bid the highest gets the object. We consider this in an abstract setting where for any type profile $t \in T$ we want to define what would be an ideal outcome. Suppose we have $f : T \rightarrow {\mathcal O}$ which we call the social choice function. We then consider the following definition:

We say that a mechanism ${\mathcal M}$ implements $f : T \rightarrow {\mathcal O}$ in dominant strategies, if there exists a dominant Nash equilibrium strategy profile $(s_1^*, \ldots, s_N^*)$ such that $g(s_1^*(t_1), \ldots, g(s_N^*(t_N)) = f(t_1, \ldots, t_N)$ .

A mechanism ${\mathcal M}$ is said to be a direct mechanism if for all $A i = T i$ , i.e. the actions are the types themselves. A direct truthful mechanism (a.k.a. incentive compatible mechanism) is one in which it is the dominant strategy to take $s i (t i) = t i$ for all $i$ .

Revelation Principle If ${\mathcal M}$ implements a social choice function $f$ in dominant strategies, then there is a direct trutful mechanism ${\mathcal M}^\prime$ that implements $f$ in dominant strategies.

Proof: Let ${\mathcal M} = (A, g)$ be the given mechanism and we want to construct a mechanism ${\mathcal M}^\prime = (T, g^\prime)$ . If $(a_1^\prime, \ldots, a_N^\prime) \in T$ is a type profile, we define $g^\prime(a_1^\prime, \ldots, a_N^\prime) = g(s_1^*(a_1), \ldots, s_N^*(a_N))$ . All we need to observe now is that if $s_i^* : T_i \rightarrow A_i$ is a dominant strategy for ${\mathcal M}$ then $s_i^*(t_i) = t_i$ is a dominant strategy in ${\mathcal M}^\prime$ . This concludes the proof.

We introduce payments to the game denoted by $π i$ for player $i$ . If the original utility function was $u_i : T_i \times {\mathcal O} \rightarrow \mathbb{R}$ , the true utility for player $i$ is now $u i (t, o) + π i$

We modify the definition of mechanism to deal with payments. We now define a mechanism as ${\mathcal M} = (A, g, \pi)$ where $g : A \rightarrow {\mathcal O} \times \mathbb{R}^N$ .

Vickrey-Clarke-Grove (VCG) Mechanism

This mechanism generalises second price auction. In this mechanism, the set of actions is the set of types so that we have ${\mathcal M} = (A=T, g, \pi)$ . Define $g(a_1,\ldots,a_N) = \left( \operatorname{arg max}_{o \in {\mathcal O}} \sum_i u_i(a_i,o),\pi_1,\ldots, \pi_N \right)$ Let $o^* = \operatorname{arg max}_{o \in {\mathcal O}} \sum_i u_i(a_i,o)$ and $o^*_{-i} = \operatorname{arg max}_{o \in {\mathcal O}} \sum_{j, j\neq i} u_j(a_j,o)$ . Finally define $\pi_i = \sum_{j \neq i}(u_j(a_j,o^*_{-i}) - u_j(a_j,o^*))$ .

Let us consider an example. Suppose there are 5 objects ${A, B, C, D, E}$ . Let us suppose that there are four players, P1 likes ${A, B, E}$ and is willing to pay $10 for that, P2 likes ${C, D}$ and is willing to pay $5 for that, P3 likes just ${D}$ and pay $4 for that and P4 likes ${A, C}$ and is willing to pay $10 for that. The optimal outcome $o *$ is when P1 and P2 get the bid. Calculating from the above definitions one can show that player 1 should pay $9, player 2 should pay $4.

Theorem VCG is a direct and truthful mechanism

Proof: The total utility for player $i$ is

$u_i( t_i, o^* ) + \sum_{ j \neq i } u_j( a_j, o^* ) - \sum_{ j \neq i } u_j( a_j, o_{ -i }^* )$ .

The last term in this expression does not depend on player $i$ 's action, so we can ignore it. Furthermore, $o *$ maximizes total utility given each player's action. However, $i$ 's actual utility depends on his type $t i$ , so he will maximize his utility by setting $a i = t i$ .

Retrieved from "http://wiki.cc.gatech.edu/theory/index.php/Auctions"

Auctions

From Theory

Mechanism Design

Views

Personal tools

Navigation

Search

Toolbox