Counterexamples in fair division

__counterexamples_fair_division.txt

A collection of some counterexamples I've found for
fair allocation of indivisible goods, mostly via random sampling.

ef_ef1_connected.txt

Additive valuations where there exists no envy-free lottery 
whose support only includes EF1 connected allocations, 
when items are ordered on a path.

additive valuations, one row per agent:
[3, 3, 0, 5, 4]
[4, 0, 4, 7, 6]
[6, 7, 3, 4, 4]
all EF1 connected allocations:
{a}, {e}, {bcd}
{e}, {a}, {bcd}
{ab}, {e}, {cd}
{e}, {ab}, {cd}
{cd}, {e}, {ab}
{e}, {cd}, {ab}
{d}, {e}, {abc}
{e}, {d}, {abc}
linear program says there's no way to combine them into EF

ef_efx_po.txt

Additive valuations where there exists no envy-free lottery 
whose support only includes EFx + PO allocations.

utilities:
[4.324934406119022, 4.943040081769852, 5.0289022449163925, 5.662927091771665, 5.662942084623662]
[4.5916840406621215, 5.592268930787794, 5.6368451333997225, 6.212904250228197, 7.504461944449886]
[5.3019576336142356, 5.420799151967095, 5.696739329289325, 5.812331125620395, 6.8149605519022245]
{ab}, {cd}, {e}
{ab}, {e}, {cd}
{ac}, {bd}, {e}
{ad}, {bc}, {e}
{ac}, {e}, {bd}
{ad}, {e}, {bc}
{bd}, {ac}, {e}
{cd}, {ab}, {e}
{bd}, {e}, {ac}
{cd}, {e}, {ab}

-------
Additive valuations where there exists no envy-free lottery 
whose support only includes PMMS + PO allocations.

[2.4329359509055655, 4.604846233153175, 5.175368248214479, 5.213142398980857, 5.7562334221853115]
[4.164944748496483, 4.29317794271225, 4.675741912088396, 4.7418908132674895, 5.966175358548215]
[3.6298571865046374, 4.695559569214814, 4.76008828915616, 5.925340668516357, 5.925342144176543]
PMMS + PO allocations in instance:
{bc}, {e}, {ad}
{e}, {bc}, {ad}

mms_submodular.txt

The following paper includes an example (Theorem 4.2) of an instance with submodular valuations
where no 3/4-MMS allocation exists.
Ghodsi, Mohammad, et al. "Fair allocation of indivisible goods: Improvements and generalizations." Proceedings of the 2018 ACM Conference on Economics and Computation. 2018.
https://dl.acm.org/doi/abs/10.1145/3219166.3219238

The following submodular instance with 2 agents and 4 goods admits no 2/3-MMS allocation.
Gurobi indicates that there are no counterexamples of this size for (2/3-eps)-MMS.
(Please ask for permission before publishing this example.)

Bundles:        empty | a   | b    | c    | d    | ab   | ac   | ad   | bc   | bd   | cd   | abc  | abd  | acd  | bcd  | abcd 
Valuation of 0 - [0.0, 200.0, 200.0, 100.0, 100.0, 300.0, 200.0, 300.0, 300.0, 200.0, 200.0, 300.0, 300.0, 300.0, 300.0, 300.0]
MMS value of 0 - 300.0 witnessed by ad - bc  
Valuation of 1 - [0.0, 200.0, 200.0, 100.0, 100.0, 300.0, 300.0, 200.0, 200.0, 300.0, 200.0, 300.0, 300.0, 300.0, 300.0, 300.0]
MMS value of 1 - 300.0 witnessed by ac - bd  

abcd -    -> 1 gets 0.0 <= 0.67 * 300.0
abc - d   -> 1 gets 100.0 <= 0.67 * 300.0
abd - c   -> 1 gets 100.0 <= 0.67 * 300.0
ab - cd   -> 1 gets 200.0 <= 0.67 * 300.0
acd - b   -> 1 gets 200.0 <= 0.67 * 300.0
ac - bd   -> 0 gets 200.0 <= 0.67 * 300.0
ad - bc   -> 1 gets 200.0 <= 0.67 * 300.0
a - bcd   -> 0 gets 200.0 <= 0.67 * 300.0
bcd - a   -> 1 gets 200.0 <= 0.67 * 300.0
bc - ad   -> 1 gets 200.0 <= 0.67 * 300.0
bd - ac   -> 0 gets 200.0 <= 0.67 * 300.0
b - acd   -> 0 gets 200.0 <= 0.67 * 300.0
cd - ab   -> 0 gets 200.0 <= 0.67 * 300.0
c - abd   -> 0 gets 100.0 <= 0.67 * 300.0
d - abc   -> 0 gets 100.0 <= 0.67 * 300.0
 - abcd   -> 0 gets 0.0 <= 0.67 * 300.0

