Generalized Nash games with shared constraints: Existence, efficiency, refinement and equilibrium 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 [MWG95] of the generalized Nash equilibria (GNE). 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.;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 [Har91] 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.;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 [MWG95] 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.;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. (Abstract shortened by UMI.)