= Set cover reduction to equilibrium support
Assume $2\leq k<m$ and $\bigcup_iS_i=S$. Construct a two-player game with row $i$ for $S_i$ and columns $0,1,\ldots,n$. Column $0$ pays both players one; column $j>0$ pays $(1,0)$ when $j\in S_i$, and $(0,k/(k-1))$ otherwise. There is a <Nash equilibrium> whose row player's <support of a mixed strategy> has size $k$ exactly when $k$ rows cover the universe. A uniform mixture on a cover makes column $0$ a <best response>. Conversely, if some element is uncovered by the support, the column player's <best responses> are uncovered elements and the row player's current payoff is zero. The union promise provides a profitable row deviation. Without the union promise the equivalence is false: a globally uncovered element is a <best response> against every row mixture.
// Target: mathematical-optimization.bigb
Back to article page
