No truthful, IR and deterministic online auction can obtain $(2-\epsilon)$-approximation for efficiency theorem proof is unclear to me

28 Views Asked by At

enter image description here

The theorem is from Algorithmic Game Theory Textbook by Nisan et al. available here on page 423 https://www.cs.cmu.edu/~sandholm/cs15-892F13/algorithmic-game-theory.pdf

To elaborate on the notation, $\theta_i = (a_i, d_i, r_i)$ is the type of agent $i$ and has arrival and departure times $a_i$ and $d_i$ and values their desired item by $r_i$. Critical values are denoted by $v^c_{(a_i,d_i)}(\theta_{-i})$. That is, it is the lowest $r_i$ that can be reported alongside times $a_i, d_i$ and when the other agents have types represented by $\theta_{-i}$.

I do not understand how the three scenarios presented in the proof establish the theorem. I fail to see the contradiction in (i) and while I understand the points (ii) and (iii) are making I do not see how these three scenarios exhaust the space of all truthful, IR, deterministic online auctions. Also it seems to me that if we want to show that no online auction with the aforementioned properties can a $(2-\epsilon)$-efficiency then we would have to consider arbitrary types and not just a few hand picked ones; why is this not the case?

I am still very new to the subject and think that I am not familiar with the structure that a lot of the proofs follow. Thank you in advance for any help.