20 problems

Symmetric price-of-anarchy conjecture. The bound is tight: the price of anarchy in the symmetric case is

Let Algorithm be the algorithm defined in the paper, let $M$ denote its termination parameter, and let $\epsilon>0$. Termination conjecture. Algorithm will terminate with…

Greedy approximation conjecture. A greedy approximation algorithm similar to the algorithm in Hoffmann's Proposition 2.17 should also be designable.

Consider a hedonic game and the welfare of a coalition structure, with the price of anarchy measuring the ratio between the maximum possible welfare and the welfare of the worst…

A fractional hedonic game assigns each agent utility equal to the average value they receive from the members of their coalition. A coalition structure is $q$-size core stable if n…

Let $V$ be a set of $n$ agents that build a connected graph $G=(V,E)$, where each agent buys a set of edges and pays an edge cost of $\alpha$ for every edge it buys, in addition to…

Bounded-delay convergence conjecture. If information delays are bounded, then proportional response dynamics converge in the full asynchrony model.

Let $\Lambda\in(0,1)$ be a peak. A Single-Peaked Jump Schelling Game and a Single-Peaked Swap Schelling Game are instances of the respective models, and $\operatorname{NE}$ denotes…

A finite game is specified by its players, strategy sets, and payoff functions, and a Nash equilibrium is a strategy profile from which no player can profit by unilaterally deviati…

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…

Optimal-coloring strong-equilibrium conjecture. Every optimal coloring is an SE.

Kawamura–Soejima's conjecture. The best possible efficiency satisfies $\alpha\leq\frac{2}{3}$ for every set of agent speeds.

Let a finite game be either a two-player general-sum game or a multiplayer game, and let a Nash equilibrium be a strategy profile from which no player can gain by deviating unilate…

Let $N=\{1,\ldots,n\}$ be the set of players, let $\alpha>0$ be the link cost, and let a strategy profile determine a communication network on $N$. The cost of player $i$ is … The…

Let a generator's weak incentive to deviate mean that there exists an execution of the deviation dynamics along which … so that the generator obtains a higher payoff than…

Seasonality upper-bound conjecture. Based on numerical examples, $D(\boldsymbol{\delta})$ is always an upper bound for the extra equilibrium cost due to seasonality.

Computational hardness conjecture. There is no polynomial-time algorithm for computing Nash equilibria.

Consider the least best response dynamics for the capacitated selfish replication game on a network with an arbitrary number of resources. Let $B$ denote a constant factor, and cal…

Consider the least best response dynamics for the capacitated selfish replication game on a network, where a bad case is the exceptional configuration described in the preceding an…

An anonymous game is a game in which all players have the same strategy set and a player's payoff is unchanged when two other players exchange their strategies. Let $L(n,m,\delta)$…