skip to main content
article

The analysis of Nash equilibria of the one-shot random-access game for wireless networks and the behavior of selfish nodes

Published: 01 October 2008 Publication History

Abstract

We address the fundamental question of whether or not there exist stable operating points in a network in which selfish nodes share a common channel, and if they exist, how the nodes behave at these stable operating points. We begin with a wireless communication network in which n nodes (agents), which might have different utility functions, contend for access on a common, wireless communication channel. We characterize this distributed multiple-access problem in terms of a one-shot random-access game, and then analyze the behavior of the nodes using the tools of game theory. We give necessary and sufficient conditions on nodes for the complete characterization of the Nash equilibria of this game for all n ≥ 2. We show that all centrally controlled optimal solutions are a subset of this game theoretic solution, and almost all (w.r.t. Lebesgue measure) transmission probability assignments chosen by a central authority are supported by the game theoretic solution. We analyze the behavior of the network throughput at Nash equilibria as a function of the costs of the transmitters incurred by failed transmissions. Finally, we conclude the paper with the asymptotic analysis of the system as the number of transmitters goes to infinity. We show that the asymptotic distribution of the packet arrivals converges in distribution to a Poisson random variable, and the channel throughput converges to - (c/ (1 + c)) In (c/ (1 + c)) with c > 0 being the cost of failed transmissions. We also give the best possible bounds on the rates of convergence of the packet arrival distribution and the channel throughput.

References

[1]
P. Gupta and P. R. Kumar, "The capacity of wireless networks," IEEE Trans. Inf. Theory, vol. 46, no. 2, pp. 388-404, Mar. 2000.
[2]
M. Grossglauser and D. Tse, "Mobility increases the capacity of wireless ad hoc networks," IEEE/ACM Trans. Netw., vol. 10, no. 4, pp. 477-486, Aug. 2002.
[3]
J. Eriksson, M. Faloutsos, and S. Krishnamurthy, "Scalable ad hoc routing: The case of dynamic addressing," in Proc. IEEE INFOCOM, Hong Kong, Mar. 2004, pp. 1108-1119.
[4]
X. Hong, K. Xu, and M. Gerla, "Scalable routing protocols for mobile ad hoc networks," IEEE Netw. Mag., vol. 16, no. 4, Jul.-Aug. 2002.
[5]
A. B. MacKenzie and L. A. DaSilva, Game Theory for Wireless Engineers . San Rafael, CA: Morgan and Claypool, 2006.
[6]
L. Kleinrock and J. A. Silvester, "Optimal transmission radii in packet radio networks or why six is a magic number," in Proc. Nat. Telecommun. Conf., Birmingham, AL, Dec. 1978.
[7]
H. Takagi and L. Kleinrock, "Optimal transmission ranges for randomly distributed packet radio terminals," IEEE Trans. Commun., vol. COM-32, no. 3, Mar. 1984.
[8]
T. C. Hou and V. O. K. Li, "Transmission range control in multi-hop packet radio networks," IEEE Trans. Commun., vol. COM-34, no. 1, Jan. 1986.
[9]
C. U. Saraydar, N. B. Mandayam, and D. J. Goodman, "Pricing and power control in a multicell wireless data network," IEEE J. Sel. Areas Commun., vol. 19, no. 10, pp. 1883-1892, Oct. 2001.
[10]
M. Cagalj, S. Ganeriwal, I. Aad, and J. P. Hubaux, "On selfish behavior in CSMA/CA networks," in Proc. IEEE INFOCOM, Mar. 2005, pp. 2513-2524.
[11]
A. B. MacKenzie and S. B. Wicker, "Stability of multipacket slotted Aloha with selfish users and perfect information," in Proc. IEEE INFOCOM , 2003, pp. 1583-1590.
[12]
E. Altman, R. El Azouzi, and T. Jimenez, "Slotted Aloha as a stochastic game with partial information," in WiOpt'03, Mar. 2003.
[13]
H. Inaltekin and S. Wicker, "A one shot random access game for wireless networks," in Symp. Information Theory in Wirelesscom., 2005.
[14]
T. C. Schelling, The Strategy of Conflict. Cambridge, MA: Harvard Univ. Press, 1960.
[15]
H. Inaltekin, "Topics on wireless network design: Game theoretic MAC protocol design and interference analysis for wireless networks," Ph.D. dissertation, Cornell Univ., Ithaca, NY, Aug. 2006.
[16]
H. Inaltekin and S. B. Wicker, "The analysis of a game theoretic MAC protocol for wireless networks," in Proc. IEEE Secon'06.
[17]
R. B. Myerson, Game Theory, Analysis of Conflict. Cambridge, MA: Harvard Univ. Press, 1997.
[18]
D. Fudenberg and J. Tirole, Game Theory. Cambridge, MA: MIT Press, 1991.
[19]
P. Billingsley, Probability and Measure. Hoboken, NJ: Wiley, 1995.
[20]
J. Nash, "Equilibruim points in n-person games," in Proc. Nat. Acad. Sci., 1950, vol. 36, no. 1.
[21]
R. Durrett, Probability: Theory and Examples, 2nd ed. Duxbury Press, MA: Duxbury, 1996.
[22]
W. Rudin, Principles of Mathematical Analysis. New York: Mc-Graw-Hill, 1976.

