5.7 Sealed Bids Method
The Sealed Bids method provides a method for discrete fair division, allowing for the division of items that cannot be split into smaller pieces, like a house or a car. Because of this, the method requires that all parties have a large amount of cash at their disposal to balance out the difference in item values.
Note
Sealed Bids Method
The method begins by compiling a list of items to be divided. Then:
1) Each party involved lists, in secret, a dollar amount they value each item to be worth. This is their sealed bid.
2) The bids are collected. For each party, the value of all the items is totaled, and divided by the number of parties. This defines their fair share.
3) Each item is awarded to the highest bidder.
4) For each party, the value of all items received is totaled. If the value is more than that party’s fair share, they pay the difference into a holding pile. If the value is less than that party’s fair share, they receive the difference from the holding pile. This ends the initial allocation.
5) In most cases, there will be a surplus, or leftover money, in the holding pile. The surplus is divided evenly between all the players. This produces the final allocation.
While the assumptions we made for fair division methods specified that an arbitrator should not be necessary, it is common for an independent third party to collect the bids and announce the outcome. While not technically necessary, since the method can be executed without a third party involved, this protects the secrecy of the bids, which can sometimes help avoid resentment or bad feelings between the players.
Example 1
Sam and Omar have cohabitated for the last 3 years, during which time they shared the expense of purchasing several items for their home. Sam has accepted a job in another city, and now they find themselves needing to divide their shared assets.
# Math in Society 5.7 -- Sealed Bids, for things that cannot be cut in half
# Everyone bids on every item in secret. Each item goes to its highest bidder,
# then cash moves until everybody has reached their own fair share, and whatever
# is left in the holding pile is split evenly.
def sealed_bids(bids, label, unit="$"):
items = list(bids)
players = list(bids[items[0]])
n = len(players)
total = {p: sum(bids[i][p] for i in items) for p in players}
fair = {p: total[p] / n for p in players}
won = {p: [i for i in items if max(players, key=lambda q: (bids[i][q], q)) == p]
for p in players}
value = {p: sum(bids[i][p] for i in won[p]) for p in players}
initial = {p: value[p] - fair[p] for p in players} # positive = pays in
pile = sum(initial.values())
cut = pile / n
def m(v, dp=0):
return ("-" if v < 0 else "") + unit + format(abs(v), f",.{dp}f")
W = max(11, max(len(i) for i in items) + 1)
print(f"{label}")
print(f" {'':<{W}}" + "".join(f"{p:>13}" for p in players))
for i in items:
top = max(players, key=lambda q: (bids[i][q], q))
print(f" {i:<{W}}" + "".join(
f"{m(bids[i][p]) + (' *' if p == top else ' '):>13}" for p in players))
print(f" {'total':<{W}}" + "".join(f"{m(total[p]) + ' ':>13}" for p in players))
print(f" {'fair share':<{W}}" + "".join(f"{m(fair[p], 2) + ' ':>13}" for p in players))
print(f" (* = highest bidder, so that item is awarded to them)")
print(f" holding pile: {m(pile, 2)}, split {n} ways = {m(cut, 2)} each")
for p in players:
net = initial[p] - cut
verb = "pays" if net > 1e-9 else ("receives" if net < -1e-9 else "settles for")
print(f" {p:<10} takes " + (", ".join(won[p]) or "nothing")
+ f" and {verb} {unit}{abs(net):,.2f}"
+ f" (fair share {unit}{fair[p]:,.2f}, ends at {unit}{value[p]-net:,.2f})")
print()
sealed_bids({"couch": {"Sam": 150, "Omar": 100},
"TV": {"Sam": 200, "Omar": 250},
"game system": {"Sam": 250, "Omar": 150},
"sound": {"Sam": 50, "Omar": 100}},
"Sam and Omar split the apartment") # EDIT any bid
sealed_bids({"house": {"Jamal": 250, "Maggie": 300, "Kendra": 280},
"vacation": {"Jamal": 170, "Maggie": 180, "Kendra": 200},
"business": {"Jamal": 300, "Maggie": 255, "Kendra": 270}},
"An estate, in thousands", "$")
# Fair division also works on things nobody WANTS. Bid what you'd pay to avoid it.
sealed_bids({"vacuuming": {"Chelsea": -10, "Mariah": -8},
"bathroom": {"Chelsea": -14, "Mariah": -20},
"dishes": {"Chelsea": -4, "Mariah": -6},
"dusting": {"Chelsea": -6, "Mariah": -4}},
"Weekly chores (negative values: what you'd pay NOT to do it)")
print("Every player ends up better than their own fair share, and every player")
print("thinks they got the good end -- because each one is measuring with their own")
print("bids. The chores work identically: -8 beats -10, so the person who minds a")
print("chore least is the 'highest bidder' and gets stuck with it, plus cash.")
print("Try it: raise Omar's TV bid to 400 and re-run. He pays more into the pile,")
print("the surplus doubles, and BOTH of them finish further above their own fair")
print("share than before -- overbidding on what you want is not a trap, it is how")
print("the surplus gets created.")Each records their value of each item, as shown below.
Show solution
Sam’s total valuation of the items is $ 150 + $ 200 + $ 250 + $ 50 = $ 650 $ 650 / 2 = $ 325
Omar’s total valuation of the items is $ 100 + $ 250 + $ 150 + $ 100 = $ 600 $ 600 / 2 = $ 300
Each item is now awarded to the highest bidder. Sam will receive the couch and video game system, providing $ 150 + $ 250 = $ 400
Omar will receive the TV and surround sound system, providing $ 250 + $ 100 = $ 350
Thus, in the initial allocation, Sam receives the couch and video game system and pays $75 into the holding pile. Omar receives the TV and surround sound system and pays $50 into the holding pile. At this point, both players would feel they have received a fair share.
There is now $125 remaining in the holding pile. This is the surplus from the division. This is now split evenly, and both Sam and Omar are given back $62.50. Since Sam had paid in $75, the net effect is that he paid $12.50. Since Omar had originally paid in $50, the net effect is that he receives $12.50.
Thus, in the final allocation, Sam receives the couch and video game system and pays $12.50 to Omar. Omar receives the TV and surround sound system and receives $12.50. At this point, both players feel they have received more than a fair share.
Your Turn
Try it Now 6
Jamal, Maggie, and Kendra are dividing an estate consisting of a house, a vacation home, and a small business. Their valuations (in thousands) are shown below. Determine the final allocation.
Answer
Jamal’s total value is $ 250 + $ 170 + $ 300 = $ 720
Maggie’s total value is $ 300 + $ 180 + $ 255 = $ 735
Kendra’s total value is $ 280 + $ 200 + $ 270 = $ 750
In the initial allocation,
Jamal receives the business, and pays $ 300 − $ 240 = $ 60
Maggie receives the house, and pays $ 300 − $ 245 = $ 55
Kendra receives the vacation home, and gets $ 250 − $ 200 = $ 50
There is a surplus of $ 60 + $ 55 − $ 50 = $ 65 $ 21,667
Jamal receives the business, and pays $ 38,333
Maggie receives the house, and pays $ 33,333
Kendra receives the vacation home, and gets $ 71,667
Example 3
Fair division does not always have to be used for items of value. It can also be used to divide undesirable items. Suppose Chelsea and Mariah are sharing an apartment, and need to split the chores for the household. They list the chores, assigning a negative dollar value to each item; in other words, the amount they would pay for someone else to do the chore (a per week amount). We will assume, however, that they are committed to doing all the chores themselves and not hiring a maid.
Show solution
We can then calculate fair share:
We award to the person with the largest bid. For example, we award vacuuming to Mariah since she dislikes it less (remember -8 > -10).
Chelsea gets cleaning the bathroom and doing dishes. Value: -$18
Mariah gets vacuuming and dusting. Value: -$12
Notice that Chelsea’s fair share is -$17 but she is doing chores she values at -$18. She should get $1 to bring her to a fair share. Mariah is doing chores valued at -$12, but her fair share is -$19. She needs to pay $7 to bring her to a fair share.
This creates a surplus of $6, which will be divided between the two. In the final allocation:
Chelsea gets cleaning the bathroom and doing dishes, and receives $ 1 + $ 3 = $ 4
Mariah gets vacuuming and dusting, and pays $ 7 − $ 3 = $ 4
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 .
