I have been struggling with the technical details of a proof concerning auction theory in this paper:  http://users.eecs.northwestern.edu/~hartline/omd.pdfSpecifically, 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.
Understanding a Mechanism Design Proof
gt.game theory
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 