Mechanism Design and Revenue Equivalence

Happy Pi Day! I have an economics midterm on Wednesday, so here is my attempt at studying.

1. Mechanisms

The idea is as follows.

We have ${N}$ people and a seller who wants to auction off a power drill.
The ${i}$ th person has a private value of at most ${\$1000}$ on the power drill. We denote it by ${x_i \in [0,1000]}$ .
However, everyone knows the ${x_i}$ are distributed according to some measure ${\mu_i}$ supported on ${[0, 1000]}$ . (let’s say a Radon measure, but I don’t especially care). Tacitly we assume ${\mu_i([0,1000]) = 1}$ .

Definition 1

Consider a game ${M}$ played as follows:

Each player ${i=1, \dots, N}$ makes a bid ${b_i}$ (which depends on how much they value the object)
Based on all the bids ${\vec b = \left( b_1, \dots, b_N \right)}$ , each player has a chance ${Q_i(\vec b) \in [0,1]}$ of actually obtaining the object. We call ${Q = \{Q_i\}_{i=1}^N}$ the allocation function and require ${\sum_i Q_i(\vec b) \le 1}$ .
Based on all the bids ${\vec b = \left( b_1, \dots, b_N \right)}$ , each player makes a payment ${P_i(\vec b) \in \mathbb R_{\ge 0}}$ . We call the ${P = \{P_i\}_{i=1}^n}$ the payment function. Note that one might have to pay even if they don’t get the drill!
The utility of the ${i}$ th player is
$\displaystyle U_i(\vec b) = Q_i(\vec b) \cdot x_i - P_i(\vec b)$

i.e. the expected chance they get the power drill minus the amount which they pay.

We call the pair ${(P,Q,\mu)}$ a mechanism.

For experts: we require that each ${P_i}$ and ${Q_i}$ is measurable. Right now this is not a very good definition, because there are no assumptions on what ${P}$ and ${Q}$ look like. Nonetheless, we’ll give some examples.

2. Examples of mechanisms

In the auction that you’d see in real life, we usually set

$\displaystyle Q = Q_{\text{highest}} \overset{\mathrm{def}}{=} \text{highest bidder wins}$

which is the simple rule that the highest bidder gets the power drill with probability ${1}$ ; if there is a tie, we pick one of the highest bidders at random.

In all the examples that follow, for simplicity let’s take the case ${N=2}$ , and call the two players Anna and Elsa. We assume that both Anna and Elsa the value they place on the drill is uniform between ${[0,1000]}$ . Finally, we give the auctioneer a name, say Hans.

2.1. First-price auction

The first-price auction is the one you’ve probably heard of: each player makes a bid and

${Q = Q_{\text{highest}}}$ , and
${P}$ is defined by requiring the winner to pay their bid.

How do Anna and Elsa behave in this auction? Clearly no one will bid more than they think the drill is worth, because then they stand to lose utility if they happen to win the auction. But the truth is they actually will bid less than they think the drill is worth.

For concreteness, suppose Anna values the drill at ${\$700}$ . It doesn’t make sense for Anna to bid more than ${\$700}$ obviously. But perhaps she should bid ${\$699}$ — save a dollar. After all, what’s the chance that Elsa would bid right between ${\$700}$ and ${\$699}$ ? For that matter, Anna knows that Elsa has a ${50\%}$ chance of valuing the drill at less than ${\$500}$ . So if Anna bids ${\$500}$ , she has at least a ${50\%}$ of saving at least ${\$200}$ ; it makes no sense for her to bid her true ${\$700}$ value.

It gets better. Anna knows that Elsa isn’t stupid, and isn’t going to bid ${\$500}$ even if her true value is ${\$500}$ . That is, Elsa is going to try and sell Hans short as well. Given this Anna can play the game of cheating Hans more aggressively, and so an ad infinitum.

Of course there’s a way to capture this idea of “I know that you know that I know that you know. . .”: we just compute the Nash equilibrium.

Proposition 2 (Nash eqilibirum of the first-price auction for ${N=2}$ )

Consider a first-price auction where Anna and Elsa have values uniformly distributed in ${[0, 1000]}$ . Suppose both Anna and Elsa bid ${x/2}$ if they have value ${x}$ . Then this is a Nash equilibrium.

Proof: Suppose Anna values the drill at ${a}$ and wants to make a bid ${x}$ . Elsa values the drill at ${e}$ , and follows the equilibrium by bidding ${e/2}$ . For a bid of ${x}$ , Anna gets utility

$\displaystyle \begin{cases} a-x & x>e/2 \\ 0 & \text{otherwise} \end{cases}.$

