14 problems

In a finite game, consider the set of Nash equilibria in mixed strategies and its connected components. A component is strategically essential if it persists under sufficiently sma…

Semicontinuity conjecture. The displayed inequality holds for every generic two-action game and every $d\in\{0,1,\ldots,m\}$.

Bi-SP Conjecture. If $G$ has an $(s,V_T)$-path, then $P_1$ and $P_2$ have such a path in common, that is,

Terminal Nash equilibrium conjecture. Every finite positive two-person shortest path game has a terminal Nash equilibrium provided it has at least one terminal play.

Let $C$ be the payoff matrix of a game, let $X$ and $Z$ be the variables in the system … … A convergence conjecture. This system has a solution that converges to a symmetric Nash e…

Consider the Trail of Lost Pennies on the finite trail $\llbracket -j-1,k+1\rrbracket$ in its symmetric standard form. Finite-trail equilibrium-count conjecture. The number of time…

Let $Q:(0,\infty)\to\mathbb{N}$ denote the maximum cardinality of a set of mutually shift-inequivalent time-invariant Nash equilibria for the game $\operatorname{Standard}(x)$, and…

Let $Q:(0,\infty)\to\mathbb{N}$ denote the maximum cardinality of a set of mutually shift-inequivalent time-invariant Nash equilibria for the game $\operatorname{Standard}(x)$. For…

Let $G$ be a finite directed graph, and call it bidirected if every non-terminal move is reversible: for non-terminal vertices $v'$ and $v”$, $v'v”\in E(G)$ if and only if…

A finite deterministic graphical game is a finite directed graph whose terminal vertices represent terminal outcomes and whose directed cycles represent a common outcome $c$. Let…

Let a finite two-person game with a tight game form have Alice's and Bob's lexsafe strategies and the corresponding lexsafe Nash equilibrium boxes NE-A and NE-B. Preference conject…

Let a nondegenerate bimatrix game be a two-player game in which the two players have the same number $r$ of actions, and let an equilibrium mean a Nash equilibrium of the game. Qui…

An FPTAS for computing Nash equilibria in $k$-strategy anonymous games is an algorithm running in time polynomial in the input size and $1/\epsilon$ that returns an $\epsilon$-appr…

An $n$-player anonymous game has a fixed number $k=O(1)$ of strategies, and an $\boldsymbol{\epsilon}$-Nash equilibrium is an equilibrium in which no player can gain more than…