Cited By

View all

Index Terms

  1. The analysis of Nash equilibria of the one-shot random-access game for wireless networks and the behavior of selfish nodes

                        Recommendations

                        Comments

                        Information & Contributors

                        Information

                        Published In

                        cover image IEEE/ACM Transactions on Networking
                        IEEE/ACM Transactions on Networking  Volume 16, Issue 5
                        October 2008
                        238 pages

                        Publisher

                        IEEE Press

                        Publication History

                        Published: 01 October 2008
                        Revised: 04 April 2007
                        Received: 11 November 2005
                        Published in TON Volume 16, Issue 5

                        Author Tags

                        1. Nash equilibrium
                        2. channel throughput
                        3. game theory
                        4. random access control
                        5. slotted ALOHA

                        Qualifiers

                        • Article

                        Contributors

                        Other Metrics

                        Bibliometrics & Citations

                        Bibliometrics

                        Article Metrics

                        • Downloads (Last 12 months)1
                        • Downloads (Last 6 weeks)0
                        Reflects downloads up to 14 Feb 2025

                        Other Metrics

                        Citations

                        Cited By

                        View all
                        • (2022)A Multiple Access Game with Incomplete InformationAutomation and Remote Control10.1134/S000511792209009083:9(1467-1475)Online publication date: 1-Sep-2022
                        • (2019)TCGMACTransactions on Emerging Telecommunications Technologies10.1002/ett.373030:12Online publication date: 10-Dec-2019
                        • (2018)Selfish Users in Graph-Based Random Access2018 IEEE 29th Annual International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC)10.1109/PIMRC.2018.8580831(1960-1966)Online publication date: 9-Sep-2018
                        • (2016)Exploiting Social Tie Structure for Cooperative Wireless NetworkingIEEE/ACM Transactions on Networking10.1109/TNET.2016.253007024:6(3593-3606)Online publication date: 1-Dec-2016
                        • (2016)Distributed game-theoretic optimization and management of multichannel ALOHA networksIEEE/ACM Transactions on Networking10.1109/TNET.2015.243112124:3(1718-1731)Online publication date: 1-Jun-2016
                        • (2016)Thwarting selfish behavior in 802.11 WLANsIEEE/ACM Transactions on Networking10.1109/TNET.2014.236953524:1(492-505)Online publication date: 1-Feb-2016
                        • (2016)Mixed scheduling with heterogeneous delay constraints in cyber-physical systemsFuture Generation Computer Systems10.1016/j.future.2015.10.02161:C(108-117)Online publication date: 1-Aug-2016
                        • (2014)A survey of QoS/QoE mechanisms in heterogeneous wireless networksPhysical Communication10.1016/j.phycom.2014.04.00913:PB(61-72)Online publication date: 1-Dec-2014
                        • (2010)Optimal SINR-based random accessProceedings of the 29th conference on Information communications10.5555/1833515.1833827(2384-2392)Online publication date: 14-Mar-2010
                        • (2010)Random access game and medium access control designIEEE/ACM Transactions on Networking10.1109/TNET.2010.204106618:4(1303-1316)Online publication date: 1-Aug-2010
                        • Show More Cited By

                        View Options

                        Login options

                        Full Access

                        View options

                        PDF

                        View or Download as a PDF file.

                        PDF

                        eReader

                        View online with eReader.

                        eReader

                        Figures

                        Tables

                        Media

                        Share

                        Share

                        Share this Publication link

                        Share on social media