TY - GEN

T1 - On the efficiency of sequential auctions for spectrum sharing

AU - Bae, Junjik

AU - Beigman, Eyal

AU - Berry, Randall

AU - Honig, Michael L.

AU - Vohra, Rakesh

PY - 2009

Y1 - 2009

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

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

UR - http://www.scopus.com/inward/record.url?scp=70350000221&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70350000221&partnerID=8YFLogxK

U2 - 10.1109/GAMENETS.2009.5137402

DO - 10.1109/GAMENETS.2009.5137402

M3 - Conference contribution

AN - SCOPUS:70350000221

SN - 9781424441778

T3 - Proceedings of the 2009 International Conference on Game Theory for Networks, GameNets '09

SP - 199

EP - 205

BT - Proceedings of the 2009 International Conference on Game Theory for Networks, GameNets '09

T2 - 2009 International Conference on Game Theory for Networks, GameNets '09

Y2 - 13 May 2009 through 15 May 2009

ER -