News

Colloquia

Pricing in Network Games using Supply Functions

Dr. Nicolas Stier
Columbia University

February 12, 2009
Troy 2012, 4:00 p.m. to 5:00 p.m.
Refreshments at 3:30 p.m.

Abstract:

One of the first problems studied in the area of Algorithmic Game Theory has been to determine the inefficiency that arises from selfish behavior in network games. In these games, arcs have cost functions defined a-priori and players have to choose paths in the network whose costs depend on the choices of other players. Some common applications can be found in telecommunication, transportation and logistic networks. From the perspective of the system, one would like that players coordinate themselves to maximize the global welfare but, in most cases, players are oblivious to this and only pay attention to their own welfare. The mismatch between the global and personal objectives leads the system to operate in a suboptimal regime. For this reason, this stream of research focused on quantifying the inefficiency introduced by selfish behavior and determined that, under some assumptions, the operating regime---represented by an equilibrium---cannot be more than 33% worse than optimal. In this talk, I will review some of these results and then introduce a model that endogenizes the selection of cost functions, which were previously considered exogenous and fixed. As opposed to traditional network games, the owners of arcs choose how much to charge to users interested in selecting them. Owners do this by determining the supply function that maximizes their own profits. Users learn these functions and compete for paths as in a traditional network game. This type of model and their solutions have been called supply function equilibria and have immediate application to electricity markets. Indeed, a mechanism of this type is used daily to decide how much electricity each generator is going to produce to inject to the grid. I will present necessary and sufficient conditions for the existence of equilibria in the space of supply functions, which can be used to show that charges at equilibrium equal the cost of providing service plus a multiplicative markup. Finally, I will analyze the inefficiency introduced by competition and the distortion of costs that it generates.

Bio:

Nicolas Stier-Moses is an Associate Professor at the Decision, Risk and Operations Division of Columbia Business School. He received a Ph.D. degree from the Operations Research Center of the Massachusetts Institute of Technology. Nicolas' research focuses on the study of the impact that self-minded agents have on decentralized systems. In particular, his goal is exploring mechanisms that can help coordinate agents, either by design or by offering the correct incentives.

Hosted by: Dr. Elliot Anshelevich (x6491)

Last updated: January 2, 2009