$$\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}}$$

8.4: Discrete Methods - Sealed Bids and Markers

$$\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}}$$

There are two more fair division methods that deal with discrete objects. It two heirs have to split a house they cannot just cut the house in half. Instead we have to figure out a way to keep the house intact and still have both heirs feel like they received a fair share. The method of sealed bids is used for dividing up a small number of objects not necessarily similar in value. If there are many objects similar in value, like a jewelry collection, the method of markers can be used to find a fair division.

Method of Sealed Bids

The method of sealed bids can be used to split up an estate among a small number of heirs. A nice feature of this method is that every player in the game ends up with more than a fair share (in their own eyes). The method can also be used when business partners wish to dissolve a partnership in an equitable way or roommates want to divide up a large list of chores.

We make the following assumptions in the method of sealed bids.

1. The players are the only ones involved in the game and are willing to accept the outcome.
2. The players have no prior knowledge of the other players’ preferences so they do not try to manipulate the game. If this assumption is not met the game might not produce a fair division.
3. The players are not emotionally/irrationally attached to any of the items. The players will settle for any of the items or cash as long as it is a fair share. For example, no one would say “I want the house and I will do anything to get it.”

The easiest way to explain the method is to work through an example. An easy way to keep the steps neat and organized is to do the steps in one big table, working from the top to the bottom.

Example $$\PageIndex{1}$$: Method of Sealed Bids, #1

Three heirs, Alice, Betty and Charles inherit an estate consisting of a house, a painting and a tractor. They decide to use the method of sealed bids to divide the estate among themselves.

1. The players each submit a list of bids for the items. The bid is the value that a player would assign to the item. The bids are done privately and independently. The bids are usually listed in a table.
Table $$\PageIndex{1}$$: Initial Bids

Alice

Betty

Charles

House

$280,000$275,000

$300,000 Painting$75,000

$70,000$72,000

Tractor

$56,000$60,000

$63,000 1. For each item, the player with the highest bid wins the item. The winning bids are highlighted in the table. Table $$\PageIndex{2}$$: Winning Bids Alice Betty Charles House$280,000

$275,000$300,000

Painting

$75,000$70,000

$72,000 Tractor$56,000

$60,000$63,000

1. For each player find the sum of his/her bids. This amount is what the player thinks the whole estate is worth. For three players, each player is entitled to one third of the estate. Divide each sum by three to get a fair share for each player. Remember that each player sees the values differently so the fair shares will not be the same.
Table $$\PageIndex{3}$$: Total Bids and Fair Shares

Alice

Betty

Charles

House

$280,000$275,000

$300,000 Painting$75,000

$70,000$72,000

Tractor

$56,000$60,000

$63,000 Total Bids$411,000

$405,000$435,000

Fair Share

$137,000$135,000

$145,000 1. Each player either gets more than his/her fair or less than his/her fair share when the items are awarded. Find the difference between the fair share and the items awarded for each player. If a player was awarded more than his/her fair share, the player owes the difference to the estate. If a player was awarded less than his/her fair share, the estate owes the player the difference. Alice:$137,000 - $75,000 =$62,000. The estate owes Alice $62,000. Betty:$135,000 - $0 =$135,000. The estate owes Betty $135,000. Charles:$145,000 – ($300,000 +$63,000) = -$218,000. Charles owes the estate$218,000.

Table $$\PageIndex{4}$$: Owed to Estate and Estate Owes

Alice

Betty

Charles

House

$280,000$275,000

$300,000 Painting$75,000

$70,000$72,000

Tractor

$56,000$60,000

$63,000 Total Bids$411,000

$405,000$435,000

Fair Share

$137,000$135,000

$145,000 Owed to Estate$218,000

Estate Owes

$62,000$135,000

1. At this point in the game, there is always some extra money in the estate called the surplus. To find the surplus, we find the difference between all the money owed to the estate and all the money the estate owes.

$218,000 – ($62,000 + $135,000) =$21,000.

Divide this surplus evenly between the three players.

Table $$\PageIndex{5}$$: Share of Surplus

Alice

Betty

Charles

House

$280,000$275,000

$300,000 Painting$75,000

$70,000$72,000

Tractor

$56,000$60,000

$63,000 Total Bids$411,000

$405,000$435,000

Fair Share

$137,000$135,000

$145,000 Owed to Estate$218,000

Estate Owes

$62,000$135,000

Share of Surplus

$7,000$7,000

$7,000 1. Finish the problem by combining the share of the surplus to either the amount owed to the estate or the amount the estate owes. Include the items awarded in the final share as well as any money. Alice:$62,000 + $7,000 =$69,000

Betty: $135,000 +$7,000 = $142,000 Charles: -$218,000 + $7,000 = -$211,000

Table $$\PageIndex{6}$$: Final Share