The probability of winning with ${x}$ is thus ${\min(1, 2x/1000)}$ (this the probability that ${e < 2x}$ ) so the expected utility is

$\displaystyle (a-x)\min\left( 1, \frac{2x}{1000} \right) \le \frac{2}{1000} x(a-x).$

Hence we see ${x = a/2}$ maximizes Anna’s expected utility. $\Box$

The first-price auction is interesting because both players “lie” when bidding in the Nash equilibrium. For this reason we say that the first-price auction is not incentive compatible.

Just for interest, let’s compute how much money Hans is going to make off the drill in this equilibrium. The amount paid to him is equal to

$\displaystyle \mathbf E_{a,e} \left( \max(a/2, e/2) \right) = \frac{1000}{3}.$

To see this we had to use the fact that if two numbers in ${[0,1]}$ are chosen at random, the expected value of the larger is ${\frac23}$ . Multiplying by ${1000/2 = 500}$ gives the answer: Hans expects to make ${\$333}$ .

2.2. Second-price auction

The second-price auction is the other one you’ve probably heard of: each player makes a bid and

${Q = Q_{\text{highest}}}$ , and
${P}$ is defined by requiring the winner to pay the smallest amount needed to win, i.e. the second highest bid.

The fundamental difference is that in a second-price auction, a player “doesn’t need to be shy”: if they place a large bid, they don’t have to worry about possibly paying it.

Another way to think about is as a first-price auction with the property that the winning player can retroactively change their bid, provided they still win the auction. So unlike before there is no advantage to being honest.

Indeed, the second-price auction is incentive compatible in a very strong sense: bidding your true value is the best thing to do regardless of whether your opponents are playing optimally.

Proposition 3 (Second-price auctions are incentive compatible)

In a second-price auction, bidding truthfully is a weakly dominant strategy.

Proof: Easy. Check it. $\Box$

Just for interest, let’s compute how much money Hans is going to make off the drill in this equilibrium. This time he amount paid to him is equal to

$\displaystyle \mathbf E_{a,e} \left( \min(a, e) \right) = \frac{1000}{3}.$

Here we had to use the fact that if two numbers in ${[0,1]}$ are chosen at random, the expected value of the smaller is ${\frac13}$ . This might come as a surprise: the expected revenue is ${\$333}$ in this auction too.

2.3. All-pay auction

The all-pay auction is like lobbying. Each player makes a bid, and

${Q = Q_{\text{highest}}}$ , and
${P}$ is defined by requiring everyone to pay their bid, regardless of whether they win the power drill or not.

This is clearly not incentive compatible. In fact, the Nash equilibrium is as follows:

Proposition 4 (Nash equilibirum of the all-pay auction)

Consider a first-price auction where Anna and Elsa have values uniformly distributed in ${[0, 1000]}$ . Suppose both Anna and Elsa bid ${\frac{1}{2} \cdot 1000(x/1000)^2}$ if they have value ${x}$ . Then this is a Nash equilibrium.

Proof: Omitted, but a fun and not-hard exercise if you like integrals. It will follow from a later result. $\Box$

Just for interest, let’s compute how much money Hans is going to make off the drill in this equilibrium. This time he amount paid to him is equal to

$\displaystyle \mathbf E_{a,e} \left( \frac{a^2}{2000} + \frac{b^2}{2000} \right) = \int_{0}^{1000} \frac{x^2}{1000} \; dx = \frac{1000}{3}.$

Surprise — same value again! This is a very special case of the Revenue Equivalence Theorem later.

2.4. Extortion

We’ve seen three examples that all magically gave ${\$333}$ as the expected gain. So here’s a silly counterexample to show that not every auction is going to give ${\$333}$ as an expected gain. It blatantly abuses the fact that we’ve placed almost no assumptions on ${P}$ and ${Q}$ :

${Q = Q_{\text{highest}}}$ , or any other ${Q}$ for that matter, and
${P}$ is defined by requiring both Anna and Elsa to give ${\$1000000}$ to Hans.

This isn’t very much an auction at all: more like Hans just extracting money from Anna and Elsa. Hans is very happy with this arrangement, Anna and Elsa not so much. So we want an assumption on our auctions to prevent this silly example:

Definition 5

A mechanism ${(M, \sigma)}$ is voluntary (or individually rational) if ${u_i(x_i) \ge 0}$ for every ${x_i \in [0,1000]}$ .

2.5. Second-price auction with reserve

Here is a less stupid example of how Hans can make more money. The second-price auction with reserve is the same as the second-price auction, except Hans himself also places a bid of ${R = 500}$ . Thus if no one bids more than ${R}$ , the item is not sold.

For the same reason as in the usual second-price auction, bidding truthfully is optimal for each players. The cases are:

