5.7: Sealed Bids Method
- Page ID
- 34203
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)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.
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.
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.
Each records their value of each item, as shown below.
\(\begin{array}{|l|l|l|}
\hline & \textbf { Sam } & \textbf { Omar } \\
\hline \textbf { Couch } & \$ 150 & \$ 100 \\
\hline \textbf { TV } & \$ 200 & \$ 250 \\
\hline \textbf { Video game system } & \$ 250 & \$ 150 \\
\hline \textbf { Surround sound system } & \$ 50 & \$ 100 \\
\hline
\end{array}\)
Solution
Sam’s total valuation of the items is \(\$150+\$200+\$250+\$50 = \$650\), making a fair share for Sam \(\$650/2 = \$325\).
Omar’s total valuation of the items is \(\$100+\$250+\$150+\$100 = \$600\), making a fair share for Omar \(\$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\) of value to Sam. Since this exceeds his fair share, he has to pay the difference, $75, into a holding pile.
Omar will receive the TV and surround sound system, providing \(\$250+\$100=\$350\) in value. This is more than his fair share, so he has to pay the difference, $50, into the holding pile.
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.
Four small graphic design companies are merging operations to become one larger corporation. In this merger, there are a number of issues that need to be settled. Each company is asked to place a monetary value (in thousands of dollars) on each issue:
\(\begin{array}{|l|l|l|l|l|}
\hline & \textbf { Super Designs } & \textbf { DesignByMe } & \textbf { LayoutPros } & \textbf { Graphix } \\
\hline \textbf { Company name } & \$ 5 & \$ 3 & \$ 3 & \$ 6 \\
\hline \textbf { Company location } & \$ 8 & \$ 9 & \$ 7 & \$ 6 \\
\hline \textbf { CEO } & \$ 10 & \$ 5 & \$ 6 & \$ 7 \\
\hline \textbf { Chair of the board } & \$ 7 & \$ 6 & \$ 6 & \$ 8 \\
\hline
\end{array}\)
Solution
We can then calculate for each company:
\(\begin{array}{|l|l|l|l|l|}
\hline & \textbf { Super Designs } & \textbf { DesignByMe } & \textbf { LayoutPros } & \textbf { Graphix } \\
\hline \begin{array}{l}
\text { Total value of all } \\
\text { issues }
\end{array} & \$ 30 & \$ 23 & \$ 22 & \$ 27 \\
\hline \text { Fair share } & \$ 7.50 & \$ 5.75 & \$ 5.50 & \$ 6.75 \\
\hline
\end{array}\)
The items would then be allocated to the company that bid the most for each.
Company name would be awarded to Graphix
Company location would be awarded to DesignByMe
CEO would be awarded to Super Designs
Chair of the board would be awarded to Graphix
For each company, we calculate the total value of the items they receive, and how much they get or pay in the initial allocation
\(\begin{array}{|l|l|l|l|l|}
\hline & \textbf { Super Designs } & \textbf { DesignByMe } & \textbf { LayoutPros } & \textbf { Graphix } \\
\hline \text { Total value of issues awarded} & \$ 10 & \$ 9 & \$ 0 & \$ 14 \\
\hline \text { Amount they } & \$ 7.50-\$ 10 & \$ 5.75-\$ 9 & \$ 5.50-\$ 0 & \$ 6.75-\$ 14 \\
\text { pay/get } & \text { Pay } \$ 2.50 & \text { Pay } \$ 3.25 & \text { Get } \$ 5.50 & \text { Pay } \$ 7.25 \\
\hline
\end{array}\)
After the initial allocation, there is a total of \($2.50+\$3.25-\$5.50+\$7.25 = \$7.50\) in surplus. Dividing that evenly, each company gets $1.875 (approximately)
\(\begin{array}{|l|l|l|l|l|}
\hline & \textbf { Super Designs } & \textbf { DesignByMe } & \textbf { LayoutPros } & \textbf { Graphix } \\
\hline \text { Amount they } & \text { Pay \$2.50 } & \text { Pay \$3.25 } & \text { Get \$5.50 } & \text { Pay \$7.25 } \\
\text { pay/get } & \text { Get \$1.875 } & \text { Get \$1.875 } & \text { Get \$1.875 } & \text { Get \$1.875 } \\
\hline \text { After surplus } & \text { Pay \$0.625 } & \text { Pay \$1.375 } & \text { Get \$7.375 } & \text { Pay \$5.375 } \\
\hline
\end{array}\)
So in the final allocation,
Super Designs wins the CEO, and pays $625 ($0.625 thousand)
DesignByMe wins the company location and pays $1,375 ($1.375 thousand)
LayoutPros wins no issues, but receives $7,375 in compensation
Graphix wins the company name and chair of the board, and pays $5,375.
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.
\(\begin{array}{|l|l|l|l|}
\hline & \textbf { Jamal } & \textbf { Maggie } & \textbf { Kendra } \\
\hline \textbf { House } & \$ 250 & \$ 300 & \$ 280 \\
\hline \textbf { Vacation home } & \$ 170 & \$ 180 & \$ 200 \\
\hline \textbf { Small business } & \$ 300 & \$ 255 & \$ 270 \\
\hline
\end{array}\)
- Answer
-
Jamal’s total value is \(\$250 + \$170 + \$300 = \$720\). His fair share is $240 thousand.
Maggie’s total value is \(\$300 + \$180 + \$255 = \$735\). Her fair share is $245 thousand.
Kendra’s total value is \(\$280 + \$200 + \$270 = \$750\). Her fair share is $250 thousand.
In the initial allocation,
Jamal receives the business, and pays \(\$300 - \$240 = \$60\) thousand into holding.
Maggie receives the house, and pays \(\$300 - \$245 = \$55\) thousand into holding.
Kendra receives the vacation home, and gets \(\$250 - \$200 = \$50\) thousand from holding.
There is a surplus of \(\$60 + \$55 - \$50 = \$65\) thousand in holding, so each person will receive \(\$21,667\) from surplus. In the final allocation,
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\).
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.
\(\begin{array}{|l|l|l|}
\hline & \textbf { Chelsea } & \textbf { Mariah } \\
\hline \textbf { Vacuuming } & -\$ 10 & -\$ 8 \\
\hline \textbf { Cleaning bathroom } & -\$ 14 & -\$ 20 \\
\hline \textbf { Doing dishes } & -\$ 4 & -\$ 6 \\
\hline \textbf { Dusting } & -\$ 6 & -\$ 4 \\
\hline
\end{array}\)
Solution
We can then calculate fair share:
\(\begin{array}{|l|l|l|}
\hline & \textbf { Chelsea } & \textbf { Mariah } \\
\hline \text { Total value } & -\$ 34 & -\$ 38 \\
\hline \text { Fair Share } & -\$ 17 & -\$ 19 \\
\hline
\end{array}\)
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\)/week.
Mariah gets vacuuming and dusting, and pays \(\$7 - \$3 = \$4\)/week.