Generalized Nash games with shared constraints: Existence, efficiency, refinement and equilibrium constraints

Kulkarni, Ankur A.

Permalink

https://hdl.handle.net/2142/18469 Copy

Description

Title

Generalized Nash games with shared constraints: Existence, efficiency, refinement and equilibrium constraints

Author(s)

Kulkarni, Ankur A.

Issue Date

2011-01-14T22:51:51Z

Director of Research (if dissertation) or Advisor (if thesis)

Shanbhag, Vinayak V.

Doctoral Committee Chair(s)

Shanbhag, Vinayak V.

Committee Member(s)

• Meyn, Sean P.
• Kumar, P.R.
• Basar, Tamer
• Pang, Jong-Shi

Department of Study

Industrial&Enterprise Sys Eng

Discipline

Industrial Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Game theory
• Generalized Nash games
• Shared constraints
• Refinement of an equilibrium
• Multi-leader multi-follower games
• Equilibrium problem with equilibrium constraints
• Variational inequalities
• Quasi-variational 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, shared-constraint games. In such a game, every strategy-tuple 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 real-world 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. Shared-constraint games admit two kinds of equilibria: generalized Nash equilibria (GNE) that are ill-posed and often intractable and a smaller subset of them (called variational equilibria or VE) satisfying an exogenous regularity condition that are well-posed 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 shared-constraint games. The unconventional shared-constraint games are in fact a class of dynamic games, called multi-leader multi-follower games, which we view through the lens of shared constraints. Four questions are addressed in this thesis with the central theme as shared-constraint 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 primal-dual 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 multi-leader multi-follower 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 multi-leader multi-follower games with shared constraints. The application of standard fixed point arguments to the reaction map of general multi-leader multi-follower 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 shared-constraint games and present modifications of the canonical multi-leader multi-follower game that result in shared-constraint 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 LCP-constrained 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 shared-constraint games. The equilibrium conditions of a generalized Nash game can be compactly stated as a quasi-variational 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 shared-constraint games proves difficult because its hypotheses can fail to hold even for simple shared-constraint 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 shared-constraint 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 shared-constraint game. In the fourth part we take a system-level view of shared-constraint 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 shared-constraint game with respect to the system-level 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.

Graduation Semester

2010-12

Permalink

http://hdl.handle.net/2142/18469

Copyright and License Information

Copyright 2o1o Ankur A. Kulkarni

Owning Collections