If both Anna and Elsa bid less than ${\$500}$ , no one gains anything.
If both Anna and Elsa bids more than ${\$500}$ , the higher bidder wins and pays the lower bid.
If exactly one player bids more than ${\$500}$ , that player wins and pays the bid for ${\$500}$ .

So Hans suffers some loss in the first case, but earns some extra money in the last case (when compared to the traditional second-price auction.) It turns out that if you do the computation, then Hans gets an expected profit of

$\displaystyle \frac{1250}{3} \approx \$417$

meaning he earns another ${\$80}$ or so by setting a reserve price.

3. Direct mechanisms

As it stands, ${b_i}$ might depend in complicated ways on the actual values ${x_i}$ : for example in the first-price auction. We can capture this formalism as follows.

Definition 6

A direct mechanism is a pair ${M = (M, \sigma)}$ where

${(P,Q, \mu)}$ is a mechanism,
${\sigma = \{\sigma_i\}_{i=1}^N}$ is a Nash equilibrium of bidding strategies for the bidders. So in this equilibrium the ${i}$ th player will bid ${\sigma_i(x_i)}$ .

If ${\sigma = \mathrm{id}}$ , meaning ${\sigma_i(x) \equiv x}$ for every ${i}$ , then we say ${M}$ is incentive compatible.

So in other words, I’m equipping the mechanism ${M}$ with a particular Nash equilibrium ${\sigma}$ . This is not standard, but I think it is harder to state the theorems in a non-confusing form otherwise.

Definition 7

Let ${M = (M, \sigma)}$ be a direct mechanism. Then we define ${p_i(x)}$ , ${q_i(x)}$ , ${u_i(x)}$ by

$\displaystyle u_i(x) = \mathbb E\left[ U_i(\vec b) \mid x_i = x \text{ and everyone follows } \sigma \right]$

For example, ${u_1(x)}$ is the expected utility of the 1st player conditioned on them having value ${x}$ for the power drill:

$\displaystyle u_1(x) = \int_{x_2=0}^{1000} \dots \int_{x_N=0}^{1000} U_1(\sigma_1(x), \sigma_2(x_2), \dots, \sigma_N(x_N)) \; d\mu_2 \dots d\mu_N.$

Similarly, let

$\displaystyle \begin{aligned} p_i(x) &= \mathbb E\left[ P_i(\vec b) \mid x_i = x \text{ and everyone follows }\sigma \right] \\ q_i(x) &= \mathbb E\left[ Q_i(\vec b) \mid x_i = x \text{ and everyone follows }\sigma \right]. \end{aligned}$

Note that ${p_i}$ , ${q_i}$ , ${u_i}$ depend not only on the mechanism ${M}$ itself but also on the attached equilibrium ${\sigma}$ .

It’s important to realize the functions ${p_i}$ , ${q_i}$ , ${u_i}$ carry much more information than just ${P}$ , ${Q}$ , ${U}$ . All three functions depend on the equilibrium strategy ${\sigma}$ , which in turn depend on both ${P}$ and ${Q}$ . Moreover, all three functions also depend on ${\mu}$ . Hence for example ${q}$ actually depends indirectly on ${P}$ as well, because the choice of ${P}$ affects the resulting equilibrium ${\sigma}$ .

Example 8 (Example of ${\sigma}$ , ${q_i}$ , ${p_i}$ )

Let’s take the first-price auction with two players Anna and Elsa. If we call it ${M = (M, \sigma)}$ then as we described before we have:

${N = 2}$ ,
${\mu_1}$ and ${\mu_2}$ are uniform distributions over ${[0,1000]}$ ,
${P_i}$ is defined by having player ${i}$ pay their bid upon winning.
${Q = Q_{\text{highest}}}$

Moreover, the Nash equilibrium ${\sigma = (\sigma_1, \sigma_2)}$ is given by

$\displaystyle \sigma_i(x) = x/2$

for all ${x}$ , as we saw earlier. Consequently, we have

${q_i(x) = x/1000}$ since the probability of winning (and hence winning the bid) is proportional to the value placed on the item (since ${\mu}$ is a uniform distribution).
${p_i(x) = x/2 \cdot x/1000}$ as the expected payment: there’s a ${x/1000}$ chance of winning, and a payment of ${x/2}$ if you do.

4. Equivalence of utility and payment

In what follows let ${i}$ be any index.

We now prove that

Lemma 9 (Envelope theorem)

Assume ${M = (M, \sigma)}$ is a direct mechanism. Then ${u}$ is convex, and

$\displaystyle u_i'(x) = q_i(x)$

except for at most countably many points at which ${u}$ is not differentiable.

Proof: Since ${\sigma}$ is an equilibrium, we have

