<p>I think what you want is the following proposition.</p>

<p><b>Proposition.</b>
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})).$$</p>

<p><b>Proof.</b>
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.</p>

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

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

CC BY-SA 3.0
2012-07-02T18:12:56.213Z
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.
Novak
CC BY-SA 3.0
2012-07-02T18:20:59.590Z
@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$?
Colin McQuillan
CC BY-SA 3.0
2012-07-02T18:29:09.233Z
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.)
Novak
CC BY-SA 3.0
2012-07-02T19:23:25.023Z
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.
Novak
CC BY-SA 3.0
2012-07-02T19:26:55.067Z
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.
Novak
CC BY-SA 3.0
2012-07-02T20:24:38.203Z
Ok - truthfulness is physically meaningful but it is usually modelled in a particular way, where truthfulness is just a property of $(f,p_1,\dots,p_n)$, and does not depend on a particular bidder or strategy profile. Unfortunately this is never made clear in the literature, so I can only say it as an assertion (and point out that it certainly makes the proofs more make sense!). You could interpret this as meaning it has to encourage truthfulness in all possible worlds, or something like that.
Colin McQuillan
CC BY-SA 3.0
2012-07-02T17:44:31.717Z
2012-07-02T17:44:31.717Z
Colin McQuillan
<p>The answer is that the mechanism must be truthful for <em>every</em> 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$.</p>

<p>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 </p>

CC BY-SA 3.0
2012-07-05T17:30:17.490Z
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.
Novak
CC BY-SA 3.0
2012-07-03T00:18:23.380Z
2012-07-03T00:18:23.380Z
Aaron Roth
<p>I have been struggling with the technical details of a proof concerning auction theory in this paper:  <a href="http://users.eecs.northwestern.edu/~hartline/omd.pdf">http://users.eecs.northwestern.edu/~hartline/omd.pdf</a></p>

<p>Specifically, Theorem 2.5:  The necessary and sufficient conditions for a truthful mechanism. </p>

<p>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$.</p>

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

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

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

<p>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?</p>

<p>(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 <em>necessary</em> to do it the author's way.  But I still don't understand it.)</p>

<p><strong>Update:</strong>  I knew I had seen something similar in <a href="http://rads.stackoverflow.com/amzn/click/0521899435">Shoham and Leyton-Brown's</a> 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. </p>

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

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

<gt.game-theory>
Understanding a Mechanism Design Proof
Novak
# Understanding a Mechanism Design Proof

(Asked by: username_0 on 2012-07-01)

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](http://rads.stackoverflow.com/amzn/click/0521899435) 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.

**Tags:** gt.game-theory


---

## 2 answers

### Answer by username_2 on 2012-07-03. Score: 11 | Accepted answer

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

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_1 on 2012-07-02. Score: 4

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.

> **Comments:**
> **username_0**: 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.  
> **username_1**: @username_0: 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$?  
> **username_0**: 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.)  
> **username_0**: 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.  
> **username_0**: 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.  
> **username_1**: Ok - truthfulness is physically meaningful but it is usually modelled in a particular way, where truthfulness is just a property of $(f,p_1,\dots,p_n)$, and does not depend on a particular bidder or strategy profile. Unfortunately this is never made clear in the literature, so I can only say it as an assertion (and point out that it certainly makes the proofs more make sense!). You could interpret this as meaning it has to encourage truthfulness in all possible worlds, or something like that.  

---

