research-article

Breaking bidder collusion in large-scale spectrum auctions

Authors:

Haitao ZhengAuthors Info & Claims

MobiHoc '10: Proceedings of the eleventh ACM international symposium on Mobile ad hoc networking and computing

Pages 121 - 130

https://doi.org/10.1145/1860093.1860110

Published: 20 September 2010 Publication History

Abstract

Dynamic spectrum auction is an effective solution to provide spectrum on-demand to many small wireless networks. As the number of participants grows, bidder collusion becomes a serious threat. In this paper, we study bidder collusion in large-scale spectrum auctions, investigating its impact on auction outcomes. We found that the nature of the complex interference constraints among bidders provides a fertile breeding ground for colluders, causing significant damage in auction efficiency and revenue. In particular, collusion group of small size plays a dominant role since it is easy to form and hard to be detected.

We propose Athena, a new collusion-resistant auction framework for large-scale dynamic spectrum auction. Athena implements a soft collusion resistance, allowing the auctioneer to exploit the tradeoff between the level of collusion resistance and the cost of achieving such level of resistance. Unlike existing solutions, Athena enables spectrum reuse across bidders, achieves soft collusion resistance against any form of collusive bidding strategy, maintains provable revenue guarantee, and does so with polynomial-time complexity. To provide a comprehensive evaluation, we first analytically prove Athena's collusion resistance and revenue guarantee (under any bids), and then experimentally verify our analytical conclusions using empirical bid distributions.

References

[1]

}}Bajari, P., and Fox, J. T. Complementarities and collusion in an FCC spectrum auction. Tech. Rep. 11671, National Bureau of Economic Research, October 2005.

[2]

}}Bajari, P., and Yeo, J. Auction design and tacit collusion in FCC spectrum auctions. Tech. Rep. 14441, National Bureau of Economic Research, October 2008.

[3]

}}Buddhikot, M., and Ryan, K. Spectrum management in coordinated dynamic spectrum access based cellular networks. In Proc. of DySPAN (2005).

[4]

}}Clarke, E. Multipart pricing of public goods. Public Choice XI (1971), 17--33.

[5]

}}Cramton, P., and Schwartz, J. Collusive bidding: Lessons from the FCC spectrum auctions. Journal of REgulatory Economics 17 (May 2000), 229--252.

[6]

}}Cramton, P., and Schwartz, J. Collusive bidding in the FCC spectrum auctions. Tech. rep., U. Maryland, 2002.

[7]

}}Fleishman, G. So many nodes, no little security. The New York Times (2002).

[8]

}}Friedman, M. Comment on 'collusion in the auction market for treasury bills'. J. of Political Economy 9 (1996), 757--785.

[9]

}}Gandhi, S., et al. A general framework for wireless spectrum auctions. In Proc. of DySPAN (2007).

Digital Library

[10]

}}Goldberg, A. V., and Hartline, J. D. Competitiveness via consensus. In Proc. of SODA (2003).

Digital Library

[11]

}}Goldberg, A. V., and Hartline, J. D. Collusion-resistant mechanisms for single-parameter agents. In Proc. of SODA (2005).

Digital Library

[12]

}}Goswami, G., Noe, T. H., and Rebello, M. J. Collusion in uniform-price auctions: Experimental evidence and implications for treasury auctions. Review of Financial Studies 72 (1964), 513--514.

[13]

}}Groves, T. Incentive in terms. Econometrica 41 (1973), 617--631.

[14]

}}Gupta, A., and Nadarajah, S. Handbook of Beta Distribution and Its Applications. CRC Press, 2004.

[15]

}}Ileri, O., and Mandayam, N. Dynamic spectrum access models: toward an engineering perspective in the spectrum debate. IEEE Commu. Magazine 46, 1 (2008), 153--160.

Digital Library

[16]

}}Ji, Z., and Liu, K. Multi-stage pricing game for collusion-resistant dynamic spectrum allocation. IEEE JSAC 26, 1 (Jan. 2008), 182--191.

