On generalized Nash equilibrium problems with linear coupling constraints and mixed-integer variables

ABSTRACT

We define and discuss different enumerative methods to compute solutions of generalized Nash equilibrium problems with linear coupling constraints and mixed-integer variables. We propose both branch-and-bound methods based on merit functions for the mixed-integer game, and branch-and-prune methods that exploit the concept of dominance to make effective cuts. We show that under mild assumptions the equilibrium set of the game is finite and we define an enumerative method to compute the whole of it. We show that our branch-and-prune method can be suitably modified in order to make a general equilibrium selection over the solution set of the mixed-integer game. We define an application in economics that can be modelled as a Nash game with linear coupling constraints and mixed-integer variables, and we adapt the branch-and-prune method to efficiently solve it.     

Computing equilibria of Cournot oligopoly models with mixed-integer quantities

We consider Cournot oligopoly models in which some variables represent indivisible quantities. These models can be addressed by computing equilibria of Nash equilibrium problems in which the players solve mixed-integer nonlinear problems. In the literature there are no methods to compute equilibria of this type of Nash games. We propose a Jacobi-type method for computing solutions of Nash equilibrium problems with mixed-integer variables. This algorithm is a generalization of a recently proposed method for the solution of discrete so-called “2-groups partitionable” Nash equilibrium problems. We prove that our algorithm converges in a finite number of iterations to approximate equilibria under reasonable conditions. Moreover, we give conditions for the existence of approximate equilibria. Finally, we give numerical results to show the effectiveness of the proposed method.     

Robust Multiple Objective Game Theory

In this paper, we propose a distribution-free model instead of considering a particular distribution for multiple objective games with incomplete information. We assume that each player does not know the exact value of the uncertain payoff parameters, but only knows that they belong to an uncertainty set. In our model, the players use a robust optimization approach for each of their objective to contend with payoff uncertainty. To formulate such a game, named “robust multiple objective games” here, we introduce three kinds of robust equilibrium under different preference structures. Then, by using a scalarization method and an existing result on the solutions for the generalized quasi-vector equilibrium problems, we obtain the existence of these robust equilibria. Finally, we give an example to illustrate our model and the existence theorems. Our results are new and fill the gap in the game theory literature.     

Computing payoff allocations in the approximate core of linear programming games in a privacy-preserving manner

We investigate privacy-preserving ways of allocating payoffs among players participating in a joint venture, using tools from cooperative game theory and differential privacy. In particular, we examine linear programming games, an important class of cooperative games that model a myriad of payoff sharing problems, including those from logistics and network design. We show that we can compute a payoff allocation in the approximate core of these games in a way that satisfies joint differential privacy.     

A Bridge Between Bilevel Programs and Nash Games

We study connections between optimistic bilevel programming problems and generalized Nash equilibrium problems. We remark that, with respect to bilevel problems, we consider the general case in which the lower level program is not assumed to have a unique solution. Inspired by the optimal value approach, we propose a Nash game that, transforming the so-called implicit value function constraint into an explicitly defined constraint function, incorporates some taste of hierarchy and turns out to be related to the bilevel programming problem. We provide a complete theoretical analysis of the relationship between the vertical bilevel problem and our “uneven” horizontal model: in particular, we define classes of problems for which solutions of the bilevel program can be computed by finding equilibria of our game. Furthermore, by referring to some applications in economics, we show that our “uneven” horizontal model, in some sense, lies between the vertical bilevel model and a “pure” horizontal game.     

Useful New Equilibria for Differential Games with Side Interests of the Participants

For conflict static and dynamic problems (described by differential equations) considered either on a game set common for all participants or on partly intersecting game sets, we propose new notions of conflict equilibria which are efficient for seeking the solutions of coalition-free and cooperative games and for specifying the hierarchy of all known equilibria. Several examples are used to show that, without the proposed new notions of equilibrium, an actually fair sharing may be impossible in cooperative games.     

Separable and low-rank continuous games

