Expected Maximin Fairness in Max-Cut and other Combinatorial Optimization Problems

Jad Salem, Reuben Tate, Stephan Eidenbenz

Maximin fairness is the ideal that the worst-off group (or individual) should be treated as well as possible. Literature on maximin fairness in various decision-making settings has…