$\displaystyle x \cdot q_i(x) - p_i(x) = u_i(x) \ge x \cdot q_i(b) - p_i(b) \qquad \forall b \in I.$

i.e. there is no benefit in lying and bidding ${b}$ rather than ${x}$ .

First, let’s show that if ${x}$ is differentiable, then ${u_i'(x) = q_i(x)}$ . We have that

$\displaystyle \lim_{h \rightarrow 0} \frac{u_i(x+h)-u_i(x)}{h} \ge \lim_{h \rightarrow 0} \frac{\left[ (x+h)q_i(x)-p_i(x) \right] - \left[ x \cdot q_i(x)-p_i(x) \right]}{h} = q(x).$

Similarly

$\displaystyle \lim_{h \rightarrow 0} \frac{u_i(x)-u_i(x-h)}{h} \le \lim_{h \rightarrow 0} \frac{\left[ x \cdot q_i(x)-p_i(x) \right] - \left[ (x-h)q_i(x)-p_i(x) \right]}{h} = q_i(x).$

This implies the limit, if it exists, must be ${q_i(x)}$ . We’ll omit the proof that ${u}$ is differentiable almost everywhere, remarking that it follows from ${q_i(x)}$ being nondecreasing in ${x}$ (proved later). $\Box$

Theorem 10 (Utility equivalence)

Let ${(M, \sigma)}$ be a direct mechanism. For any ${x}$ ,

$\displaystyle u_i(x) = u_i(0) + \int_0^x q_i(t) \; dt.$

Proof: Fundamental theorem of calculus. $\Box$

Theorem 11 (Payment equivalence)

Let ${(M, \sigma)}$ be a direct mechanism. For any ${x}$ ,

$\displaystyle p_i(x) = p_i(0) + x \cdot q_i(x) - \int_0^x q_i(t) \; dt.$

Thus ${p}$ is determined by ${q}$ up to a constant shift.

Proof: Use ${u_i(x) = x \cdot q_i(x) - p_i(x)}$ and ${u_i(0) = - p_i(0)}$ . $\Box$

This means that both functions ${p}$ and ${u}$ are completely determined, up to a constant shift, by the expected allocation ${q}$ in the equilibrium ${\sigma}$ .

5. Revenue equivalence

A corollary:

Corollary 12 (Revenue equivalence)

Let ${M = (M, \sigma)}$ be a mechanism. Then the expected revenue of the auctioneer, namely,

$\displaystyle \mathbf E_{\vec x} \sum_{i=1}^N p_i(x_i)$

depends only on ${q_i}$ and ${p_i(0)}$ .

Very often, textbooks will add the additional requirement that ${u_i(0) = 0}$ or ${p_i(0) = 0}$ , in which case the statements become slightly simpler, as the constant shifts go away.

Here are the two important corollaries, which as far as I can tell are never both stated.

Corollary 13 (Revenue equivalence for incentive compatible mechanisms)

If ${M = (M, \mathrm{id})}$ is incentive compatible, then ${u_i(x)}$ and ${p_i(x)}$ (and hence the seller’s revenue) depends only on the allocation function ${Q}$ and distributions ${\mu}$ , up to a constant shift.

Proof: In an incentive compatible situation where ${\sigma_i(x) = x}$ we have

$\displaystyle q_1(x) = \int_{x_2=0}^{1000} \dots \int_{x_N=0}^{1000} Q_1(x, x_2, \dots, x_N) \; d\mu_2 d\mu_3 \dots d\mu_N$

so ${q_1}$ depends only on ${Q}$ and ${\mu}$ up to a constant shift. Ditto for any other ${q_i}$ . $\Box$

Corollary 14 (Revenue equivalence for ${Q_{\text{highest}}}$ auctions)

Suppose ${M = (M, \sigma)}$ is a mechanism in which

The allocation function is ${Q = Q_{\text{highest}}}$ ,
The ${\sigma_i(x)}$ is strictly increasing in ${x}$ for all ${i}$ (players with higher values bid more).

Then ${u(x)}$ and ${p(x)}$ are determined up to constant shifts by ${\mu}$ .

Proof: By the assumption on ${\sigma}$ we have

$\displaystyle Q_{\text{highest}}( \sigma_1(x_1), \dots, \sigma_N(x_N) ) = Q_{\text{highest}}\left( x_1, \dots, x_N \right)$

so it follows for example that

$\displaystyle \begin{aligned} q_1(x) &= \int_{x_2=0}^{1000} \dots \int_{x_N=0}^{1000} Q_1(\sigma_1(x), \sigma_2(x_2), \dots, \sigma_N(x_N)) \; d\mu_2 \dots d\mu_N \\ &= \int_{x_2=0}^{1000} \dots \int_{x_N=0}^{1000} Q_1(x, x_2, \dots, x_N) \; d\mu_2 \dots d\mu_N. \end{aligned}$

Once again ${q_i}$ now depends only on ${\mu}$ . $\Box$

As an application, we can actually use the revenue equivalence theorem to compute the equilibrium strategies of the first-price, second-price, and all-pay auctions with ${n \ge 2}$ players.

Corollary 15 (Nash equilibria of common ${Q_{\text{highest}}}$ auctions)

Suppose a player has value ${x \in [0,1000]}$ as in our setup, and that the prior ${\mu}$ is distributed uniformly. Each of the following is a Nash equilibrium:

In a first-price auction, bid ${\frac{n}{n+1} x}$ .
In a second-price auction, bid ${x}$ (i.e. bid truthfully).
In an all-pay auction, bid ${1000 \cdot \frac{n-1}{n} (x/1000)^n}$ .

Proof: First, as we saw already the second-price auction has an equilibrium where everyone bids truthfully. In this case, the probability of winning is ${(x/1000)^{n-1}}$ and the expected payment when winning is ${\frac{n-1}{n} x}$ (this is the expected value of the largest of ${n-1}$ numbers in ${[0,x]}$ .) Now by revenue equivalence, we have

$\displaystyle p_i^{\mathrm{all}}(x) = p_i^{\mathrm{I}}(x) = p_i^{\mathrm{II}}(x) = 1000 \cdot \frac{n-1}{n} \left( x/1000 \right)^n.$

Now we examine the all-pay and first-price auction.

We have ${p_i^{\mathrm{all}}(x) = 1000 \cdot \frac{n-1}{n} \left( x/1000 \right)^n}$ , i.e. in the equilibrium strategy for the all-pay auction, a player with type ${x}$ pays on average ${1000 \cdot \frac{n-1}{n} \left( x/1000 \right)^n}$ . But the payment in an all-pay auction is always the bid! Hence conclusion.
We have ${p_i^{\mathrm{I}}(x) = p_i^{\mathrm{II}}(x)}$ , and since in both cases the chance of paying at all is ${(x/1000)^{n-1}}$ , the payment if a player does win is ${\frac{n-1}{n} x}$ ; hence the equilibrium strategy is to bid ${\frac{n-1}{n}x}$ .

$\Box$

6. Design feasibility

By now we have seen that all our mechanisms really depend mostly on the functions ${q_i}$ , (from which we can then compute ${p_i}$ and ${u_i}$ ) while we have almost completely ignored the parameters ${P_i}$ , ${Q_i}$ , ${\sigma}$ which give rise to the mechanism ${(M, \sigma)}$ in the first place.

We would like to continue doing this, and therefore, we want a way to reverse the work earlier: given the functions ${q_i}$ construct a mechanism ${(M, \sigma)}$ with those particular expected allocations. The construction need not even be explicit; we will be content just knowing such a mechanisms exists.

Thus, the critical question is: which functions ${q_i}$ can actually arise? The answer is that the only real constraint is that ${q_i}$ are nondecreasing.

Theorem 16 (Feasability rule)

Consider ${N}$ players with a fixed a distribution ${\{\mu_i\}_{i=1}^N}$ of private values. Consider any measurable functions ${q_1, \dots, q_N : [0,1000] \rightarrow \mathbb R_{\ge 0}}$ .

Then there exists a direct mechanism ${(M, \sigma)}$ with ${q_i}$ as the expected allocations if and only if

each function ${q_i}$ is nondecreasing.
${q_1(x_1) + \dots + q_N(x_N) \le 1}$ with probability ${1}$ .

Proof: First, we show that any ${q_i}$ arising from a direct mechanism are nondecreasing. Indeed, if ${x > y}$ then we have the inequalities

$\displaystyle \begin{aligned} x \cdot q_i(x) - p_i(x) &\ge x \cdot q_i(y) - p_i(y) \\ y \cdot q_i(y) - p_i(y) &\ge y \cdot q_i(x) - p_i(x). \end{aligned}$

If we add these inequalities we recover ${(x-y)q_i(x) \ge (x-y)q_i(y)}$ , which shows that ${q_i}$ is nondecreasing. The second condition just reflects that ${\sum Q_i(\vec b) \le 1}$ .

Conversely, suppose ${q_i}$ are given nondecreasing function. We will construct an incentive compatible mechanism inducing them. First, define ${p_i(x) = x \cdot q_i(x) - \int_0^x q_i(t) \; dt}$ as predicted by Revenue Equivalence. First, define ${M = (P,Q, \mu)}$ by

${P_i(x_1, \dots, x_N) = p_i(x_i)}$ , and
${Q_i(x_1, \dots, x_N) = q_i(x_i)}$ . (Note ${\sum_i Q_i(x_i) \le 1}$ .)

Then trivially ${p_i^M = p_i}$ and ${q_i^M = q_i}$ .

However, we haven’t specified a ${\sigma}$ yet! This is the hard part, but the crucial claim is that we can pick ${\sigma = \mathrm{id}}$ : that is, ${(M, \mathrm{id})}$ is an incentive compatible direct mechanism.

Thus we need to check that for all ${x}$ and ${y}$ that

$\displaystyle u_i(x) \ge x \cdot q_i(y) - p_i(y)$

We just do ${x > y}$ since the other case is analogous; then the inequality we want to prove rearranges as

$\displaystyle \begin{aligned} \iff u_i(x) - u_i(y) &\ge (x-y) \cdot q_i(y) \\ \iff \int_y^x q(t) \; dt &\ge \int_y^x q(y) \; dt \end{aligned}$

Since ${q}$ is increasing, this is immediate. $\Box$

In particular, we can now state:

Corollary 17 (Individually Rational)

A direct mechanism ${(M, \sigma)}$ is voluntary if and only if

$\displaystyle u_i(0) \ge 0 \iff p_i(0) \le 0$

for every ${i}$ .

Proof: Since ${u_i' = q_i \ge 0}$ , the function ${u_i}$ is nonnegative everywhere if and only if ${u_i(0) \ge 0}$ . $\Box$

7. Optimal auction

Since we’re talking about optimal auctions, we now restrict our attention to auctions in which ${p_i(0) = 0}$ for every ${i}$ (hence the auction is voluntary).

Now, we want to find the amount of money we expect to extract for player ${i}$ . Let’s compute the expected revenue given a function ${q}$ and distribution ${\mu}$ . Of course, we know that

$\displaystyle \mathbf E_{x_i}\left[ p_i(x_i) \right] = \int_{t=0}^{1000} p_i(t) \; d\mu_i$

but we also know by revenue equivalence that we want to instead use the function ${q_i}$ , rather than the function ${p_i}$ . So let’s instead use our theorem for the integral to compute it:

$\displaystyle \mathbf E_{x_i}\left[ p_i(x_i) \right] = p_i(0) + \mathbf E_{x_i}\left[ x_i \cdot q_i(x_i) \right] - \mathbf E_{x_i}\left[ \int_0^{x_i} q(t) \; dt \right]$

Applying the definition of expected value and switching the order of summation,

$\displaystyle \begin{aligned} \mathbf E_{x_i}\left[ p_i(x_i) \right] &= p_i(0) + \int_{t=0}^{1000} t \cdot q_i(t) \; d\mu_i - \int_{x=0}^{1000} \int_0^{x} q(t) \; dt d\mu_i \\ &= \int_{t=0}^{1000} t \cdot q_i(t) \; d\mu_i - \int_{t=0}^{1000} q(t) \int_{x=t}^{1000} \int_0^{x} d\mu_i dt \\ &= \int_{t=0}^{1000} t \cdot q_i(t) \; d\mu_i - \int_{t=0}^{1000} q_i(t) \cdot \mu_i([t, 1000]) dt \\ &= \int_{t=0}^{1000} t \cdot q_i(t) \; d\mu_i - \int_{t=0}^{1000} q_i(t) \cdot \frac{1-\mu_i([0, t])} {\frac{d\mu_i}{dt}(t)} d\mu_i \\ &= \int_{t=0}^{1000} q_i(t) \left( t - \frac{1-\mu_i([0,t])} {\frac{d\mu_i}{dt}(t)} \right) d\mu_i \end{aligned}$

Thus, we define for the player ${i}$ their virtual valuation to be the thing that we just obtained in this computation:

$\displaystyle \psi_i(t) = t - \frac{1-\mu_i([0,t])}{\frac{d\mu_i}{dt}(t)}.$

Thus

$\displaystyle \mathbf E_{x_i}\left[ p_i(x_i) \right] = \int_{t=0}^{1000} q_i(t) \cdot \psi_i(t) \; dt. \ \ \ \ \ (1)$

The virtual valuation ${\psi_i(t)}$ can be thought of as the expected value of the amount of money we extract if we give the object to player ${i}$ when she has type ${t}$ . Note it has the very important property of not depending on ${q_i}$ .

Now, let’s observe that

$\displaystyle \begin{aligned} \sum_{i=1}^N \mathbf E_{x_i} \left[ p_i(x_i) \right] &= \sum_{i=1}^N \int_{t=0}^{1000} q_i(t) \psi_i(t) \; d\mu_i \\ &= \sum_{i=1}^N \int_{x_1=0}^{1000} \dots \int_{x_N=0}^{1000} Q_i(\vec x) \psi(x_i) \; d\mu_1 d\mu_2 \dots d\mu_N \\ &= \int_{x_1=0}^{1000} \dots \int_{x_N=0}^{1000} \sum_{i=1}^N \left( Q_i(\vec x) \psi(x_i) \right) \; d\mu_1 d\mu_2 \dots d\mu_N. \end{aligned}$

Now, our goal is to select the function ${Q}$ to maximize this. Consider a particular point ${\vec x = (x_1, \dots, x_N)}$ . Then we’re trying to pick ${Q_1(\vec x)}$ , ${Q_2(\vec x)}$ , \dots, ${Q_n(\vec x)}$ to maximize the value of

$\displaystyle Q_1(\vec x) \psi_1(x_1) + Q_2(\vec x) \psi_2(x_2) + \dots + Q_n(\vec x) \psi_n(x_n)$

subject to ${\sum Q_i(\vec x) \le 1}$ . The ${\psi_i}$ ‘s here depend only on the distribution ${\mu}$ . This is thus a convex optimization problem, so the solution is obvious: put all the weight on the biggest positive ${\psi_i(x_i)}$ , breaking ties arbitrarily. In other words, if ${k = \text{argmax }_i \psi_i(x_i)}$ and ${\psi_k(x_k) > 0}$ , then set ${Q_k(\vec x) = 1}$ and all the other coefficients to be zero. (Ties broken arbitrarily as usual.) To be explicit, we set

$\displaystyle Q_k(\vec x) = \begin{cases} 1 & \psi_k(x_k) \ge 0 \text{ is maximal (ties broken arbitrarily)} \\ 0 & \text{else}. \end{cases}$

So we should think of this as a second-price auction with discriminatory reserve prices. Moreover, the “second-price” payment is done based on ${\psi_i}$ , so rather than “pay second highest bid” we instead have “pay smallest amount needed to win”, i.e. the smallest ${y}$ such that ${\psi_k(y) \ge \psi_j(x_j)}$ for all ${j \neq k}$ .

Unfortunately, since the ${\mu_i}$ are arbitrary the resulting ${Q_i}$ might be strange enough that the game fails to have a reasonable strategy ${\sigma}$ ; in other words we’re worried the maximum might not be achievable. The easiest thing to do is write down a condition to handle this:

Definition 18

We say ${\mu = \{\mu_i\}_{i=1}^N}$ is regular if the virtual valuations ${\psi_i : [0,1000] \rightarrow \mathbb R}$ are strictly increasing for all ${i}$ .

Theorem 19 (Regularity implies optimal auction is achievable)

Assume regularity of ${\mu}$ . Consider a second-price auction with discriminatory reserve prices: the reserve price for player ${i}$ is the smallest ${x}$ such that ${\psi_i(x) > 0}$ , and the winner ${k}$ pays the smallest amount needed to win.

This is an incentive compatible mechanism which maximizes the expected revenue of the auctioneer.

Proof: The ${Q}$ described in the theorem is the one we mentioned earlier. The hypothesis defines ${P}$ as follows:

If ${\psi_k(x_k) > 0}$ is maximal, then that player wins and pays the smallest amount ${y}$ such that ${\psi_k(y)}$ still exceeds all other ${\psi_j(x_j)}$ .
Otherwise, the item is not sold.

The fact that this mechanism ${M = (P,Q,\mu)}$ is incentive compatible is more or less the same as before (bidding truthfully is a weakly dominant strategy). Moreover we already argued above that this allocation ${Q}$ maximizes revenue. $\Box$

You can and should think of this as a “reserve price second price auction” except with virtual valuations instead. The winner is the player with the highest virtual valuation, who is then allowed to retroactively change their bid so long as they still win.

To see this in action:

Corollary 20 (Optimal symmetric uniform auction)

Consider an auction in which ${n}$ players have uniform values in ${[0,1000]}$ . Then the optimal auction is a second-price auction with reserve price ${\$500}$ . The expected earning of the auctioneer is

$\displaystyle 1000 \cdot \frac{n - 1 + \left( \frac{1}{2} \right)^n}{n+1}.$

Proof: We compute each ${\psi_i}$ as

$\displaystyle \psi_i(x) = x - \frac{1 - \mu_i([0,x])}{\frac{d\mu_i}{dt}(x)} = x - \frac{1-x/1000}{1/1000} = 2x - 1000.$

Hence, we usually want to award the item to the player with the largest virtual valuation (i.e. the highest bidder), setting the reserve price at ${500}$ for everyone since ${\psi_i(500) = 0}$ . By (1) the expected payment from a player equals

$\displaystyle \frac{1}{1000} \int_{x=0}^{1000} \psi_i(x) \cdot q_i(x) \; dx = \frac{1}{1000}\int_{x=500}^{1000} (2x-1000) \cdot (x/1000)^{n-1} \; dx$

Simplifying and multiplying by ${n}$ gives the answer. $\Box$

More generally, in an asymmetric situation the optimal reserve prices are discriminatory and vary from player to player. As a nice exercise to get used to this:

Exercise 21

Find the optimal auction mechanism if two players are bidding, with one player having value distributed uniformly in ${[0,500]}$ and the other player having value distributed uniformly in ${[0,1000]}$ .

8. Against revelation

Here’s a pedagogical point: almost all sources state early on the so-called “revelation principle”.

Proposition 22 (Revelation principle)

Let ${M = (M, \sigma)}$ be a direct mechanism. Then there exists a incentive compatible mechanism ${M^\ast}$ such that

${M^\ast = (M^\ast, \mathrm{id})}$ is incentive compatible, and
For any ${i}$ , ${p_i^\ast = p_i}$ , ${q_i^\ast = q_i}$ , ${u_i^\ast = u_i}$ , i.e. at the equilibrium point, the expected payoffs and allocations don’t change.

Proof: Consider ${M = (M, \sigma)}$ . Then ${M^\ast}$ is played as follows:

Each player ${i}$ has an advisor to whom it tells their value ${x_i}$
The advisor and figures out the optimal bid ${\sigma_i(x_i)}$ in ${M}$ , and submits this bid on the player’s behalf.
The game ${M}$ is played with the advisor’s bids, and the payments / allocations are given to corresponding players.

Clearly the player should be truthful to their advisor. $\Box$

Most sources go on to say that this makes their life easier, because now they can instead say “it suffices to study incentive compatible mechanisms”. For example, one can use this to

Replace “direct mechanism” with “incentive-compatible direct mechanism”.
Replace “there exists a direct mechanism ${(M, \sigma)}$ ” with “there exists a ${(P,Q)}$ which is incentive compatible”.

However, I personally think this is awful. Here is why.

The proof of Revelation is almost tautological. Philosophically, it says that you should define the functions ${q_i}$ , ${p_i}$ , ${u_i}$ in terms of the equilibrium ${\sigma}$ . Authors which restrict to incentive compatible mechanisms are hiding this fact behind Revelation: now to the reader it’s no longer clear whether ${u_i}$ should be interpreted as taking a bid or value as input.

Put another way, the concept of a bid/value should be kept segregated. That’s why I use ${x_i}$ only for values, ${b_i}$ only for bids, and build in the equilibrium ${\sigma}$ as into ${u_i}$ , ${p_i}$ , ${q_i}$ ; So ${u_i(x)}$ is the expected utility of bidding ${\sigma(x_i)}$ in the equilibrium. Revelation does the exact opposite: it lets authors promiscuously mix the concepts of values and bids, and pushes ${\sigma}$ out of the picture altogether.

2 thoughts on “Mechanism Design and Revenue Equivalence”

J Esparza April 9, 20163:26 AM Reply

Hi! You seem to be able to think when you write in LaTeX. Do you have a visual program that helps you with that (WYGIWYS) or has it come from years of experience?

LikeLike
1. Evan Chen (陳誼廷) April 9, 20168:49 AM Reply
  
  I don’t use WYSIWYG, have gotten used to working with LaTeX source by now. My editor is Vim.
  
  LikeLike

Mechanism Design and Revenue Equivalence

1. Mechanisms

2. Examples of mechanisms

2.1. First-price auction

2.2. Second-price auction

2.3. All-pay auction

2.4. Extortion

2.5. Second-price auction with reserve

3. Direct mechanisms

4. Equivalence of utility and payment

5. Revenue equivalence

6. Design feasibility

7. Optimal auction

8. Against revelation

Published by Evan Chen (陳誼廷)

2 thoughts on “Mechanism Design and Revenue Equivalence”

Leave a Reply Cancel reply

1. Mechanisms

2. Examples of mechanisms

2.1. First-price auction

2.2. Second-price auction

2.3. All-pay auction

2.4. Extortion

2.5. Second-price auction with reserve

3. Direct mechanisms

4. Equivalence of utility and payment

5. Revenue equivalence

6. Design feasibility

7. Optimal auction

8. Against revelation

Share:

Like this:

Related

Published by Evan Chen (陳誼廷)

2 thoughts on “Mechanism Design and Revenue Equivalence”

Leave a Reply Cancel reply