In this paper, we study nonzero-sum separable games, which are continuous games whose payoffs take a sum-of-products form. Included in this subclass are all finite games and polynomial games. We investigate the structure of equilibria in separable games. We show that these games admit finitely supported Nash equilibria. Motivated by the bounds on the supports of mixed equilibria in two-player finite games in terms of the ranks of the payoff matrices, we define the notion of the rank of an n-player continuous game and use this to provide bounds on the cardinality of the support of equilibrium strategies. We present a general characterization theorem that states that a continuous game has finite rank if and only if it is separable. Using our rank results, we present an efficient algorithm for computing approximate equilibria of two-player separable games with fixed strategy spaces in time polynomial in the rank of the game. This research was funded in part by National Science Foundation grants DMI-0545910 and ECCS-0621922 and AFOSR MURI subaward 2003-07688-1.     

How to Select a Solution in Generalized Nash Equilibrium Problems

We propose a new solution concept for generalized Nash equilibrium problems. This concept leads, under suitable assumptions, to unique solutions, which are generalized Nash equilibria and the result of a mathematical procedure modeling the process of finding a compromise. We first compute the favorite strategy for each player, if he could dictate the game, and use the best response on the others’ favorite strategies as starting point. Then, we perform a tracing procedure, where we solve parametrized generalized Nash equilibrium problems, in which the players reduce the weight on the best possible and increase the weight on the current strategies of the others. Finally, we define the limiting points of this tracing procedure as solutions. Under our assumptions, the new concept selects one reasonable out of typically infinitely many generalized Nash equilibria.     

Equilibrium programming using proximal-like algorithms

We compute constrained equilibria satisfying an optimality condition. Important examples include convex programming, saddle problems, noncooperative games, and variational inequalities. Under a monotonicity hypothesis we show that equilibrium solutions can be found via iterative convex minimization. In the main algorithm each stage of computation requires two proximal steps, possibly using Bregman functions. One step serves to predict the next point; the other helps to correct the new prediction. To enhance practical applicability we tolerate numerical errors. Research supported partly by the Norwegian Research Council, project: Quantec 111039/401.     

COMPUTING THE EQUILIBRIA OF DYNAMIC COMMON PROPERTY GAMES

In this paper we discuss techniques for rapidly computing the equilibria of a class of dynamic linear-quadratic games involving the extraction of a common property resource. Though this class of games has been much studied, the search for equilibria of these games has only been attempted in special cases, and analysis of the game has tended to focus on its steady-state properties. We construct a pseudo-planning problem, the optimal of which correspond to the Markov perfect equilibria of the class of games we explore. We show how the optima (equilibria) of this pseudo-planning problem (game) can be rapidly computed via a Riccati-like equation. Finally, we illustrate the use of these techniques with several examples involving the extraction of a common property resource.     

GOSAC: global optimization with surrogate approximation of constraints

We introduce GOSAC, a global optimization algorithm for problems with computationally expensive black-box constraints and computationally cheap objective functions. The variables may be continuous, integer, or mixed-integer. GOSAC uses a two-phase optimization approach. The first phase aims at finding a feasible point by solving a multi-objective optimization problem in which the constraints are minimized simultaneously. The second phase aims at improving the feasible solution. In both phases, we use cubic radial basis function surrogate models to approximate the computationally expensive constraints. We iteratively select sample points by minimizing the computationally cheap objective function subject to the constraint function approximations. We assess GOSAC’s efficiency on computationally cheap test problems with integer, mixed-integer, and continuous variables and two environmental applications. We compare GOSAC to NOMAD and a genetic algorithm (GA). The results of the numerical experiments show that for a given budget of allowed expensive constraint evaluations, GOSAC finds better feasible solutions more efficiently than NOMAD and GA for most benchmark problems and both applications. GOSAC finds feasible solutions with a higher probability than NOMAD and GOSAC.     

Computation of equilibria and the price of anarchy in bottleneck congestion games

We study Nash and strong equilibria in weighted and unweighted bottleneck games. In such a game every (weighted) player chooses a subset of a given set of resources as her strategy. The cost of a resource depends on the total weight of players choosing it and the personal cost every player tries to minimize is the cost of the most expensive resource in her strategy, the bottleneck value. To derive efficient algorithms for finding equilibria in unweighted games, we generalize a transformation of a bottleneck game into a congestion game with exponential cost functions introduced by Caragiannis et al. (2005). For weighted routing games we show that Greedy methods give Nash equilibria in extension-parallel and series-parallel graphs. Furthermore, we show that the strong Price of Anarchy can be arbitrarily high for special cases and give tight bounds depending on the topology of the graph, the number and weights of the users and the degree of the polynomial latency functions. Additionally we investigate the existence of equilibria in generalized bottleneck games, where players aim to minimize not only the bottleneck value, but also the second most expensive resource in their strategy and so on.     