Alice

Betty

Charles

House

$280,000$275,000

$300,000 Painting$75,000

$70,000$72,000

Tractor

$56,000$60,000

$63,000 Total Bids$411,000

$405,000$435,000

Fair Share

$137,000$135,000

$145,000 Owed to Estate$218,000

Estate Owes

$62,000$135,000

Share of Surplus

$7,000$7,000

$7,000 Final Share Gets painting and$69,000 cash

Gets $142,000 cash Gets house and tractor and pays$211,000

Alice gets the painting and $69,000 cash. Betty gets$142,000 cash. Charles gets the house and the tractor and pays $211,000 to the estate. Now, we find the value of the final settlement for each of the three heirs in this example. Remember that each player has their own value system in this game so fair shares are not the same amount. Alice: Painting worth$75,000 and $69,000 cash for a total of$144,000. This is $7,000 more than her fair share of$137,000.

Betty: $142,000 cash. This is$7,000 more than her fair share of $135,000. Charles: House worth$300,000, tractor worth $63,000 and pays$211,000 for a total share of $152,000. This is$7,000 more that his fair share of $145,000. At the end of the game, each player ends up with more than a fair share. It always works out this way as long as the assumptions are satisfied. Summary of the Method of Sealed Bids: 1. Each player privately and independently bids on each item. A bid is the amount the player thinks the item is worth. 2. For each item, the player with the highest bid wins the item. 3. For each player find the sum of the bids and divide this sum by the number of players to find the fair share for that player. 4. Find the difference (fair share) – (total of items awarded) for each player. If the difference is negative, the player owes the estate that amount of money. If the difference is positive, the estate owes the player that amount of money. 5. Find the surplus by finding the difference (sum of money owed to the estate) – (sum of money the estate owes). Divide the surplus by the number of players to find the fair share of surplus. 6. Find the final settlement by adding the share of surplus to either the amount owed to the estate or the amount the estate owes. Include any items awarded and any cash owed in the final settlement. The sum of all the cash in the final settlement should be$0.

Example $$\PageIndex{2}$$: Method of Sealed Bids, #2

Doug, Edward, Frank and George have inherited some furniture from their great-grandmother’s estate and wish to divide the furniture equally among themselves. Use the method of sealed bids to find a fair division of the furniture.

Note: We start with one table and add lines to the bottom as we go through the steps.

1. List the bids in table form.
Table $$\PageIndex{7}$$: Initial Bids

Doug

Edward

Frank

George

Dresser

$280.00$275.00

$250.00$300.00

Desk

$480.00$500.00

$450.00$475.00

Wardrobe

$775.00$800.00

$850.00$800.00

Dining Set

$1,000.00$800.00

$900.00$950.00

Poster Bed

$500.00$650.00

$600.00$525.00

1. Award each item to the highest bidder.
 Doug Edward Frank George Dresser $280.00$275.00 $250.00$300.00 Desk $480.00$500.00 $450.00$475.00 Wardrobe $775.00$800.00 $850.00$800.00 Dining Set $1,000.00$800.00 $900.00$950.00 Poster Bed $500.00$650.00 $600.00$525.00
1. Find the fair share for each player.

Doug:

Edward:

Calculate similarly for Frank and George.

Table $$\PageIndex{9}$$: Total Bids and Fair Shares

Doug

Edward

Frank

George

Dresser

$280.00$275.00

$250.00$300.00

Desk

$480.00$500.00

$450.00$475.00

Wardrobe

$775.00$800.00

$850.00$800.00

Dining Set

$1,000.00$800.00

$900.00$950.00

Poster Bed

$500.00$650.00

$600.00$525.00

Total Bids

$3,035.00$3,025.00

$3,050.00$3,050.00

Fair Share

$758.75$756.25

$762.50$762.50

1. Find the amount owed to the estate or the amount the estate owes.

Doug: $$\ 758.75-\ 1000.00=-\ 241.25$$

Doug owes the estate $241.25. Calculate similarly for Edward and Frank. George: $$\ 762.50-\ 300.00=\ 462.50$$ The estate owes George$462.50.

Table $$\PageIndex{10}$$: Owes to Estate and Estate Owes

Doug

Edward

Frank

George

Dresser

$280.00$275.00

$250.00$300.00

Desk

$480.00$500.00

$450.00$475.00

Wardrobe

$775.00$800.00

$850.00$800.00

Dining Set

$1,000.00$800.00

$900.00$950.00

Poster Bed

$500.00$650.00

$600.00$525.00

Total Bids

$3,035.00$3,025.00

$3,050.00$3,050.00

Fair Share

$758.75$756.25

$762.50$762.50

Owes to Estate

$241.25$393.75

$87.50 Estate Owes$462.50

