Efficient contention resolution protocols for selfish agents

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 , Tania Jiménez, Slotted Aloha as a game with partial information, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.45 n.6, p.701-713, 21 August 2004 [doi>10.1016/j.comnet.2004.02.013]
• 2: Eitan Altman, Dhiman Barman, Rachid El Azouzi, and Tania Jiménez. A game theoretic approach for delay minimization in slotted aloha.
• 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.
• 4: Joan Feigenbaum , Christos Papadimitriou , Rahul Sami , Scott Shenker, A BGP-based mechanism for lowest-cost routing, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571856]
• 5: Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria. Lecture Notes in Computer Science, 1563:404--413, 1999.
• 6: Allen MacKenzie and Stephen B. Wicker. Stability of multipacket slotted aloha with selfish users and perfect information. In INFOCOM, 2003.
• 7: Martin J. Osborne and Ariel Rubenstein. A Course in Game Theory. The MIT Press, Cambridge, Massachusetts, 1994.
• 8: Martin L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, John Wiley & Sons, Inc., New York, NY, 1994
• 9: Raphael Rom , Moshe Sidi, Multiple access protocols: performance and analysis, Springer-Verlag New York, Inc., New York, NY, 1990
• 10: Tim Roughgarden, Selfish Routing and the Price of Anarchy, The MIT Press, 2005