Equilibrium strategies for multiple interdictors on a common network

In this work, we introduce multi-interdictor games, which model interactions among multiple interdictors with differing objectives operating on a common network. As a starting point, we focus on shortest path multi-interdictor (SPMI) games, where multiple interdictors try to increase the shortest path lengths of their own adversaries attempting to traverse a common network. We first establish results regarding the existence of equilibria for SPMI games under both discrete and continuous interdiction strategies. To compute such an equilibrium, we present a reformulation of the SPMI game, which leads to a generalized Nash equilibrium problem (GNEP) with non-shared constraints. While such a problem is computationally challenging in general, we show that under continuous interdiction actions, an SPMI game can be formulated as a linear complementarity problem and solved by Lemke’s algorithm. In addition, we present decentralized heuristic algorithms based on best response dynamics for games under both continuous and discrete interdiction strategies. Finally, we establish theoretical lower bounds on the worst-case efficiency loss of equilibria in SPMI games, with such loss caused by the lack of coordination among noncooperative interdictors, and use the decentralized algorithms to numerically study the average-case efficiency loss.     

Optimal strategic reasoning with McNaughton functions

The aim of the paper is to explore strategic reasoning in strategic games of two players with an uncountably infinite space of strategies the payoff of which is given by McNaughton functions—functions on the unit interval which are piecewise linear with integer coefficients. McNaughton functions are of a special interest for approximate reasoning as they correspond to formulas of infinitely valued Lukasiewicz logic. The paper is focused on existence and structure of Nash equilibria and algorithms for their computation. Although the existence of mixed strategy equilibria follows from a general theorem (Glicksberg, 1952) [5], nothing is known about their structure neither the theorem provides any method for computing them. The central problem of the article is to characterize the class of strategic games with McNaughton payoffs which have a finitely supported Nash equilibrium. We give a sufficient condition for finite equilibria and we propose an algorithm for recovering the corresponding equilibrium strategies. Our result easily generalizes to n-player strategic games which don't need to be strictly competitive with a payoff functions represented by piecewise linear functions with real coefficients. Our conjecture is that every game with McNaughton payoff allows for finitely supported equilibrium strategies, however we leave proving/disproving of this conjecture for future investigations.     

Nondominated Nash points: application of biobjective mixed integer programming

We study the connection between biobjective mixed integer linear programming and normal form games with two players. We first investigate computing Nash equilibria of normal form games with two players using single-objective mixed integer linear programming. Then, we define the concept of efficient (Pareto optimal) Nash equilibria. This concept is precisely equivalent to the concept of efficient solutions in multi-objective optimization, where the solutions are Nash equilibria. We prove that the set of all points in the payoff (or objective) space of a normal form game with two players corresponding to the utilities of players in an efficient Nash equilibrium, the so-called nondominated Nash points, is finite. We demonstrate that biobjective mixed integer linear programming, where the utility of each player is an objective function, can be used to compute the set of nondominated Nash points. Finally, we illustrate how the nondominated Nash points can be used to determine the disagreement point of a bargaining problem.     

The solution of evolutionary games using the theory of Hamilton-Jacobi equations

A dynamical model of a non-antagonistic evolutionary game for two coalitions is considered. The model features an infinite time span and discounted payoff functionals. A solution is presented using differential game theory. The solution is based on the construction of a value function for auxiliary antagonistic differential games and uses an approximate grid scheme from the theory of generalized solutions of the Hamilton-Jacobi equations. Together with the value functions the optimal guaranteeing procedures for control on the grid are computed and the Nash dynamic equilibrium is constructed. The behaviour of trajectories generated by the guaranteeing controls is investigated. Examples are given.     

A Globally Convergent Algorithm to Compute All Nash Equilibria for <Emphasis Type="Italic">n</Emphasis>-Person Games

