## Invited Session Fri.2.H 3027

#### Friday, 13:15 - 14:45 h, Room: H 3027

**Cluster 7: Finance & economics** [...]

### Generalized nash equilibrium problems

**Chair: Kenneth Judd**

**Friday, 13:15 - 13:40 h, Room: H 3027, Talk 1**

**Philipp Johannes Renner**

Computing generalized Nash equilibria by polynomial programming

**Coauthor: Eleftherios Couzoudis**

**Abstract:**

We present a new way to solve generalized Nash equilibrium problems. We assume the feasible set to be closed and compact. Furthermore all functions are assumed to be rational. However we do not need any convexity assumptions on either the utility functions or the action sets. The key idea is to use Putinar's Positivstellensatz, a representation result for positive polynomials. We obtain a system of polynomial equations and inequalities. The solutions to this are all within epsilon to be optimal. In many situations epsilon is zero.

**Friday, 13:45 - 14:10 h, Room: H 3027, Talk 2**

**Frits Spieksma**

Testing rationality: algorithms and complexity

**Coauthor: Bart Smeulders**

**Abstract:**

Micro-economic theory offers non-parametric tests that show whether observed data are consistent with a model of utility maximization. For instance, it is well-known that, given a dataset, it can be efficiently tested whether the generalized axiom of revealed preference (GARP) holds. The outcome of such a test is binary: data either satisfy GARP or they don't. An implication of such an approach is that when the data do not pass the test, there is no indication concerning the severity or the amount of violations. A number of approaches have been proposed in the literature to express how close a dataset is to satisfying rationality. One popular approach is Afriat's efficiency-index. Several alternative measures have been proposed, amongst others by Houtman and Maks, and by Varian. For the latter two indices, it is empirically recognized in the literature that finding these measures is computationally intensive. We show that computing these maximum efficiency-indices is an NP-hard problem. We also show that no constant-factor approximation algorithm exists for the Houtman-Maks index unless P = NP. Finally, we give an exact polynomial time algorithm for finding the Afriat index.

**Friday, 14:15 - 14:40 h, Room: H 3027, Talk 3**

**Eleftherios Couzoudis**

Finding all generalized Nash equilibria

**Abstract:**

Often a generalized generalized Nash equilibrium problem has infinitely many solutions and commonly the solution set isn't connected. The current method is then to only compute the normalized equilibrium in which the Lagrange multipliers are equal. This is only one solution out of the set of normalized equilibria which is a subset of the solution set. For problems with linear constraints an approach is shown where all solutions are given as a union of sets. For this a modified simplex algorithm is used to yield a vertex representation of the equilibrium subsets. The implementation is then used to compute some popular examples.