1. Find the share of surplus for each player.
Table $$\PageIndex{11}$$: Share of Surplus

Doug

Edward

Frank

George

Dresser

$280.00$275.00

$250.00$300.00

Desk

$480.00$500.00

$450.00$475.00

Wardrobe

$775.00$800.00

$850.00$800.00

Dining Set

$1,000.00$800.00

$900.00$950.00

Poster Bed

$500.00$650.00

$600.00$525.00

Total Bids

$3,035.00$3,025.00

$3,050.00$3,050.00

Fair Share

$758.75$756.25

$762.50$762.50

Owes to Estate

$241.25$393.75

$87.50 Estate Owes$462.50

Share of Surplus

$65.00$65.00

$65.00$65.00

1. Find the final share for each player.

Doug: $$-\ 241.25+\ 65.00=-\ 176.25$$

Calculate similarly for Edward and Frank.

George: $$\ 462.50+\ 65.00=\ 527.50$$

Table $$\PageIndex{12}$$: Final Shares

Doug

Edward

Frank

George

Dresser

$280.00$275.00

$250.00$300.00

Desk

$480.00$500.00

$450.00$475.00

Wardrobe

$775.00$800.00

$850.00$800.00

Dining Set

$1,000.00$800.00

$900.00$950.00

Poster Bed

$500.00$650.00

$600.00$525.00

Total Bids

$3,035.00$3,025.00

$3,050.00$3,050.00

Fair Share

$758.75$756.25

$762.50$762.50

Owes to Estate

$241.25$393.75

$87.50 Estate Owes$462.50

Share of Surplus

$65.00$65.00

$65.00$65.00

Final Share

Dining set and pays $176.25 Desk and poster bed and pays$328.75

Wardrobe and pays $22.50 Dresser and gets$527.50

Doug gets the dining set and pays $176.25. Edward gets the desk and poster bed and pays$328.75. Frank gets the wardrobe and pays $22.50. George gets the dresser and$527.50 in cash.

Note that the sum of all the money in the final shares is $0 as it should be. Also note that each player’s final share is worth$65.00 more than the fair share in his eyes.

Example $$\PageIndex{3}$$: Method of Sealed Bids in Dissolving a Partnership

Jack, Kelly and Lisa are partners in a local coffee shop. The partners wish to dissolve the partnership to pursue other interests. Use the method of sealed bids to find a fair division of the business. Jack bids $450,000, Kelly bids$420,000 and Lisa bids $480,000 for the business. Make a table similar to the table for dividing up an estate and follow the same set of steps to solve this problem. Table $$\PageIndex{13}$$: Method of Sealed Bids for Dissolving a Partnership Jack Kelly Lisa Business$450,000

$420,000$480,000

Total Bids

$450,000$420,000

$480,000 Fair Share$150,000

$140,000$160,000

$320,000 Business Owes$150,000

$140,000 Share of Surplus$10,000

$10,000$10,000

Final Share

$160,000 cash$150,000 cash

