On Nash equilibria for multicast transmissions in ad-hoc wireless networks |
| |
Authors: | Vittorio Bilò Michele Flammini Giovanna Melideo Luca Moscardelli |
| |
Affiliation: | (1) Dipartimento di Matematica “Ennio De Giorgi”, Università di Lecce, Provinciale Lecce-Arnesano, P.O. Box 193, 73100 Lecce, Italy;(2) Dipartimento di Informatica, Università di L’Aquila, Via Vetoio, Coppito, 67100, L’Aquila, Italy |
| |
Abstract: | We study a multicast game in ad-hoc wireless networks in which a source sends the same message or service to a set of receiving
stations via multi-hop communications and the overall transmission cost is divided among the receivers according to given
cost sharing methods. We assume that each receiver gets a certain utility from the transmission and enjoys a benefit equal
to the difference between his utility and the shared cost he is asked to pay. Assuming a selfish and rational behavior, each
user is willing to receive the transmission if and only if his shared cost does not exceed his utility. Moreover, given the
strategies of the other users, he wants to select a strategy of minimum shared cost. A Nash equilibrium is a solution in which
no user can increase his benefit by choosing to adopt a different strategy. We consider the following reasonable cost sharing
methods: egalitarian, semi-egalitarian next-hop-proportional, path-proportional, egalitarian-path-proportional and Shapley
value. We prove that, while the first five cost sharing methods in general do not admit a Nash equilibrium, the Shapley value
yields games always converging to a Nash equilibrium. We then turn our attention to the special case in which the receivers’
set R is part of the input (that is only the stations belonging to R have a positive utility which is set equal to infinity) and show that in such a case also the egalitarian and the egalitarian-path-proportional
methods yield convergent games. In such a framework, we show that the price of anarchy is unbounded for the game yielded by
the egalitarian method and provide matching upper and lower bounds for the price of anarchy of the other two convergent games
with respect to two different global cost functions, that is the overall cost of the power assignment, that coincides with
the sum of all the shared costs, and the maximum shared cost paid by the receivers. Finally, in all cases we show that finding
the best Nash equilibrium is computationally intractable, that is NP-hard.
Vittorio Bilò received the degree in Computer Science and the Ph.D. degree in Computer Science at the University of L’Aquila in 2001 and
2005 respectively. He is currently an assistant professor at the Department of Mathematics “Ennio De Giorgi” of the University
of Lecce. His research interests include algorithms and computational complexity, communication problems in interconnection
networks and game theoretical issues in non-cooperative networks.
Michele Flammini received the degree in Computer Science at the University of L’Aquila in 1990 and the Ph.D. degree in Computer Science at
the University of Rome “La Sapienza” in 1995. He is full professor at the Computer Science Department of the University of
L’Aquila since March 2005. His research interests include algorithms and computational complexity, game theory, communication
problems in interconnection networks and routing. He has authored and co-authored more than 70 papers in his fields of interest
published in the most reputed international conferences and journals.
Giovanna Melideo received the Laurea degree in computer science in 1997 from the University of L’Aquila (Italy) and the Ph.D. degree in computer
engineering in 2001 from the University of Rome “La Sapienza”. From November 1999 to February 2000 she was visitor at IRISA/INRIA,
University of Rennes 1, Rennes (France) in the ADP group. She was research fellow from June to October 2001 at the University
of L’Aquila, where she is currently an assistant professor in the Computer Science Department. Her research interests include
algorithms and complexity, algorithmic game theory, wireless networks, models for information integration and cooperative
information systems, certification and security in e-service, distributed protocols and dependability. She has been a member
of the scientific and organizing committee of the IFIP international workshop on Certification and Security in E-Services
(CSES 2002), Montreal, Canada.
Luca Moscardelli received the degree in Computer Science at the University of L’Aquila in 2004. He is currently a Ph.D. student in Computer
Science at the University of L’Aquila. His current research interests include optimization problems in social and communication
networks, and the analysis of the interaction between selfish agents in non-cooperative networks. |
| |
Keywords: | Energy saving Cost sharing methods Nash equilibria Price of anarchy |
本文献已被 SpringerLink 等数据库收录! |
|