research-article

Approximation algorithms for secondary spectrum auctions

Authors:

Thomas Kesselheim,

Berthold VöckingAuthors Info & Claims

SPAA '11: Proceedings of the twenty-third annual ACM symposium on Parallelism in algorithms and architectures

Pages 177 - 186

https://doi.org/10.1145/1989493.1989520

Published: 04 June 2011 Publication History

Abstract

We study combinatorial auctions for the secondary spectrum market. In this market, short-term licenses shall be given to wireless nodes for communication in their local neighborhood. In contrast to the primary market, channels can be assigned to multiple bidders, provided that the corresponding devices are well separated such that the interference is sufficiently low. Interference conflicts are described in terms of a conflict graph in which the nodes represent the bidders and the edges represent conflicts such that the feasible allocations for a channel correspond to the independent sets in the conflict graph.

In this paper, we suggest a novel LP formulation for combinatorial auctions with conflict graph using a non-standard graph parameter, the so-called inductive independence number. Taking into account this parameter enables us to bypass the well-known lower bound of Ω(n^1-ε) on the approximability of independent set in general graphs with n nodes (bidders). We achieve significantly better approximation results by showing that interference constraints for wireless networks yield conflict graphs with bounded inductive independence number.

Our framework covers various established models of wireless communication, e.g., the protocol or the physical model. For the protocol model, we achieve an O(√k)-approximation, where k is the number of available channels. For the more realistic physical model, we achieve an O(√k log² n) approximation based on edge-weighted conflict graphs. Combining our approach with the LP-based framework of Lavi and Swamy, we obtain incentive compatible mechanisms for general bidders with arbitrary valuations on bundles of channels specified in terms of demand oracles.

References

[1]

Karhan Akcoglu, James Aspnes, Bhaskar DasGupta, and Ming-Yang Kao. Opportunity cost algorithms for combinatorial auctions. CoRR, cs.CE/0010031, 2000.

[2]

Mansoor Alicherry, Randeep Bhatia, and Li (Erran) Li. Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks. In Proceedings of the 11th International Conference on Mobile Computing and Networking (MobiCom), pages 58--72, 2005.

Digital Library

[3]

H. Balakrishnan, C.L. Barrett, V.S.A. Kumar, M.V. Marathe, and S. Thite. The distance-2 matching problem and its relationship to the mac-layer capacity of ad hoc wireless networks. Selected Areas in Communications, IEEE Journal on, 22(6):1069 -- 1079, aug. 2004.

Digital Library

[4]

Christopher L. Barrett, V. S. Anil Kumar, Madhav V. Marathe, Shripad Thite, and Gabriel Istrate. Strong edge coloring for channel assignment in wireless radio networks. In Proceedings of the 4th annual IEEE international conference on Pervasive Computing and Communications Workshops (PERCOMW), page 106, 2006.

Digital Library

[5]

Milind M. Buddhikot, Paul Kolodzy, Scott Miller, Kevin Ryan, and Jason Evans. Dimsumnet: New directions in wireless networking using coordinated dynamic spectrum access. In Proceedings of the IEEE WoWMoM, pages 78--85, 2005.

Digital Library

[6]

George Christodoulou, Khaled Elbassioni, and Mahmoud Fouz. Truthful mechanisms for exhibitions. In Proceedings of the 6th Workshop on Internet & Network Economics (WINE), pages 170--181, 2010.

Digital Library

[7]

Peter Cramton, Yoav Shoham, and Richard Steinberg, editors. Combinatorial Auctions. MIT Press, 2006.

Digital Library

[8]

Shahar Dobzinski, Noam Nisan, and Michael Schapira. Truthful randomized mechanisms for combinatorial auctions. In Proceedings of the 38th ACM Symposium on Theory of Computing (STOC), pages 644--652, 2006.

Digital Library

[9]

Alexander Fanghanel, Sascha Geulen, Martin Hoefer, and Berthold Vöcking. Online capacity maximization in wireless networks. In Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 92--99, 2010.

Digital Library

[10]

Alexander Fanghanel, Thomas Kesselheim, Harald Racke, and Berthold Vöcking. Oblivious interference scheduling. In Proceedings of the 28th ACM Symposium on Principles of Distributed Computing (PODC), pages 220--229, 2009.

Digital Library

[11]

Alexander Fanghanel, Thomas Kesselheim, and Berthold Vöcking. Improved algorithms for latency minimization in wireless networks. In Proceedings of the 36th International EATCS Colloquium on Automata, Languages and Programming (ICALP), volume 2, pages 208--219, 2009.

Digital Library

[12]

Uriel Feige and Jan Vondrák. Approximation algorithms for allocation problems: Improving the factor of 1-1/e. In Proceedings of the 47th IEEE Symposium on Foundations of Computer Science (FOCS), pages 667--676, 2006.

