Article

Efficient contention resolution protocols for selfish agents

Authors:

Amos Fiat,

Yishay Mansour,

Uri NadavAuthors Info & Claims

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 179 - 188

Published: 07 January 2007 Publication History

Get Access

Abstract

We seek to understand behavior of selfish agents accessing a broadcast channel. In particular, we consider the natural agent utility where costs are proportional to delay. Access to the channel is modelled as a game in extensive form with simultaneous play.

Standard protocols such as Aloha are vulnerable to manipulation by selfish agents. We show that choosing appropriate transmission probabilities for Aloha to achieve equilibrium implies exponentially long delays. We give a very simple protocol for the agents that is in Nash equilibrium and is also very efficient --- other than with exponentially negligible probability --- all n agents will successfully transmit within cn time, for some small constant c.

References

[1]

Eitan Altman, Rachid El Azouzi, and Tania Jiménez. Slotted aloha as a game with partial information. Computer Networks, 45(6):701--713, 2004.

Digital Library

Google Scholar

[2]

Eitan Altman, Dhiman Barman, Rachid El Azouzi, and Tania Jiménez. A game theoretic approach for delay minimization in slotted aloha.

Google Scholar

[3]

Feigenbaum and Shenker. Distributed algorithmic mechanism design: Recent results and future directions. BEATCS: Bulletin of the European Association for Theoretical Computer Science, 79, 2003.

Google Scholar

[4]

J. Feigenbaum, C. Papadimitriou, R. B. Sami, and S. Shenker. A bgp-based mechanism for lowest-cost routing, 2002.

Digital Library

Google Scholar

[5]

Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria. Lecture Notes in Computer Science, 1563:404--413, 1999.

Digital Library

Google Scholar

[6]

Allen MacKenzie and Stephen B. Wicker. Stability of multipacket slotted aloha with selfish users and perfect information. In INFOCOM, 2003.

Google Scholar

[7]

Martin J. Osborne and Ariel Rubenstein. A Course in Game Theory. The MIT Press, Cambridge, Massachusetts, 1994.

Google Scholar

[8]

Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., New York, NY, USA, 1994.

Digital Library

Google Scholar

[9]

Raphael Rom and Moshe Sidi. Multiple access protocols: performance and analysis. Springer-Verlag New York, Inc., New York, NY, USA, 1990.

Digital Library

Google Scholar

[10]

Tim Roughgarden. Selfish Routing And The Price Of Anarchy. The MIT Press, Cambridge, Massachusetts, 2005.

Digital Library

Google Scholar

Cited By

View all

Chionas GKowalski DKrysta POh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Combinatorial group testing with selfish agentsProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3667571(33352-33364)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3667571
Chionas GChlebus BKowalski DKrysta PElkind E(2023)Adversarial contention resolution gamesProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/289(2598-2606)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/289
Koutsoupias EPapakonstantinopoulou K(2012)Contention issues in congestion gamesProceedings of the 39th international colloquium conference on Automata, Languages, and Programming - Volume Part II10.1007/978-3-642-31585-5_55(623-635)Online publication date: 9-Jul-2012
https://dl.acm.org/doi/10.1007/978-3-642-31585-5_55
Show More Cited By

Efficient contention resolution protocols for selfish agents
1. Theory of computation

Recommendations

Contention Resolution under Selfishness

In many communications settings, such as wired and wireless local-area networks, when multiple users attempt to access a communication channel at the same time, a conflict results and none of the communications are successful. Contention resolution is ...
Contention-based MAC protocols with erasure coding for wireless data networks

Contention-based medium access control (MAC) protocol is a key component for the success of wireless data networks. Conventional random access protocols like ALOHA and Carrier Sense Multiple Access (CSMA) suffer from packet collision which leads to low ...
QoS-Based Adaptive Contention/Reservation Medium Access Control Protocols for Wireless Local Area Networks

In the conventional IEEE 802.11 medium access control protocol, the distributed coordination function is designed for the wireless stations (WSs) to perform channel contention within the wireless local area networks (WLANs). Research work has been ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

January 2007

1322 pages

ISBN:9780898716245

Conference Chair:
Harold Gabow
University of Colorado, Boulder

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 07 January 2007

Check for updates

Qualifiers

Article

Acceptance Rates

SODA '07 Paper Acceptance Rate 139 of 382 submissions, 36%;

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
327
Total Downloads

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

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chionas GKowalski DKrysta POh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Combinatorial group testing with selfish agentsProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3667571(33352-33364)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3667571
Chionas GChlebus BKowalski DKrysta PElkind E(2023)Adversarial contention resolution gamesProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/289(2598-2606)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/289
Koutsoupias EPapakonstantinopoulou K(2012)Contention issues in congestion gamesProceedings of the 39th international colloquium conference on Automata, Languages, and Programming - Volume Part II10.1007/978-3-642-31585-5_55(623-635)Online publication date: 9-Jul-2012
https://dl.acm.org/doi/10.1007/978-3-642-31585-5_55
Christodoulou GLigett KPyrga E(2010)Contention resolution under selfishnessProceedings of the 37th international colloquium conference on Automata, languages and programming: Part II10.5555/1880999.1881046(430-441)Online publication date: 6-Jul-2010
https://dl.acm.org/doi/10.5555/1880999.1881046
Menache IShimkin NBaras J(2008)Reservation-based distributed medium access in wireless collision channelsProceedings of the 3rd International Conference on Performance Evaluation Methodologies and Tools10.4108/ICST.VALUETOOLS2008.4475(1-8)Online publication date: 20-Oct-2008
https://dl.acm.org/doi/10.4108/ICST.VALUETOOLS2008.4475

View Options

Login options

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

Cited By

Recommendations

Contention Resolution under Selfishness

Contention-based MAC protocols with erasure coding for wireless data networks

QoS-Based Adaptive Contention/Reservation Medium Access Control Protocols for Wireless Local Area Networks