Pricing in Network Games using Supply Functions
Dr. Nicolas Stier
February 12, 2009
Troy 2012, 4:00 p.m. to 5:00 p.m.
Refreshments at 3:30 p.m.
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
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.
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
Hosted by: Dr. Elliot Anshelevich (x6491)
Last updated: January 2, 2009