Digital Library

[13]

Aleksei V. Fishkin. Disk graphs: A short survey. In Proceedings of the First Workshop on Approximation and Online Algorithms (WAOA), pages 260--264, 2003.

[14]

S. Gandhi, C. Buragohain, Lili Cao, Haitao Zheng, and S. Suri. A general framework for wireless spectrum auctions. In Proceedings of the 2nd IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks (DySPAN), pages 22--33, April 2007.

Digital Library

[15]

Olga Goussevskaia, Roger Wattenhofer, Magnús M. Halldórsson, and Emo Welzl. Capacity of arbitrary wireless networks. In Proceedings of the 28th Conference of the IEEE Communications Society (INFOCOM), pages 1872--1880, 2009.

[16]

Albert Graf, Martin Stumpf, and Gerhard Weißenfels. On coloring unit disk graphs. Algorithmica, 20:277--293, 1994.

[17]

Piyush Gupta and P. R. Kumar. The capacity of wireless networks. IEEE Transactions on Information Theory, 46:388--404, 2000.

Digital Library

[18]

Magnús M. Halldórsson. Wireless scheduling with power control. In Proceedings of the 17th European Symposium on Algorithms (ESA), pages 361--372, 2009.

[19]

J. Håstad. Clique is hard to approximate within n<sup>1-ε</sup>. Acta Mathematica, 182(1):105--142, 1999.

[20]

Ron Holzman, Noa Kfir-Dahav, Dov Monderer, and Moshe Tennenholtz. Bundling equilibrium in combinatorial auctions. Games and Economic Behavior, 47(1):104--123, 2004.

[21]

Omer Ileri, Dragan Samardzija, Theodore Sizer, and Narayan B. Mandayam. Demand responsive pricing and competitive spectrum allocation via a spectrum server. In Proceedings of the 1st IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks (DySPAN), pages 194--202, 2005.

[22]

Thomas Kesselheim. A constant-factor approximation for wireless capacity maximization with power control in the SINR model. In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1549--1559, 2011.

Digital Library

[23]

Thomas Kesselheim and Berthold Vöcking. Distributed contention resolution in wireless networks. In Proceedings of the 24th Symposium on Distributed Computing (DISC), pages 149--163, 2010.

Digital Library

[24]

Ron Lavi and Chaitanya Swamy. Truthful and near-optimal mechanism design via linear programming. In Proceedings of the 46th IEEE Symposium on Foundations of Computer Science (FOCS), pages 595--604, 2005.

Digital Library

[25]

Noam Nisan, Éva Tardos, Tim Roughgarden, and Vijay Vazirani, editors. Algorithmic Game Theory. Cambridge University Press, 2007.

Digital Library

[26]

Luca Trevisan. Non-approximability results for optimization problems on bounded degree instances. In Proceedings of the 33rd ACM Symposium on Theory of Computing (STOC), pages 453--461, 2001.

Digital Library

[27]

Jan Vondrák. Optimal approximation for the submodular welfare problem in the value oracle model. In Proceedings of the 40th ACM Symposium on Theory of Computing (STOC), pages 67--74, 2008.

Digital Library

[28]

Peng-Jun Wan. Multiflows in multihop wireless networks. In Proceedings of the 10th ACM International Symposium Mobile Ad-Hoc Networking and Computing (MOBIHOC), pages 85--94, 2009.

Digital Library

[29]

Yuli Ye and Allan Borodin. Elimination graphs. In Proceedings of the 36th International EATCS Colloquium on Automata, Languages and Programming (ICALP), pages 774--785, 2009.

Digital Library

[30]

Xia Zhou, Sorabh Gandhi, Subhash Suri, and Haitao Zheng. eBay in the Sky: Strategy-proof wireless spectrum auctions. In Proceedings of the 14th International Conference on Mobile Computing and Networking (MobiCom), pages 2--13, 2008.

Digital Library

[31]

Xia Zhou and Haitao Zheng. TRUST: A general framework for truthful double spectrum auctions. In Proceedings of the 28th Conference of the IEEE Communications Society (INFOCOM), pages 999--1007, 2009.

Cited By

Yang ZCui YXiao SWang XLi MLi CLiu Y(2019)Achieving Efficient Routing in Reconfigurable DCNsProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/33666953:3(1-30)Online publication date: 17-Dec-2019
https://dl.acm.org/doi/10.1145/3366695
Halldórsson MWattenhofer R(2019)Wireless Network AlgorithmicsComputing and Software Science10.1007/978-3-319-91908-9_9(141-160)Online publication date: 2019
https://doi.org/10.1007/978-3-319-91908-9_9
Fortetsanakis GDimitriou IPapadopouli M(2017)A Game-Theoretical Analysis of Wireless Markets Using Network AggregationIEEE Transactions on Mobile Computing10.1109/TMC.2016.257075616:3(602-616)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1109/TMC.2016.2570756
Show More Cited By

