2010 | OriginalPaper | Chapter
Quasi-Proportional Mechanisms: Prior-Free Revenue Maximization
Authors : Vahab Mirrokni, S. Muthukrishnan, Uri Nadav
Published in: LATIN 2010: Theoretical Informatics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Inspired by Internet ad auction applications, we study the problem of allocating a single item via an auction when bidders place very different values on the item. We formulate this as the problem of
prior-free
auction and focus on designing a simple mechanism that always allocates the item. Rather than designing sophisticated pricing methods like prior literature, we design better allocation methods. In particular, we propose
quasi-proportional
allocation methods in which the probability that an item is allocated to a bidder depends (quasi-proportionally) on the bids.
We prove that corresponding games for both all-pay and winners-pay quasi-proportional mechanisms admit pure Nash equilibria and this equilibrium is unique. We also give an algorithm to compute this equilibrium in polynomial time. Further, we show that the revenue of the auctioneer is promisingly high compared to the ultimate, i.e., the highest value of any of the bidders, and show bounds on the revenue of equilibria both analytically, as well as using experiments for specific quasi-proportional functions. This is the first known revenue analysis for these natural mechanisms (including the special case of proportional mechanism which is common in network resource allocation problems).