  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).
