game theory programmers

Abstract: In perfect-information two-player stochastic games, the notions of Blackwell and sensitive optimality provide generalizations of the classical mean-payoff optimality and discount optimality criteria to account for more farsighted preferences. We provide bounds on the Blackwell threshold $α_{\sf bw}$ and the $d$-sensitive thresholds $α_{\sf d}$, defined as the smallest discount factors above which discount optimal policies coincide with Blackwell optimal policies and $d$-sensitive optimal policies respectively. Our refined bounds improve upon prior work by focusing on ``reduced'' families of polynomials and, crucially, our bounds are tight in terms of controlling the degrees and heights of the minimal polynomials of the Blackwell thresholds. We apply classical root separation based on Mahler's and Cauchy's bounds to our reduced families to derive the strongest upper and lower bounds on $α_{\sf bw}$ in the literature, and we are the first to obtain bounds on $α_{\sf d}$ in the multichain stochastic setting.

Abstract: In Max-$k$-Cut games, optimal colorings maximize social welfare, but are they stable against coordinated deviations that strictly benefit every participating player? A recurring conjecture in the literature asserts that, for unweighted graphs, every optimal coloring has this stability property, known as strong equilibrium. We disprove the conjecture for every $k\ge3$ by exhibiting a finite, simple, connected, unweighted graph with an optimal coloring that is not a strong equilibrium. The profitable coalitional deviation leads to another optimal coloring: every coalition member gains, while players outside the coalition bear the corresponding losses and social welfare remains unchanged. We also give an exact identity relating coalitional gains, changes in cut value, and internal conflicts, recovering the known stability guarantee for optimal colorings when the maximum degree is at most $2k-1$. For strong deviations from general Nash equilibria, we establish a sharp upper bound on the number of monochromatic edges remaining within the coalition and show that this number can exceed the coalition size.