5.4 Lone Divider

The lone divider method works for any number of parties – we will use N for the number of parties. One participant is randomly designated the divider, and the rest of the participants are designated as choosers.

Note

Lone Divider Method

The Lone Divider method proceeds as follows:

1) The divider divides the item into $N$ pieces, which we’ll label $S_{1}, S_{2}, \ldots, S_{N}$ .

2) Each of the choosers will separately list which pieces they consider to be a fair share. This is called their declaration, or bid.

3) The lists are examined. There are two possibilities:

a. If it is possible to give each party a piece they declared then do so, and the divider gets the remaining piece.

b. If two or more parties both want the same pieces and no others, then give a non-contested piece to the divider. The rest of the pieces are combined and repeat the entire procedure with the remaining parties. If there are only two parties left, they can use divider-chooser.

Example 1

Consider the example from earlier, in which the pieces were valued as:

	Piece 1	Piece 2	Piece 3
Chooser 1	$40 \%$	$30 \%$	$30 \%$
Chooser 2	$45 \%$	$30 \%$	$25 \%$
Divider	$33.3 \%$	$33.3 \%$	$33.3 \%$

Show solution

Each chooser makes a declaration of which pieces they value as a fair share. In this case,

Chooser 1 would make the declaration: Piece 1

Chooser 2 would make the declaration: Piece 1

Since both choosers want the same piece, we cannot immediately allocate the pieces. The lone divider method specifies that we give a non-contested piece to the divider. Both pieces 2 and 3 are uncontested, so we flip a coin and give Piece 2 to the divider. Piece 1 and 3 are then recombined to make a piece worth 70% to Chooser 1, and 70% to Chooser 2. Since there are only two players left, they can divide the recombined pieces using divider-chooser. Each is guaranteed a piece they value as at least 35%, which is a fair share.

Your Turn

Try it Now 3

Use the Lone Divider method to complete the fair division given the values below.

	Piece 1	Piece 2	Piece 3
Chooser 1	$40 \%$	$30 \%$	$30 \%$
Chooser 2	$40 \%$	$35 \%$	$25 \%$
Divider	$33.3 \%$	$33.3 \%$	$33.3 \%$

Answer

Chooser 1 would make the declaration: Piece 1

Chooser 2 would make the declaration: Piece 1, Piece 2

We can immediately allocate the pieces, giving Piece 2 to Chooser 2, Piece 1 to Chooser 1, and Piece 3 to the Divider. All players receive a piece they value as a fair share.

Example 2

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.""")

	Piece 1	Piece 2	Piece 3	Piece 4
Abby	$15 \%$	$30 \%$	$20 \%$	$35 \%$
Brian	$30 \%$	$35 \%$	$10 \%$	$25 \%$
Chris	$20 \%$	$45 \%$	$20 \%$	$15 \%$
Dorian	$25 \%$	$25 \%$	$25 \%$	$25 \%$

Show solution

Based on this, their declarations should be:

Abby: Piece 2, Piece 4

Brian: Piece 1, Piece 2, Piece 4

Chris: Piece 2

This case can be settled simply – by awarding Piece 2 to Chris, Piece 4 to Abby, Piece 1 to Brian, and Piece 3 to Dorian. Each person receives a piece that they value as at least a fair share (25% value).

Example 3

Suppose the valuations in the previous problem were:

	Piece 1	Piece 2	Piece 3	Piece 4
Abby	$15 \%$	$30 \%$	$20 \%$	$35 \%$
Brian	$20 \%$	$35 \%$	$10 \%$	$35 \%$
Chris	$20 \%$	$45 \%$	$20 \%$	$15 \%$
Dorian	$25 \%$	$25 \%$	$25 \%$	$25 \%$

Show solution

The declarations would be:

Abby: Piece 2, Piece 4

Brian: Piece 2, Piece 4

Chris: Piece 2

Notice in this case that there is no simple settlement. So, the piece no one else declared, Piece 3, is awarded to the original divider Dorian, and the procedure is repeated with the remaining three players.

Suppose that on the second round of this method Brian is selected to be the divider, three new pieces are cut, and the valuations are as follows:

	Piece 1	Piece 2	Piece 3
Abby	$40 \%$	$30 \%$	$30 \%$
Brian	$33.3 \%$	$33.3 \%$	$33.3 \%$
Chris	$50 \%$	$20 \%$	$30 \%$

The declarations here would be:

Abby: Piece 1

Chris: Piece 1

Once again we have a standoff. Brian can be awarded either of Piece 2 or Piece 3, and the remaining pieces can be recombined. Since there are only two players left, they can divide the remaining land using the basic divider-chooser method.

Your Turn

Try it Now 4

Four investors are dividing a piece of land valued at $320,000. One was chosen as the divider, and their values of the division (in thousands) are shown below. Who was the divider? Describe the outcome of the division.

	Piece 1	Piece 2	Piece 3	Piece 4
Sonya	$\$ 90$	$\$ 70$	$\$ 80$	$\$ 80$
Cesar	$\$ 80$	$\$ 80$	$\$ 80$	$\$ 80$
Adrianna	$\$ 60$	$\$ 70$	$\$ 100$	$\$ 90$
Raquel	$\$ 70$	$\$ 50$	$\$ 90$	$\$ 110$

Answer

A fair share would be $80,000. Cesar was the divider.

Their declarations would be:

Sonya: Pierce 1, Piece 3, Piece 4.
Adrianna: Piece 3, Piece 4.
Raquel: Piece 3, Piece 4.

Sonya would receive Piece 1 and Cesar would receive the uncontested Piece 2.

Since Adrianna and Raquel are both ok with either Piece 3 or Piece 4, it is possible to allocate all the pieces to someone who has declared them, and there is no need to combine those pieces and repeat the process. However the lone divider method doesn't specify how to allocate pieces when multiple choosers are ok with the same pieces, so that's left up to us. In this particular case, we could notice that of the two pieces, Adrianna prefers 3 while Raquel prefers 4, so that'd be the ideal distribution resulting in everyone receiving a piece they value a a fair share. But we also could have just flipped a coin to allocate the pieces between them and still ended up with a fair division (just maybe not an envy-free fair division).

Adapted from Math in Society by David Lippman, hosted on LibreTexts (math.libretexts.org) and licensed under CC BY-SA 3.0. Changes were made. License: CC-BY-SA-3.0.