Files in this item
Files  Description  Format 

application/pdf Kulkarni_Ankur.pdf (2Mb)  (no description provided) 
Description
Title:  Generalized Nash games with shared constraints: Existence, efficiency, refinement and equilibrium constraints 
Author(s):  Kulkarni, Ankur A. 
Director of Research:  Shanbhag, Vinayak V. 
Doctoral Committee Chair(s):  Shanbhag, Vinayak V. 
Doctoral Committee Member(s):  Meyn, Sean P.; Kumar, P. R.; Basar, Tamer; Pang, JongShi 
Department / Program:  Industrial&Enterprise Sys Eng 
Discipline:  Industrial Engineering 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Game theory
Generalized Nash games Shared constraints Refinement of an equilibrium Multileader multifollower games Equilibrium problem with equilibrium constraints Variational inequalities Quasivariational inequalities Efficiency of generalized Nash equilibrium 
Abstract:  The thesis pertains to some fundamental questions in the theory of games. Our focus is on a class of noncooperative N player games, called generalized Nash games with shared constraints, or simply, sharedconstraint games. In such a game, every strategytuple is constrained to lie in a subset C of the product space of strategies. Thus strategies available to a player are only those which when taken jointly with the strategies of all other players, form a tuple that lies in C. The set C is called the shared constraint. Despite their relevance in realworld settings, there are many theoretical properties of these games that are not well understood. What interests us in this thesis is the theoretical character of the equilibria of these games. Sharedconstraint games admit two kinds of equilibria: generalized Nash equilibria (GNE) that are illposed and often intractable and a smaller subset of them (called variational equilibria or VE) satisfying an exogenous regularity condition that are wellposed and surprisingly tractable. We seek to clarify the nature of these equilibria, study their economic implications and exploit their properties to advance the analytical theory for conventional and somewhat unconventional sharedconstraint games. The unconventional sharedconstraint games are in fact a class of dynamic games, called multileader multifollower games, which we view through the lens of shared constraints. Four questions are addressed in this thesis with the central theme as sharedconstraint games. In the first part of the thesis we present a refinement of the GNE. A refinement of an equilibrium is a subset of the set of equilibria which is nonempty whenever the original set of equilibria is nonempty. Refined equilibria are representative of the set of equilibria and have additional properties that make them more attractive as solution concepts than the original equilibria. The contribution of this work is a theory that gives sufficient conditions for a game to admit the VE as a refinement of the GNE. These conditions are expressed in terms of the Brouwer degree, which is seen to relate the GNE and the VE in a profound manner. Importantly, for certain classes of games, these conditions are also seen to be necessary. The degree theoretic relationship holds in both, primal and primaldual space. Our work unifies some previously known results and provides mathematical justification for ideas that were known to be intuitive appealing but were hitherto unsubstantiated formally. The second part of this thesis is about multileader multifollower games. These games are highly nonconvex and irregular and no reliable theory is available for claiming the existence of equilibria of these games. We develop such a theory for multileader multifollower games with shared constraints. The application of standard fixed point arguments to the reaction map of general multileader multifollower games is hindered by the lack of suitable continuity properties, amongst other requirements, in this map. We observe that these games bear a close resemblance to sharedconstraint games and present modifications of the canonical multileader multifollower game that result in sharedconstraint games, with far more favorable properties. Specifically, a global equilibrium of this game exists when a suitably defined modified reaction map admits a fixed point. Sufficient conditions for the existence of these fixed points are obtained via topological fixed point theory. Finally, the paradigm developed is applied to a class of LCPconstrained leader problems where conditions for the contractibility of the domain are derived via the theory of retracts. The third part of thesis concerns the use of variational inequalities for claiming the existence of an equilibrium to sharedconstraint games. The equilibrium conditions of a generalized Nash game can be compactly stated as a quasivariational inequality (QVI), an extension of the variational inequality (VI). Harker showed that under certain conditions on the maps defining the QVI, a solution to a related VI solves the QVI. But the application of Harker’s result to the QVI associated with sharedconstraint games proves difficult because its hypotheses can fail to hold even for simple sharedconstraint games. We show these hypotheses are in fact impossible to satisfy in most settings. But we show that for a modified QVI, whose solution set equals that of the original QVI, the hypothesis of Harker’s result always hold. This paves the way for applying this result to sharedconstraint games, albeit in an indirect manner. This avenue allows us to recover as a special case, a result proved by Facchinei et al., in which it is shown that a suitably defined variational inequality provides a solution to the QVI of a sharedconstraint game. In the fourth part we take a systemlevel view of sharedconstraint games that result from resource allocation. We clarify the relation between this mode of allocating resources and the other conventional modes via either perfect competition or through the use of a mechanism. We find that for perfectly competitive settings the VE is the same as the competitive equilibrium. We then compare the performance of GNE and VE of the sharedconstraint game with respect to the systemlevel objective of maximization of social welfare or aggregate utility. We are specifically interested in the efficiency of an equilibrium, which is the ratio of the aggregate utility for this equilibrium to the optimal aggregate utility, and in the lowest value this efficiency can take for a class of utility functions. We show that for a certain class of utility functions the VEs are fully efficient. We characterize this class and show that departures from this setting can lead to arbitrarily low efficiency in the worst case. Specifically, in this class, even while the VEs are efficient, GNEs can be arbitrarily inefficient, and VEs of games not belonging to the ‘efficient’ class can have arbitrarily low efficiency in the worst case. Finally we suggest ways to remedy the low efficiency of equilibria in these cases. We find that a more restricted class of utility functions, in which the gradient map of every member utility function is bounded away from zero and from above uniformly over the domain, gives a more favorable worst case efficiency. We then consider a game where players incur costs that, from the system point of view are not additive, whereby the system problem is not merely the sum of the objectives of all players. We characterize utility functions for which the VE is efficient under this notion of efficiency. Finally we consider the imposition of a reserve price on players. The reserve price has the effect of eliminating players with low interest in the resource. The GNE is more indicative of the system optimal. We find that under certain conditions, efficiency as high as unity is obtainable by the imposition of an appropriate reserve price. 
Issue Date:  20110114 
URI:  http://hdl.handle.net/2142/18469 
Rights Information:  Copyright 2o1o Ankur A. Kulkarni 
Date Available in IDEALS:  20110114 
Date Deposited:  December 2 
This item appears in the following Collection(s)

Dissertations and Theses  Industrial and Enterprise Systems Engineering

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois
Item Statistics
 Total Downloads: 601
 Downloads this Month: 6
 Downloads Today: 0