Suppose that Abby, Brian, Chris, and Dorian are dividing a plot of land. Dorian was selected to be the divider through a coin toss. Each person’s valuation of each piece is shown below.
# Math in Society 5.4 -- The Lone Divider method
# Each chooser DECLARES every piece they'd accept as a fair share, then we try to
# hand every chooser a piece they declared. If that is impossible, it's a standoff.
from itertools import permutations
def lone_divider(table, label, unit=""):
money = (lambda v: f"{v:.4g}{unit}") if unit == "%" else (lambda v: f"{unit}{v:.4g}")
people, n = list(table), len(table)
whole = sum(table[people[0]])
fair = whole / n
# the divider is the one who cut, so every piece looks the same to them
divider = min(people, key=lambda p: max(table[p]) - min(table[p]))
choosers = [p for p in people if p != divider]
print(f"{label} ({n} parties, fair share = {money(fair)} of {money(whole)})")
print(f" divider (values every piece alike): {divider}")
bids = {}
for p in choosers:
bids[p] = [i for i, v in enumerate(table[p]) if v >= fair - 1e-9]
vals = " ".join(money(v) for v in table[p])
print(f" {p:<9} values [{vals}] declares "
+ ", ".join(f"Piece {i+1}" for i in bids[p]))
ok = [p for p in permutations(range(n), len(choosers))
if all(p[k] in bids[choosers[k]] for k in range(len(choosers)))]
if ok: # if several allocations work, take the one the choosers like most
perm = max(ok, key=lambda p: sum(table[choosers[k]][p[k]]
for k in range(len(choosers))))
for k, p in enumerate(choosers):
print(f" -> {p} gets Piece {perm[k]+1}, worth {money(table[p][perm[k]])}")
spare = [i for i in range(n) if i not in perm][0]
print(f" -> {divider} gets Piece {spare+1}, worth {money(table[divider][spare])}")
print(" everyone holds a piece they themselves called a fair share.\n")
return
wanted = {i for p in choosers for i in bids[p]}
give = min(set(range(n)) - wanted, key=lambda i: sum(table[p][i] for p in choosers))
rest = [i for i in range(n) if i != give]
print(" -> STANDOFF: between them the choosers declared only "
+ ", ".join(f"Piece {i+1}" for i in sorted(wanted))
+ f" -- {len(wanted)} pieces for {len(choosers)} choosers.")
print(f" -> give uncontested Piece {give+1} to the divider {divider},"
f" then recombine the rest:")
for p in choosers:
pool = sum(table[p][i] for i in rest)
print(f" the recombined pool is worth {money(pool)} to {p}"
f" -> {money(pool/len(choosers))} each, still at least {money(fair)}")
print()
lone_divider({"Abby": [15, 30, 20, 35], "Brian": [30, 35, 10, 25],
"Chris": [20, 45, 20, 15], "Dorian": [25, 25, 25, 25]},
"Dividing a plot of land", "%")
lone_divider({"Abby": [15, 30, 20, 35], "Brian": [20, 35, 10, 35],
"Chris": [20, 45, 20, 15], "Dorian": [25, 25, 25, 25]},
"Same plot, Brian values it differently", "%") # EDIT Brian's row
lone_divider({"Sonya": [90, 70, 80, 80], "Cesar": [80, 80, 80, 80],
"Adrianna": [60, 70, 100, 90], "Raquel": [70, 50, 90, 110]},
"Four investors, land worth $320,000 (thousands)", "$")
print("""Lone Divider works because the divider can always be handed a piece they value
at exactly 1/N, and because a standoff still leaves the remaining choosers a pool
worth more than their combined fair shares. Nobody can be squeezed out.
Try it: change Brian's row in the second table back to [30, 35, 10, 25]. The
standoff disappears -- a single number decides whether the division settles.""")
