X hits on this document

Powerpoint document

Bidding to the Top: Position-based Auctions - page 20 / 23

45 views

0 shares

0 downloads

0 comments

20 / 23

A Nugget

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)

A

B

i

Z

j

k

… yes

… 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 ?

Document info
Document views45
Page views45
Page last viewedSun Dec 04 19:35:54 UTC 2016
Pages23
Paragraphs254
Words1078

Comments