po_efx.txt

Additive valuations where no allocation is PO and EFx:
Agent 1: 2, 1, 0
Agent 2: 2, 0, 1

By PO, the only possible allocations are {ab}, {c} and {b}, {ac}, but both fail EFx.

I am not aware of counterexamples to PO and EFx for strictly positive valuations.

po_sdef1.txt

Counterexample to existence of PO + SD-EF1, with positive additive valuations.
DP, April 2020         
         
         a  b  c  d  e  f
Agent 1: 1, 1, 1, 3, 4, 5
Agent 2: 2, 2, 2, 3, 4, 5
Agent 3: 2, 2, 2, 3, 4, 5

{ab}, {cd}, {ef}: 1 envies 3 because |{}| < |{ef}| - 1.
{ab}, {ce}, {df}: 1 envies 3 because |{}| < |{df}| - 1.
{ab}, {cf}, {de}: 1 envies 3 because |{}| < |{de}| - 1.
{ab}, {de}, {cf}: 1 envies 2 because |{}| < |{de}| - 1.
{ab}, {df}, {ce}: 1 envies 2 because |{}| < |{df}| - 1.
{ab}, {ef}, {cd}: 1 envies 2 because |{}| < |{ef}| - 1.
{ac}, {bd}, {ef}: 1 envies 3 because |{}| < |{ef}| - 1.
{ac}, {be}, {df}: 1 envies 3 because |{}| < |{df}| - 1.
{ac}, {bf}, {de}: 1 envies 3 because |{}| < |{de}| - 1.
{ad}, {bc}, {ef}: 1 envies 3 because |{}| < |{ef}| - 1.
{ae}, {bc}, {df}: 2 envies 3 because |{}| < |{df}| - 1.
{af}, {bc}, {de}: 2 envies 3 because |{}| < |{de}| - 1.
{ad}, {be}, {cf}: dominated by {e}, {cf}, {abd}
{ad}, {bf}, {ce}: dominated by {e}, {bf}, {acd}
{ae}, {bd}, {cf}: dominated by {f}, {ce}, {abd}
{af}, {bd}, {ce}: dominated by {de}, {f}, {abc}
{ae}, {bf}, {cd}: dominated by {f}, {de}, {abc}
{af}, {be}, {cd}: dominated by {de}, {abc}, {f}
{ac}, {de}, {bf}: 1 envies 2 because |{}| < |{de}| - 1.
{ac}, {df}, {be}: 1 envies 2 because |{}| < |{df}| - 1.
{ac}, {ef}, {bd}: 1 envies 2 because |{}| < |{ef}| - 1.
{ad}, {ce}, {bf}: dominated by {e}, {cf}, {abd}
{ad}, {cf}, {be}: dominated by {e}, {bf}, {acd}
{ae}, {cd}, {bf}: dominated by {f}, {ce}, {abd}
{af}, {cd}, {be}: dominated by {de}, {f}, {abc}
{ae}, {cf}, {bd}: dominated by {f}, {de}, {abc}
{af}, {ce}, {bd}: dominated by {de}, {abc}, {f}
{ad}, {ef}, {bc}: 1 envies 2 because |{}| < |{ef}| - 1.
{ae}, {df}, {bc}: 3 envies 2 because |{}| < |{df}| - 1.
{af}, {de}, {bc}: 3 envies 2 because |{}| < |{de}| - 1.
{bc}, {ad}, {ef}: 1 envies 3 because |{}| < |{ef}| - 1.
{bc}, {ae}, {df}: 1 envies 3 because |{}| < |{df}| - 1.
{bc}, {af}, {de}: 1 envies 3 because |{}| < |{de}| - 1.
{bd}, {ac}, {ef}: 1 envies 3 because |{}| < |{ef}| - 1.
{be}, {ac}, {df}: 2 envies 3 because |{}| < |{df}| - 1.
{bf}, {ac}, {de}: 2 envies 3 because |{}| < |{de}| - 1.
{bd}, {ae}, {cf}: dominated by {e}, {cf}, {abd}
{bd}, {af}, {ce}: dominated by {e}, {bf}, {acd}
{be}, {ad}, {cf}: dominated by {f}, {ce}, {abd}
{bf}, {ad}, {ce}: dominated by {de}, {f}, {abc}
{be}, {af}, {cd}: dominated by {f}, {de}, {abc}
{bf}, {ae}, {cd}: dominated by {de}, {abc}, {f}
{cd}, {ab}, {ef}: 1 envies 3 because |{}| < |{ef}| - 1.
{ce}, {ab}, {df}: 2 envies 3 because |{}| < |{df}| - 1.
{cf}, {ab}, {de}: 2 envies 3 because |{}| < |{de}| - 1.
{de}, {ab}, {cf}: 2 envies 1 because |{}| < |{de}| - 1.
{df}, {ab}, {ce}: 2 envies 1 because |{}| < |{df}| - 1.
{ef}, {ab}, {cd}: 2 envies 1 because |{}| < |{ef}| - 1.
{cd}, {ae}, {bf}: dominated by {e}, {cf}, {abd}
{cd}, {af}, {be}: dominated by {e}, {bf}, {acd}
{ce}, {ad}, {bf}: dominated by {f}, {ce}, {abd}
{cf}, {ad}, {be}: dominated by {de}, {f}, {abc}
{ce}, {af}, {bd}: dominated by {f}, {de}, {abc}
{cf}, {ae}, {bd}: dominated by {de}, {abc}, {f}
{de}, {ac}, {bf}: 2 envies 1 because |{}| < |{de}| - 1.
{df}, {ac}, {be}: 2 envies 1 because |{}| < |{df}| - 1.
{ef}, {ac}, {bd}: 2 envies 1 because |{}| < |{ef}| - 1.
{de}, {af}, {bc}: 3 envies 1 because |{}| < |{de}| - 1.
{df}, {ae}, {bc}: 3 envies 1 because |{}| < |{df}| - 1.
{ef}, {ad}, {bc}: 2 envies 1 because |{}| < |{ef}| - 1.
{bc}, {de}, {af}: 1 envies 2 because |{}| < |{de}| - 1.
{bc}, {df}, {ae}: 1 envies 2 because |{}| < |{df}| - 1.
{bc}, {ef}, {ad}: 1 envies 2 because |{}| < |{ef}| - 1.
{bd}, {ce}, {af}: dominated by {e}, {cf}, {abd}
{bd}, {cf}, {ae}: dominated by {e}, {bf}, {acd}
{be}, {cd}, {af}: dominated by {f}, {ce}, {abd}
{bf}, {cd}, {ae}: dominated by {de}, {f}, {abc}
{be}, {cf}, {ad}: dominated by {f}, {de}, {abc}
{bf}, {ce}, {ad}: dominated by {de}, {abc}, {f}
{bd}, {ef}, {ac}: 1 envies 2 because |{}| < |{ef}| - 1.
{be}, {df}, {ac}: 3 envies 2 because |{}| < |{df}| - 1.
{bf}, {de}, {ac}: 3 envies 2 because |{}| < |{de}| - 1.
{cd}, {be}, {af}: dominated by {e}, {cf}, {abd}
{cd}, {bf}, {ae}: dominated by {e}, {bf}, {acd}
{ce}, {bd}, {af}: dominated by {f}, {ce}, {abd}
{cf}, {bd}, {ae}: dominated by {de}, {f}, {abc}
{ce}, {bf}, {ad}: dominated by {f}, {de}, {abc}
{cf}, {be}, {ad}: dominated by {de}, {abc}, {f}
{de}, {bc}, {af}: 2 envies 1 because |{}| < |{de}| - 1.
{df}, {bc}, {ae}: 2 envies 1 because |{}| < |{df}| - 1.
{ef}, {bc}, {ad}: 2 envies 1 because |{}| < |{ef}| - 1.
{de}, {bf}, {ac}: 3 envies 1 because |{}| < |{de}| - 1.
{df}, {be}, {ac}: 3 envies 1 because |{}| < |{df}| - 1.
{ef}, {bd}, {ac}: 2 envies 1 because |{}| < |{ef}| - 1.
{cd}, {ef}, {ab}: 1 envies 2 because |{}| < |{ef}| - 1.
{ce}, {df}, {ab}: 3 envies 2 because |{}| < |{df}| - 1.
{cf}, {de}, {ab}: 3 envies 2 because |{}| < |{de}| - 1.
{de}, {cf}, {ab}: 3 envies 1 because |{}| < |{de}| - 1.
{df}, {ce}, {ab}: 3 envies 1 because |{}| < |{df}| - 1.
{ef}, {cd}, {ab}: 2 envies 1 because |{}| < |{ef}| - 1.