Network Games with Atomic Players
<-- Return to the list
Date: 02-28-2006
Start Time:
1:00pm
End Time: 2:00pm
Speaker: José Correa, Universidad Adolfo Ibáñez
Location: Uris 333
Abstract
We study network games with atomic players that can split their flow. Some errors in the literature led to incorrect bounds on the price of anarchy of these games. We correct past results with a new bound for arbitrary sets of cost functions. In the case of affine cost functions, this bound implies that the price of anarchy is at most 3/2 and the cost of an equilibrium is not larger than that of a social optimum of an instance with demands multiplied by 4/3. We also present an improved version of this bound for the case of a single OD pair that depends on the variability of the market power of each of the players. In addition, for the case in which all players share the same OD pair and control the same amount of flow, we provide a new potential function formulation. It implies that the cost of a Nash equilibria is no more than that of the corresponding nonatomic game, ruling out paradoxical phenomena that may arise in the general case. For instance, the cost of an equilibrium increases as the number of players increases as it is more difficult to coordinate players. All our results extend to the more general atomic congestion games with divisible demands, and to mixed atomic and nonatomic games.
Bio
José Rafael Correa graduated as a mathematical engineer from Universidad de Chile in 1999. He wrote his thesis under the supervision of Professor Roberto Cominetti on equilibria in transit networks. In September 2000, José started his Ph.D. in operations research at MIT under the supervision of professors Michel Goemans and Andreas Schulz. After graduating in June 2004, he was a postdoctoral associate in the Department of Computer Science at Universidad de Chile. José later joined the School of Business at Universidad Adolfo Ibáñez as an assistant professor. José's main research interests are in mathematical programming and operations research, in particular in the design and analysis of algorithms for combinatorial problems. He is also interested in the rapidly evolving field that studies the interaction between economics, game theory, and computer science. In particular, the study of equilibria in networks remains one of his primary research areas.