# Zero-sum matrix game
#
# Finds the optimal mixed strategy and value of a two-player zero-sum game.
# The minimax structure becomes an LP: one variable per pure strategy plus
# the game value, and one row per opponent reply. Its dual is the opponent's
# own problem, which is von Neumann's minimax theorem read off LP duality.
#
# Technique: Maximise the value v subject to v <= the payoff of every pure
# opponent reply, with the mixed strategy summing to 1.
#
# On this instance the optimum is 3 (maximisation), confirmed
# independently by two phase simplex before publication.
#
# Reference: Dantzig, G. B. (1963). Linear Programming and Extensions.
# Princeton University Press. doi:10.1515/9781400884179
model m
set R = {1, 2, 3}
set C = {1, 2, 3}
const A = {{7, 5, 3},
{7, 9, 3},
{6, 1, 2}}, forall i in R, forall j in C
var 0 <= p <= 1, forall i in R
var 0 <= v <= 9
max v
# the mixed strategy is a probability distribution
constr sum_{i in R}{p_{i}} = 1
# v is guaranteed against every pure reply the opponent could make
constr v <= sum_{i in R}{A_{i,j} * p_{i}}, forall j in C
end
import elytica
Read this through MCP: read with path: "formulations/zero-sum-game", or resource hlpl://formulations/zero-sum-game.