Digital Library

[17]

}}Jia, J., Zhang, Q., Zhang, Q., and Liu, M. Revenue generation for truthful spectrum auction in dynamic spectrum access. In Proc. of MobiHoc (2009).

Digital Library

[18]

}}Krishna, V. Auction Theory. Academic Press, March 2002.

[19]

}}Lian, Q., et al. An empirical study of collusion behavior in the maze P2P file-sharing system. In Proc. of ICDCS (2007).

Digital Library

[20]

}}McSherry, F., and Talwar, K. Mechanism design via differential privacy. In Proc. of FOCS (2007).

Digital Library

[21]

}}Ramanathan, S. A unified framework and algorithm for channel assignment in wireless networks. Wirel. Netw. 5, 2 (1999), 81--94.

Digital Library

[22]

}}Subramanian, A. P., et al. Fast spectrum allocation in coordinated dynamic spectrum access based cellular networks. In Proc. of DySPAN (2007).

Digital Library

[23]

}}Wu, Y., et al. Collusion-resistant multi-winner spectrum auction for cognitive radio networks. In Proc. of Globecom (2008).

[24]

}}Wu, Y., Wang, B., Liu, R., and Clancy, T. A scalable collusion-resistant multi-winner cognitive spectrum auction game. IEEE Transactions on Communications (Dec. 2009).

[25]

}}Zhou, X., et al. eBay in the sky: Strategy-proof wireless spectrum auctions. In Proc. of MobiCom (2008).

Digital Library

[26]

}}Zhou, X., and Zheng, H. TRUST: A general framework for truthful double spectrum auctions. In Proc. of INFOCOM (2009).

Cited By

Xiao MJin WLi MYang LThapa ALi P(2023)Collusion-Resistant Worker Recruitment in Crowdsourcing SystemsIEEE Transactions on Mobile Computing10.1109/TMC.2021.307109322:1(129-144)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TMC.2021.3071093
Li WCheng XTian ZWang SBie RYu J(2021)Truthful Auction Analysis and Design in Multiunit Heterogenous Spectrum Markets With Reserve PricesIEEE Transactions on Cognitive Communications and Networking10.1109/TCCN.2020.29966027:1(157-170)Online publication date: Mar-2021
https://doi.org/10.1109/TCCN.2020.2996602
Wang QHuang JChen YTian XZhang Q(2019)Privacy-Preserving and Truthful Double Auction for Heterogeneous SpectrumIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2019.290387927:2(848-861)Online publication date: 17-May-2019
https://dl.acm.org/doi/10.1109/TNET.2019.2903879
Show More Cited By

Index Terms

Breaking bidder collusion in large-scale spectrum auctions
1. Networks
  1. Network architectures

Recommendations

Iterative Combinatorial Auctions with Bidder-Determined Combinations

In combinatorial auctions, multiple distinct items are sold simultaneously and a bidder may place a single bid on a set (package) of distinct items. The determination of packages for bidding is a nontrivial task, and existing efficient formats require ...
Robust Large-Scale Spectrum Auctions against False-Name Bids

Auction is a promising approach for dynamic spectrum access in cognitive radio networks. Existing auction mechanisms are mainly strategy-proof to stimulate bidders to reveal their valuations of spectrum truthfully. However, they can suffer significantly ...
The Impact of Discrete Bidding and Bidder Aggressiveness on Sellers' Strategies in Open English Auctions: Reserves and Covert Shilling

In practice, the rules in most open English auctions require participants to raise bids by a sizeable, discrete amount. Furthermore, some bidders are typically more aggressive in seeking to become the "current bidder" during competitive bidding. Most ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

MobiHoc '10: Proceedings of the eleventh ACM international symposium on Mobile ad hoc networking and computing

September 2010

272 pages

ISBN:9781450301831

DOI:10.1145/1860093

