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.