Business and pays $310,000 Lisa gets the business and pays Jack$160,000 and Kelly $150,000. Method of Markers The method of markers is used to divide up a collection of many objects of roughly the same value. The heirs could use the method of markers to divide up their grandmother’s jewelry collection. The basic idea of the method is to arrange the objects in a line. Then, each player puts markers between the objects dividing the line of objects into distinct parts. Each part is a fair share to that particular player. Based on the placement of the markers, the objects are allotted to the players. If there are players, each player places markers among the objects. We will use notation A1 to represent the first marker for player A, A2 to represent the second marker for player A, and so on. Many times when the players have done all the steps in the method of markers there are some objects left over. If many objects remain, the players can line them up and do the method of markers again. If only a few objects remain, a common approach is to randomly choose an order for the players, then let each player pick an object until all the objects are gone. It is interesting to see that one player may only receive one or two objects while another player may receive four or five objects. The number of objects allotted depends on each player’s value system. First we will look at the allocation of the pieces after the markers have been placed. Once we understand that, we will look at placing the markers in the correct places for each player. Example $$\PageIndex{4}$$: Method of Markers, #1 Three players Albert (A), Bertrand (B), and Charles (C), wish to divide a collection of 15 objects using the method of markers. Determine the final allocation of objects to each player. Since there are three players, each player uses two markers. Let’s start by looking at the line of objects and Albert’s markers. The markers divide the line of objects into three pieces. Each piece of the line is a fair share in Albert’s value system. He would be satisfied with any of the three pieces in the final allocation. For now, do not worry about how Albert determined where to place the markers. We will look at that in Example $$\PageIndex{6}$$. Now let’s add the markers for Bertrand and Charles. Step 1: As you examine the objects from left to right, find the first marker, B1. Give Bertrand all the objects from the beginning of the line to the marker B1. Bertrand removes the rest of his markers and leaves the game for now. Step 2: Now, continuing from left to right, find the first marker out of the second group of markers (A2 and C2). The first marker from this group we come across is A2. Give Albert all the objects from his first marker A1 to his second marker A2. Remember that a fair share is from one marker to the next. Object #4 is not part of Albert’s fair share since it is before his first marker. Albert removes the rest of his markers and leaves the game for now. Step 3: Charles is the only player left in the game. He considers everything from his second marker to the end of the line to be a fair share so give it to him. Any objects not allocated at this point are left over. Step 4: Typically some objects are left over at this point. Objects numbered 4, 9, 10 and 11 are left over in this game. The three players could draw straws to determine an order. Then each player in order would choose an object until all the object are allocated. Note: Normally when we do the method of markers, we only draw the figure once. Summary of the Method of Markers for n players: 1. Arrange the objects in a line. Each of the n players places n-1 markers among the objects. 2. Find the 1st first marker, say A1. Give player A all the objects from the beginning of the line to the 1st first marker. Player A removes his/her remaining markers and leaves the game for now. 3. Find the 1st second marker, say B2. Give player B all the objects from the 1st second marker back to B’s previous marker B1. In other words, all the objects from B1 to B2. Player B removes his/her remaining markers and leaves the game for now. 4. Find the 1st third marker, say C3. Give player C all the objects from the 1st third marker back to C’s previous marker C2. In other words, all the objects from C2 to C3. Player C removes his/her remaining markers and leaves the game for now. 5. Continue this pattern until one player remains. Give the last player all the objects from his/her last marker to the end of the line of objects. 6. Divide up the remaining objects. If many objects remain, do the method of markers again. If only a few objects remain, randomly choose an order then let each player choose an object in order until all the objects are gone. Example $$\PageIndex{5}$$: Method of Markers, #2 Four cousins, Amy, Becky, Connie and Debbie wish to use the method of markers to divide a collection of jewels. The jewels are lined up and the cousins place their markers as shown below in Figure $$\PageIndex{23}$$. What is the final allocation of the jewels? The 1st first marker is C1 so give Connie all the jewels from the beginning of the line to her first marker. Connie removes her remaining markers and leaves the game for now. The 1st second marker is D2 so give Debbie all the jewels between markers D1 and D2. Debbie removes her remaining markers and leaves the game for now. The 1st third marker is a tie between A3 and B3 so randomly choose one. One possibility is to have Amy and Becky toss a coin and the winner gets the next fair share. Assume Becky wins the coin toss. Give Becky all the jewels between markers B2 and B3. Becky removes her remaining markers and leaves the game for now. Amy is the last player in the game. Give Amy all the jewels from her last marker to the end of the line. Jewels numbered 4, 8, and 9 are left over. The players can draw straws to determine an order. Each player, in order, chooses a jewel until all the jewels have been allocated. Example $$\PageIndex{6}$$: Determining Where to Place the Markers Four roommates want to split up a collection of fruit consisting of 8 oranges (O), 8 bananas (B), 4 pears (P), and 4 apples (A). The fruit are lined up as shown below in Figure $$\PageIndex{28}$$. To determine where to place the markers, each player assigns a value to each type of fruit. Jack loves oranges, likes apples and pears equally, but dislikes bananas. He assigns a value of$1 to each apple and each pear, a value of $2 to each orange, and a value of$0 to each banana. In Jack’s value system, the collection of fruit is worth $24. Jack’s fair share is$6. He needs to place his markers so that the fruit is divided into groups worth $6. It can be helpful to work from both ends of the line. Jack has no choice about the placement of his first and third markers. Because he sees the bananas as worth$0 he has three possible places for his second marker. These possibilities are shown below in Figure $$\PageIndex{29}$$ as dotted lines.

Kent dislikes apples and oranges, like bananas and really loves pears. He assigns a value of $0 to each apple or orange, a value of$1 to each banana, and a value of $3 to each pear. In Kent’s value system, the collection of fruit is worth$20. Since there are four players, Kent’s fair share is $5. He needs to place his markers so that the fruit is divided into groups worth$5. Jack has no choice about the placement of his third marker. He has a few possibilities for his first two markers. The possibilities are shown below in Figure $$\PageIndex{30}$$ as dotted lines.

The other two roommates would follow the same process to place their markers. Once all the markers are placed, the allocation by the method of markers begins.

Imagine if the order of the fruit in Example $$\PageIndex{6}$$ was rearranged. It might not be possible for Kent to divide up the line of fruits into groups worth $5. He might have to use a group worth$6 next to a group worth $4. This is a good time to remember that none of our fair division methods are perfect. They work well most of the time but sometimes we just have to make do. If Kent was allocated a group of fruit worth only$4 he might get some of the missing value back when the left over fruits are allocated.