5.5: Last Diminisher

Last updated
Save as PDF

Page ID: 34201

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

The Last Diminisher method is another approach to division among 3 or more parties.

Last Diminisher Method

In this method, the parties are randomly assigned an order, perhaps by pulling names out of a hat. The method then proceeds as follows:

1) The first person cuts a slice they value as a fair share.

2) The second person examines the piece

a. If they think it is worth less than a fair share, they then pass on the piece unchanged.

b. If they think the piece is worth more than a fair share, they trim off the excess and lay claim to the piece. The trimmings are added back into the to-be-divided pile.

3) Each remaining person, in turn, can either pass or trim the piece

4) After the last person has made their decision, the last person to trim the slice receives it. If no one has modified the slice, then the person who cut it receives it.

5) Whoever receives the piece leaves with their piece and the process repeats with the remaining people. Continue until only 2 people remain; they can divide what is left with the divider-chooser method.

Example 8

Suppose that four salespeople are dividing up Washington State into sales regions; each will get one region to work in. They pull names from a hat to decide play order.

Solution

$A picture of the state of Washington with a large area around Seattle colored in yellow.$ Round 1. The first salesman, Bob, draws a region around Seattle, the most populous area of the state. The piece Bob cuts and automatically lays claim to is shown in yellow.

$A picture of the state of Washington with a large area around Seattle colored in yellow, and a smaller area inside of it colored in pink.$ The second salesman, Henry, felt that this region was worth more than 25%, each player’s fair share. Because of this, Henry opts to trim this piece. The new piece is shown in pink. The trimmings (in yellow) return to the to-be-divided portion of the state. Henry automatically lays claim to this smaller piece since he trimmed it.

The third saleswoman, Marjo, feels this piece is worth less than 25% and passes, as does the fourth saleswoman, Beth. Since both pass, the last person to trim it, Henry, receives the piece.

$A picture of the state of Washington with small area around Seattle colored in pink, and a new larger area around it colored in Yellow.$ Round 2. The second round begins with Bob laying claim to a piece, shown again in yellow. Henry already has a piece, so is out of the process now. Marjo passes on this piece, feeling it is worth less than a fair share.

$A picture of the state of Washington with small area around Seattle colored in pink, a larger area around it colored in yellow, and an area barely smaller than the yellow colored in blue.$ Beth, on the other hand, feels the piece as currently drawn is worth 35%. Beth is in an advantageous position, being the last to make a decision. Even though Beth values this piece at 35%, she can cut a very small amount and still lay claim to it. So Beth barely cuts the piece, resulting in a piece (blue) that is essentially worth 35% to her. Since she is the last to trim, she receives the piece.

$A picture of the state of Washington with small area around Seattle colored in pink, a larger area around it colored in blue, with the rest of the state divided in the middle by a vertical line, the left shaded orange the right shaded yellow.$ Round 3. At this point, Bob and Marjo are the only players without a piece. Since there are two of them, they can finish the division using the divider-chooser method. They flip a coin, and determine that Marjo will be the divider. Marjo draws a line dividing the remainder of the state into two pieces. Bob chooses the Eastern piece, leaving Marjo with the Western half.

Notice that in this division, Henry and Marjo ended up with pieces that they feel are worth exactly 25% - a fair share. Beth was able to receive a piece she values as more than a fair share, and Bob may feel the piece he received is worth more than 25%.

Example 9

Marcus, Abby, Julian, and Ben are splitting a pizza that is 4 slices of cheese and 4 slices of veggie with total value $12. Marcus and Ben like both flavors equally, Abby only likes cheese, and Julian likes veggie twice as much as cheese. They divide the pizza using last diminisher method, playing in the order Marcus, Abby, Ben, then Julian.

Solution

Notice Ben and Marcus both value any slice of pizza at $1.50.

Abby values each slice of cheese at $3, and veggie at $0.

Julian values each slice of cheese at $1, and each slice of veggie at $2. (see Example 2)

A fair share for any player is $3.

In the first round, suppose Marcus cuts out 2 slices of cheese, which he values at $3.

Abby only likes cheese, so will value this cut at $6. She will trim it to 1 slice of cheese, which she values as her fair share of $3.

Ben will view this piece as less than a fair share, and will pass.

Julian will view this piece as less than a fair share, and will pass.

Abby receives the piece.

In the second round, suppose Marcus cuts a slice that is 2 slices of veggie.

Abby already received a slice so is out.

Ben will view this piece as having value $3. He can barely trim it and lay claim to it.

Julian will value this piece as having value $4, so will barely trim it and claim it.

Marcus and Ben can then split the remaining 3 slices of cheese and 2 slices of veggie using the divider-chooser method.

In the second round, both Ben and Julian will make tiny trims (pulling off a small crumb) in order to lay claim to the piece without practically reducing the value. The piece Julian receives is still essentially worth $4 to him; we don’t worry about the value of that crumb.

Try it Now 5

Five players are dividing a $20 cake. In the first round, Player 1 makes the initial cut and claims the piece. For each of the remaining players, the value of the current piece (which may have been trimmed) at the time it is their turn is shown below. Describe the outcome of the first round.

$\begin{array}{|l|l|l|l|l|}
\hline & \mathbf{P}_{2} & \mathbf{P}_{3} & \mathbf{P}_{4} & \mathbf{P}_{5} \\
\hline \begin{array}{l}
\text { Value of the } \\
\text { current piece }
\end{array} & \$ 3 & \$ 5 & \$ 3.50 & \$ 3 \\
\hline
\end{array}$

In the second round, Player 1 again makes the initial cut and claims the piece, and the current values are shown again. Describe the outcome of the second round.

$\begin{array}{|l|l|l|l|}
\hline & \mathbf{P}_{2} & \mathbf{P}_{4} & \mathbf{P}_{5} \\
\hline \begin{array}{l}
\text { Value of the } \\
\text { current piece }
\end{array} & \$ 7 & \$ 3 & \$ 5 \\
\hline
\end{array}$

Answer

In the first round, Player 1 will cut a piece he values as a fair share of $4. Player 2 values the piece as $3, so will pass. Player 3 values the piece as $5, so will claim it and trim it to something she values as $4. Player 4 receives that piece and values it as $3.50 so will pass. Player 5 values the piece at $3 and will also pass. Player 3 receives the trimmed piece she values at $4.

In the second round, Player 1 will again cut a piece he values as a fair share of $4. Player 2 values the piece as $7, so will claim it and trim it to something he values as $4. Player 4 values the trimmed piece at $3 and passes. Player 5 values the piece at $5, so will claim it. Since Player 5 is the last player, she has an advantage and can claim then barely trim the piece. Player 5 receives a piece she values at $5.