Claim: A shortest chain cannot contain a down link followed by an up link.
ci = clicks at pos i [ci > … > cn ]
vi = value of bidder in VCG pos i
Proof: Use shortcut.
v = ci (vj – vk) + ck (vk- vj)
= (ci – ck) (vj – vk)
… yes, otherwise original solution would switch j and k.
v ¸ 0, i.e. new allocation is no worse and has a shorter chain.
vj ¸vk ?
ci ¸ ck ?