# Maximising a minimum
#
# Maximises the worst-off share in a fair-division problem. The mirror of
# the minimax pattern: a single auxiliary variable is dominated by every
# term, and maximisation lifts it to exactly the minimum.
#
# Technique: Replace min_i e_i by t with t ≤ e_i for all i, then maximise
# t.
#
# On this instance the optimum is 17 (maximisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Rawls, J. (1971). A Theory of Justice. Harvard University
# Press.
model m
set A = {1, 2}
set I = {1, 2, 3, 4, 5}
const v = {{5, 6, 8, 8, 1},
{5, 6, 8, 4, 9}}, forall a in A, forall i in I
bin x, forall i in I, forall a in A
int 0 <= t <= 45
max t
# every item goes to exactly one agent
constr sum_{a in A}{x_{i,a}} = 1, forall i in I
# t is dominated by every agent's total, so maximising it lifts the worst off
constr t <= sum_{i in I}{v_{a,i} * x_{i,a}}, forall a in A
end
import elytica
Read this through MCP: read with path: "formulations/maximin", or resource hlpl://formulations/maximin.