Prompt Mechanisms for Online Auctions

摘要: We study the following online problem: at each time unit, one of midentical items is offered for sale. Bidders arrive and depart dynamically, bidder interested in winning item between his arrival departure. Our goal to design truthful mechanisms that maximize welfare, sum utilities bidders. We first consider this problem under assumption private information value getting an item. In model constant-competitive are known, but we observe these suffer from disadvantage: a might learn payment only when he departs. argue mechanism essentially unusable, because they impose several seemingly undesirable requirements on any implementation mechanisms. To crystalize issues, define notions promptand tardymechanisms. present two prompt mechanisms, deterministic other randomized, guarantee constant competitive ratio. show our optimal setting. We then which both departure information. While setting trivial ratio can be guaranteed, use randomization obtain ${\it \Theta}(\frac 1 {\log m})$-competitive mechanism. no randomized achieve better than $\frac 2$ model.