General Chair:
Nitin Vaidya
University of Illinois at Urbana-Champaign, USA
,
Program Chairs:
Christoph Lindemann
Universität Leipzig
,
Jitendra Padhye
Microsoft Research

Copyright © 2010 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

SIGMOBILE: ACM Special Interest Group on Mobility of Systems, Users, Data and Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 September 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

MobiCom/MobiHoc '10

Sponsor:

SIGMOBILE

MobiCom/MobiHoc '10: The 16th Annual International Conference on Mobile Computing and Networking and The 11th ACM International Symposium on Mobile Ad Hoc Networking and Computing

September 20 - 24, 2010

Illinois, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 296 of 1,843 submissions, 16%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

33
Total Citations
View Citations
367
Total Downloads

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

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Xiao MJin WLi MYang LThapa ALi P(2023)Collusion-Resistant Worker Recruitment in Crowdsourcing SystemsIEEE Transactions on Mobile Computing10.1109/TMC.2021.307109322:1(129-144)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TMC.2021.3071093
Li WCheng XTian ZWang SBie RYu J(2021)Truthful Auction Analysis and Design in Multiunit Heterogenous Spectrum Markets With Reserve PricesIEEE Transactions on Cognitive Communications and Networking10.1109/TCCN.2020.29966027:1(157-170)Online publication date: Mar-2021
https://doi.org/10.1109/TCCN.2020.2996602
Wang QHuang JChen YTian XZhang Q(2019)Privacy-Preserving and Truthful Double Auction for Heterogeneous SpectrumIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2019.290387927:2(848-861)Online publication date: 17-May-2019
https://dl.acm.org/doi/10.1109/TNET.2019.2903879
Wang JLong YWang JErrapotu SLi HPan MHan Z(2018)D-FROST: Distributed Frequency Reuse-Based Opportunistic Spectrum Trading via Matching With Evolving PreferencesIEEE Transactions on Wireless Communications10.1109/TWC.2018.281606417:6(3794-3806)Online publication date: Jun-2018
https://doi.org/10.1109/TWC.2018.2816064
Wu SChen YWang QLi MWang CLuo X(2018)CReam: A Smart Contract Enabled Collusion-Resistant e-AuctionIEEE Transactions on Information Forensics and Security10.1109/TIFS.2018.2883275(1-1)Online publication date: 2018
https://doi.org/10.1109/TIFS.2018.2883275
Pan MZhu XFang Y(2018)Using homomorphic encryption to secure the combinatorial spectrum auction without the trustworthy auctioneerWireless Networks10.1007/s11276-011-0390-318:2(113-128)Online publication date: 29-Dec-2018
https://dl.acm.org/doi/10.1007/s11276-011-0390-3
Chen LIellamo SCoupechoux MGodlewski P(2018)Spectrum auction with interference constraint for cognitive radio networks with multiple primary and secondary usersWireless Networks10.1007/s11276-011-0353-817:5(1355-1371)Online publication date: 29-Dec-2018
https://dl.acm.org/doi/10.1007/s11276-011-0353-8
Wu FPeng D(2018)CollusionEncyclopedia of Wireless Networks10.1007/978-3-319-32903-1_32-1(1-4)Online publication date: 24-Apr-2018
https://doi.org/10.1007/978-3-319-32903-1_32-1
Wang QSun QRen KJia X(2017)THEMIS: Collusion-Resistant and Fair Pricing Spectrum Auction Under Dynamic SupplyIEEE Transactions on Mobile Computing10.1109/TMC.2016.260942516:7(2051-2064)Online publication date: 1-Jul-2017
https://doi.org/10.1109/TMC.2016.2609425
Wang QYe BTang BXu TGuo SLu SZhuang W(2017)Robust Large-Scale Spectrum Auctions against False-Name BidsIEEE Transactions on Mobile Computing10.1109/TMC.2016.260190816:6(1730-1743)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1109/TMC.2016.2601908
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