1st International Conference on Game Theory for Networks

Research Article

On the efficiency of sequential auctions for spectrum sharing

  • @INPROCEEDINGS{10.1109/GAMENETS.2009.5137402,
        author={Junjik  Bae and Eyal  Beigman and Randall  Berry and Michael L. Honig and Rakesh  Vohra},
        title={On the efficiency of sequential auctions for spectrum sharing},
        proceedings={1st International Conference on Game Theory for Networks},
  • Junjik Bae
    Eyal Beigman
    Randall Berry
    Michael L. Honig
    Rakesh Vohra
    Year: 2009
    On the efficiency of sequential auctions for spectrum sharing
    DOI: 10.1109/GAMENETS.2009.5137402
Junjik Bae1,*, Eyal Beigman2,*, Randall Berry3,*, Michael L. Honig3,*, Rakesh Vohra4,*
  • 1: Boston consulting Group, Seoul Korea.
  • 2: Olin Business School, Washington University, in St. Louis
  • 3: Department of Electrical Engineering and Computer Science at Northwestern University
  • 4: CMS-EMS, Kellogg School of Management at Northwestern University
*Contact email: baejunjik@gmail.com, beigman@olin.wustl.edu, rberry@eecs.northwestern.edu, mhg@eecs.northwestern.edu, r-vohra@northwestern.edu


In previous work we have studied the use of sequential second price auctions for sharing a wireless resource, such as bandwidth or power. The resource is assumed to be managed by a spectrum broker (auctioneer), who collects bids and allocates discrete units of the resource. It is well known that a second price auction for a single indivisible good has an efficient dominant strategy equilibrium; this is no longer the case when multiple units of a homogeneous good are sold in repeated iterations. Previous work attempted to bound this inefficiency loss for two users with non-increasing marginal valuations and full information. This work was based on studying a setting in which one agent's valuation for each resource unit is strictly larger than any of the other agent's valuations and assuming a certain property of the price paid by such a dominant user in any sub-game. Using this assumption it was shown that the worst-case efficiency loss was no more than e-1. However, here we show that this assumption is not satisfied for all non-increasing marginals with this dominance property. In spite of this, we show that it is always true for the worst-case marginals for any number of goods and so the worst-case efficiency loss for any non-increasing marginal valuations is still bounded by e-1.