In this paper we present an algorithm to compute all Nash equilibria for generic finite n-person games in normal form. The algorithm relies on decomposing the game by means of support-sets. For each support-set, the set of totally mixed equilibria of the support-restricted game can be characterized by a system of polynomial equations and inequalities. By finding all the solutions to those systems, all equilibria are found. The algorithm belongs to the class of homotopy-methods and can be easily implemented. Finally, several techniques to speed up computations are proposed.     

Stochastic programming problems with generalized integrated chance constraints

If the constraints in an optimization problem are dependent on a random parameter, we would like to ensure that they are fulfilled with a high level of reliability. The most natural way is to employ chance constraints. However, the resulting problem is very hard to solve. We propose an alternative formulation of stochastic programs using penalty functions. The expectations of penalties can be left as constraints leading to generalized integrated chance constraints, or incorporated into the objective as a penalty term. We show that the penalty problems are asymptotically equivalent under quite mild conditions. We discuss applications of sample-approximation techniques to the problems with generalized integrated chance constraints and propose rates of convergence for the set of feasible solutions. We will direct our attention to the case when the set of feasible solutions is finite, which can appear in integer programming. The results are then extended to the bounded sets with continuous variables. Additional binary variables are necessary to solve sample-approximated chance-constrained problems, leading to a large mixed-integer non-linear program. On the other hand, the problems with penalties can be solved without adding binary variables; just continuous variables are necessary to model the penalties. The introduced approaches are applied to the blending problem leading to comparably reliable solutions.     

Robust game theory

We present a distribution-free model of incomplete-information games, both with and without private information, in which the players use a robust optimization approach to contend with payoff uncertainty. Our ``robust game' model relaxes the assumptions of Harsanyi's Bayesian game model, and provides an alternative distribution-free equilibrium concept, which we call ``robust-optimization equilibrium,' to that of the ex post equilibrium. We prove that the robust-optimization equilibria of an incomplete-information game subsume the ex post equilibria of the game and are, unlike the latter, guaranteed to exist when the game is finite and has bounded payoff uncertainty set. For arbitrary robust finite games with bounded polyhedral payoff uncertainty sets, we show that we can compute a robust-optimization equilibrium by methods analogous to those for identifying a Nash equilibrium of a finite game with complete information. In addition, we present computational results. The research of the author was partially supported by a National Science Foundation Graduate Research Fellowship and by the Singapore-MIT Alliance. The research of the author was partially supported by the Singapore-MIT Alliance.     

On the solution of affine generalized Nash equilibrium problems with shared constraints by Lemke’s method

Affine generalized Nash equilibrium problems (AGNEPs) represent a class of non-cooperative games in which players solve convex quadratic programs with a set of (linear) constraints that couple the players’ variables. The generalized Nash equilibria (GNE) associated with such games are given by solutions to a linear complementarity problem (LCP). This paper treats a large subclass of AGNEPs wherein the coupled constraints are shared by, i.e., common to, the players. Specifically, we present several avenues for computing structurally different GNE based on varying consistency requirements on the Lagrange multipliers associated with the shared constraints. Traditionally, variational equilibria (VE) have been amongst the more well-studied GNE and are characterized by a requirement that the shared constraint multipliers be identical across players. We present and analyze a modification to Lemke’s method that allows us to compute GNE that are not necessarily VE. If successful, the modified method computes a partial variational equilibrium characterized by the property that some shared constraints are imposed to have common multipliers across the players while other are not so imposed. Trajectories arising from regularizing the LCP formulations of AGNEPs are shown to converge to a particular type of GNE more general than Rosen’s normalized equilibrium that in turn includes a variational equilibrium as a special case. A third avenue for constructing alternate GNE arises from employing a novel constraint reformulation and parameterization technique. The associated parametric solution method is capable of identifying continuous manifolds of equilibria. Numerical results suggest that the modified Lemke’s method is more robust than the standard version of the method and entails only a modest increase in computational effort on the problems tested. Finally, we show that the conditions for applying the modified Lemke’s scheme are readily satisfied in a breadth of application problems drawn from communication networks, environmental pollution games, and power markets.