Index Terms

Approximation algorithms for secondary spectrum auctions
1. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Approximation Algorithms for Secondary Spectrum Auctions
Special Issue on Pricing and Incentives in Networks and Systems and Regular Papers

We study combinatorial auctions for secondary spectrum markets, where short-term communication licenses are sold to wireless nodes. Channels can be assigned to multiple bidders according to interference constraints captured by a conflict graph. We ...
Secondary Spectrum Auctions for Symmetric and Submodular Bidders
Special Issue on EC'12, Part 2

We study truthful auctions for secondary spectrum usage in wireless networks. In this scenario, n communication requests need to be allocated to k available channels that are subject to interference and noise. We present the first truthful mechanisms ...
Risk aversion and loss aversion in core-selecting auctions

Core-selecting combinatorial auctions have been introduced as an alternative to the Vickrey-Clarke-Groves (VCG) mechanism because VCG can result in payments that are not in the core with respect to bids, leading to unfair payments, unacceptably low ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '11: Proceedings of the twenty-third annual ACM symposium on Parallelism in algorithms and architectures

June 2011

404 pages

ISBN:9781450307437

DOI:10.1145/1989493

Co-chairs:
Friedhelm Meyer auf der Heide
University of Paderborn, Germany
,
Rajmohan Rajaraman
Northeastern University, USA

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

In-Cooperation

EATCS: European Association for Theoretical Computer Science

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 June 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SPAA '11

Sponsor:

SPAA '11: 23rd ACM Symposium on Parallelism in Algorithms and Architectures

June 4 - 6, 2011

California, San Jose, USA

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

32
Total Citations
View Citations
234
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yang ZCui YXiao SWang XLi MLi CLiu Y(2019)Achieving Efficient Routing in Reconfigurable DCNsProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/33666953:3(1-30)Online publication date: 17-Dec-2019
https://dl.acm.org/doi/10.1145/3366695
Halldórsson MWattenhofer R(2019)Wireless Network AlgorithmicsComputing and Software Science10.1007/978-3-319-91908-9_9(141-160)Online publication date: 2019
https://doi.org/10.1007/978-3-319-91908-9_9
Fortetsanakis GDimitriou IPapadopouli M(2017)A Game-Theoretical Analysis of Wireless Markets Using Network AggregationIEEE Transactions on Mobile Computing10.1109/TMC.2016.257075616:3(602-616)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1109/TMC.2016.2570756
Elbassioni KMehlhorn KRamezani F(2016)Towards More Practical Linear Programming-based Techniques for Algorithmic Mechanism DesignTheory of Computing Systems10.1007/s00224-016-9704-259:4(641-663)Online publication date: 1-Nov-2016
https://dl.acm.org/doi/10.1007/s00224-016-9704-2
Halldorsson MTonoyan TServedio RRubinfeld R(2015)How Well Can Graphs Represent Wireless Interference?Proceedings of the forty-seventh annual ACM symposium on Theory of Computing10.1145/2746539.2746585(635-644)Online publication date: 14-Jun-2015
https://dl.acm.org/doi/10.1145/2746539.2746585
Wu FHuang QTao YChen G(2015)Towards privacy preservation in strategy-proof spectrum auction mechanisms for noncooperative wireless networksIEEE/ACM Transactions on Networking10.1109/TNET.2014.232210423:4(1271-1285)Online publication date: 1-Aug-2015
https://dl.acm.org/doi/10.1109/TNET.2014.2322104
Zheng ZWu FChen G(2015)A Strategy-Proof Combinatorial Heterogeneous Channel Auction Framework in Noncooperative Wireless NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2014.234362414:6(1123-1137)Online publication date: 1-Jun-2015
https://doi.org/10.1109/TMC.2014.2343624
Li HWu CLi Z(2015)Socially-optimal online spectrum auctions for secondary wireless communication2015 IEEE Conference on Computer Communications (INFOCOM)10.1109/INFOCOM.2015.7218589(2047-2055)Online publication date: Apr-2015
https://doi.org/10.1109/INFOCOM.2015.7218589
Canzar SElbassioni KKlau GMestre J(2015)On Tree-Constrained Matchings and GeneralizationsAlgorithmica10.1007/s00453-013-9785-071:1(98-119)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1007/s00453-013-9785-0
Elbassioni KMehlhorn KRamezani F(2015)Towards More Practical Linear Programming-Based Techniques for Algorithmic Mechanism DesignAlgorithmic Game Theory10.1007/978-3-662-48433-3_8(98-109)Online publication date: 10-Dec-2015
https://doi.org/10.1007/978-3-662-48433-3_8
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents