Grid-Computing Algorithms for Large-Scale Stochastic Games
Uday V. Shanbhag
Award year: 2006-2007
The summer of 2000, the state of California saw a sustained period of high electricity prices. An ex-post analysis suggested that a portion of the responsibility could be laid on some electricity companies who strategically withheld generation, at the cost a few billion dollars to the consumers. This proposal is motivated by a need to develop tools to analyze strategic behavior of agents in such large spatially distributed markets, particularly in the face of uncertainty. Other instances of such problems are seen in communication networks, airline networks and traffic engineering networks. A majority of the approaches for simulating the behavior of complex multiple settlement markets use game-theoretic ideas. In almost all practical problems, there is uncertainty in the problem parameters (such as capacity, demand and fuel costs). In such settings, the equilibrium solution needs to be robust to such possibilities and requires solving equilibrium programs under uncertainty. The objectives of the proposal are to (a) develop algorithms for such problems (b) implement them on a grid-computing framework and (c) solve large instances of practical problems efficiently. We focus on two classes of problems: Nash and Nash-Stackelberg equilibrium problems. The former arise in competitive situations where each agent solves a problem, parameterized by the decisions of the remaining agents. A simple example of such a problem is newsvendors selling newspapers, where the price of newspapers is specified by a linear demand function. The equilibrium point is given by a tuple of each vendor's sales decision, such that no agent wants to deviate, given the decisions of all other agents. In many instances, certain agents (Stackelberg leaders) may have more information about other agents (Stackelberg followers). This allows the leaders to make decisions subject to the optimal decisions of the followers and such problems are referred to as Nash-Stackelberg problems. We plan to develop centralized and distributed methods for the problems of interest. Every approach will produce a sequence of iterates that will be theoretically shown to converge to the equilibrium point of interest. The introduction of uncertainty makes the computation of each iterate a cumbersome, if not intractable, task. An important characteristic of the algorithms will be to show how such a computation may be carried out efficiently from a computational and data storage standpoint. A significant part of this proposal is to interact with NCSA to implement these algorithms on a grid-computing framework. Specifically, through a collaboration with the middleware research and development (MRD) group, the algorithms will be implemented using a multi-master multi-worker framework. The parallel approach will allow the solution of large equilibrium problems, that would quite possibly have serial CPU times of a few years. To summarize, this proposal has several important algorithmic and practical purposes. First, it seeks to present scalable convergent methods for solving large equilibrium problems under uncertainty. Second, it plans to extend these methods to a grid-computing architecture to allow for the solution of enormous problems. Third, these algorithms will then be applied to a multi-settlement electricity market under uncertainty.