9
$\begingroup$

I have been struggling with the technical details of a proof concerning auction theory in this paper: http://users.eecs.northwestern.edu/~hartline/omd.pdf

Specifically, Theorem 2.5: The necessary and sufficient conditions for a truthful mechanism.

Even more specifically, the forward direction of the proof, given on page 6. Defining a truthful value as $v_i$, and a general, possibly false, value (e.g., a bid) as $b_i$, the author goes on to postulate two additional quantities, $z_1$ and $z_2$.

He then stipulates that $v_i = z_1$, $b_i = z_2$, which yields an inequality based on the previous work of the paper.

He also stipulates that $v_i = z_2$, $b_i = z_1$, which yields a similar but different inequality based on the previous work of the paper.

Okay, fair enough. He then subtracts one inequality from the other and proceeds to derive his desired result on the basis of the consequent algebra. I don't understand why that subtraction is justified-- he seems to be subtracting two inequalities that are based on entirely different (in fact, opposite) assumptions, and every time I see it I am thrown violently out of the train of thought.

I'm pretty sure I've seen this basic approach else (Shoham and Leyton-Brown's book? I don't have it close at hand to check) so it seems to be a common idea, but I cannot get past it. Can anyone help me to understand why that is valid, or explain to me what I am missing?

(I've tried proving the desired result by assuming three values-- a true value $v_i$, and two bids, $b_1$ and $b_2$-- to get his desired result, but also failed. So it may not only be common, but necessary to do it the author's way. But I still don't understand it.)

Update: I knew I had seen something similar in Shoham and Leyton-Brown's book. It is not exactly the same, but it is very similar and deals with the same equation and subject matter. It is Case 1 of Theorem 10.4.3.

Starting from the context of truthful mechanisms, they first assume a truthful $v_i$ and a false $v_i'$ and derive that the payment based on $v_i$ is lesser than or equal to the payment based on $v_i'$, e.g., $P_i(v_i) \leq P_i(v_i')$. They then assume the opposite, a truthful $v_i'$ and a false $v_i$, and derive the opposite result, that the payment based on $v_i'$ is less than the payment based on $v_i$, e.g., $P_i(v_i') \leq P_i(v_i)$. Okay, that makes sense.

They then hold that the payments based on $v_i$ and $v_i'$ must be equal, as though they are saying that $P_i(v_i) \leq P_i(v_i')$ and $P_i(v_i') \leq P_i(v_i)$ are simultaneously true, even though they are the result of not just different, but opposite assumptions.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
11
$\begingroup$

The answer is that the mechanism must be truthful for every set of possible types: the mechanism does not know which are the true types ahead of time. So for a pair of types $v_i$ and $v_i'$, the mechanism must be truthful if an agent's true type is $v_i$: i.e. his utility must be greater if he bids $v_i$ than if he bids $v_i'$. But the mechanism must also be truthful if the agent's true type is $v_i'$! After all, as far as the mechanism is concerned, it might be! So in this case, an agent's utility must be greater if he bids $v_i'$ as compared to $v_i$.

The point is that truthfulness imposes many different inequalities on the same mechanism simultaneously: one for every type an agent might have, and for every deviation he might consider. All of them hold. This proof uses only two of these inequalities

Improve this answer
$\endgroup$
1
  • $\begingroup$ I think I am finally starting to understand that. In fact, knowing that the proof is correct (and why) impresses on me even more how strict and powerful the concept of "truthfulness" actually is. Thank you. $\endgroup$ Commented Jul 5, 2012 at 17:30
4
$\begingroup$

I think what you want is the following proposition.

Proposition. Let $V$ and $A$ be sets. Let $f:V^n\to A$ and $p_1,\dots,p_n:V^n\to\mathbb{R}$. Assume that for all $i,x_i,y_i,v_{−i}$ we have $$x_i (f(x_i , v_{−i})) − p_i (x_i , v_{−i}) \geq x_i (f(y_i , v_{−i})) − p_i (y_i , v_{−i}).$$ Then for all $i,v_i,v'_i,v_{-i}$ we have $$v_i(f(v_i,v_{-i}))-v_i(f(v'_i,v_{-i}))\geq v'_i(f(v_i,v_{-i}))-v'_i(f(v'_i,v_{-i})).$$

Proof. Putting $x_i=v_i$ and $y_i=v'_i$ we have $$v_i (f(v_i , v_{−i})) − p_i (v_i , v_{−i}) \geq v_i (f(v'_i , v_{−i})) − p_i (v'_i , v_{−i}).$$ Putting $x_i=v_i$ and $y_i=v'_i$ we have $$v'_i (f(v'_i , v_{−i})) − p_i (v'_i , v_{−i}) \geq v'_i (f(v_i , v_{−i})) − p_i (v_i , v_{−i}).$$ The result follows by adding these inequalities and rearranging.

The mechanism design interpretation of this proposition is that every incentive compatible (i.e. strategy proof, i.e. truthful) mechanism has "weak monotonicity".

For some reason, it is conventional to argue by refering to true bids and lies. In this context, "true" and "lie" are just variable names, like "x" and "y". It is fine to use the same name to refer to different things in separate arguments, because there is no formal difference between a true bid and a lie.

Improve this answer
$\endgroup$
6
  • $\begingroup$ That is the proposition in question. (Although I think you have a typo in the third line of your proof-- the v_i assignments should be swapped from the first line.) I am still hazy on why it is acceptable to add the two inequalities when they result from different assumptions. Yes, there is no formal difference between a true and a false bid; they are both numbers. But they are (or to be precise, they can be) different numbers. $\endgroup$ Commented Jul 2, 2012 at 18:12
  • $\begingroup$ @Novak: How about this: if I tell you that $g(a,b)=1$ for all $a,b$, would you accept that $g(x,y)-g(y,x)=0$ for all $x,y$? $\endgroup$ Commented Jul 2, 2012 at 18:20
  • $\begingroup$ Yes. But let me chew on that in the mechanism design context for a little bit. (And at the same time update my original post in Mathjax, and add the similar case I dug out of Shoham and Leyton-Brown.) $\endgroup$ Commented Jul 2, 2012 at 18:29
  • $\begingroup$ What bothers me here is in your set-up of the proposition. When I see that assertion that the proposition is true, it is already in the context that $x_i$ is the true value, and $y_i$ is the (possibly) false bid. I also question the idea of 'true' and 'lie' being variable names; rather, true and lie seem to be actual qualities of reported values, the point of the game being to take advantage of this difference to incentivize the reporting of the truthful quality. $\endgroup$ Commented Jul 2, 2012 at 19:23
  • $\begingroup$ More concretely, if you tell me that $g(a,b) = 1$ for all truthful $a$, for all $b$ (which is a little closer to the original context) then I can accept that $g(x,y) - g(y,x) = 0$ if I know that both $x$ and $y$ are truthful. $\endgroup$ Commented Jul 2, 2012 at 19:26

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.