5.9: Exercise-2- Exploration

Last updated
Save as PDF

Page ID: 37764

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

1. This question explores how bidding dishonestly can end up hurting the cheater. Four partners are dividing a million-dollar property using the lone-divider method. Using a map, Danny divides the property into four parcels $s_1$, $s_2$, $s_3$, and $s_4$. The following table shows the value of the four parcels in the eyes of each partner (in thousands of dollars):

$\begin{array}{|c|l|l|l|l|}
\hline & \mathrm{s}_{1} & \mathrm{s}_{2} & \mathrm{s}_{3} & \mathrm{s}_{4} \\
\hline \textbf { Danny } & \$ 250 & \$ 250 & \$ 250 & \$ 250 \\
\hline \textbf { Brianna } & \$ 460 & \$ 180 & \$ 200 & \$ 160 \\
\hline \textbf { Carlos } & \$ 260 & \$ 310 & \$ 220 & \$ 210 \\
\hline \textbf { Greedy } & \$ 330 & \$ 300 & \$ 270 & \$ 100 \\
\hline
\end{array}$

Assuming all players bid honestly, which piece will Greedy receive?
Assume Brianna and Carlos bid honestly, but Greedy decides to bid only for s1, figuring that doing so will get him s1. In this case there is a standoff between Brianna and Greedy. Since Danny and Carlos are not part of the standoff, they can receive their fair shares. Suppose Danny gets s3 and Carlos gets s2, and the remaining pieces are put back together and Brianna and Greedy will split them using the basic divider-chooser method. If Greedy gets selected to be the divider, what will be the value of the piece he receives?
Extension: Create a Sealed Bids scenario that shows that sometimes a player can successfully cheat and increase the value they receive by increasing their bid on an item, but if they increase it too much, they could end up receiving less than their fair share.

Explain why divider-chooser method with two players will always result in an envy-free division.

Will the lone divider method always result in an envy-free division? If not, will it ever result in an envy-free division?

The Selfridge-Conway method is an envy-free division method for three players. Research how the method works and prepare a demonstration for the class.

Suppose that two people are dividing a $12 pizza that is half pepperoni, half cheese. Steve likes both equally, but Maria likes cheese twice as much as pepperoni. As divider, Steve divides the pizza so that one piece is 1/3 cheese and 2/3 pepperoni, and the second piece is 1/3 pepperoni and 2/3 cheese.
1. Describe the value of each piece to each player
2. Since the value to each player is not the same, this division is not equitable. Find a division that would be equitable. Is it still envy-free?
3. The original division is not Pareto optimal. To show this, find another division that would increase the value to one player without decreasing the value to the other player. Is this division still envy-free?
4. Would it be possible with this set of preferences to find a division that is both equitable and Pareto optimal? If so, find it. If not, explain why.

Is the Sealed Bids method Pareto optimal when used with two players? If not, can you adjust the method to be so?

Is the Sealed Bids method envy-free when used with two players? If not, can you adjust the method to be so?

Is the Sealed Bids method equitable when used with two players? If not, can you adjust the method to be so?

All the problems we have looked at in this chapter have assumed that all participants receive an equal share of what is being divided. Often, this does not occur in real life. Suppose Fred and Maria are going to divide a cake using the divider-chooser method. However, Fred is only entitled to 30% of the cake, and Maria is entitled to 70% of the cake (maybe it was a $10 cake, and Fred put in $3 and Maria put in $7). Adapt the divider-choose method to allow them to divide the cake fairly.

Assume (as we have throughout this chapter) that different parts of the cake may have different values to Fred and Maria, and that they don't communicate their preferences/values with each other. You goal is to come up with a method of fair division, meaning that although the participants may not receive equal shares, they should be guaranteed their fair share. Your method needs to be designed so that each person will always be guaranteed a share that they value as being worth at least as much as they're entitled to.

The last few questions will be based on the Adjusted Winner method, described here:

For discrete division between two players, there is a method called Adjusted Winner that produces an outcome that is always equitable, envy-free, and Pareto optimal. It does, however, require that items can be split or shared. The method works like this:

1) Each player gets 100 points that they assign to the items to be divided based on their relative worth.

2) In the initial allocation, each item is given to the party that assigned it more points. If there were any items with both parties assigned the same number of points, they’d go to the person with the fewest points so far.

3) If the assigned point values are not equal, then begin transferring items from the person with more points to the person with fewer points. Start with the items that have the smallest point ratio, calculated as (higher valuation/lower valuation).

4) If transferring an entire item would move too many points, only transfer a portion of the item.

Example: A couple is attempting to settle a contentious divorce[1]. They assign their 100 points to the issues in contention:

$\begin{array}{|l|l|l|}
\hline & \textbf { Mike } & \textbf { Carol } \\
\hline \textbf { Custody of children } & 25 & 65 \\
\hline \textbf { Alimony } & 60 & 25 \\
\hline \textbf { House } & 15 & 10 \\
\hline
\end{array}$

In the initial allocation, Mike gets his way on alimony and house, and Carol gets custody of the children. In the initial allocation, Mike has 75 points and Carol has 65 points. To decide what to transfer, we calculate the point ratios.

$\begin{array}{|l|l|l|l|}
\hline & \textbf { Mike } & \textbf { Carol } & \textbf { Point ratio } \\
\hline \textbf { Custody of children } & 25 & 65 & 65 / 25=2.6 \\
\hline \textbf { Alimony } & 60 & 25 & 60 / 25=2.4 \\
\hline \textbf { House } & 15 & 10 & 15 / 10=1.5 \\
\hline
\end{array}$

Since the house has the smallest point ratio, the house will be the item we work with first. Since transferring the entire house would give Carol too many points, we instead need to transfer some fraction, $p$, of the house to that Carol and Mike will end up with the same point values. If Carol receives a fraction $p$ of the house, then Mike will give up $(1-p)$ of the house. The value Carol will receive is $10p$: the fraction $p$ of the 10 points Carol values the house at. The value Mike will get is $15(1-p)$. We set their point totals equal to solve for $p$:

$\begin{array} {lll} 65+10 p & = & 60+15(1-p) \\ 65+10 p & = & 60+15-15 p \\ 25 p & = & 10 \\ \end{array}$

Where $p=10 / 25=0.4=40 \%$. So Carol should receive 40% of the house.

Apply the Adjusted Winner method to settle a divorce where the couples have assigned the point values below

$\begin{array}{|l|l|l|}
\hline & \textbf { Sandra } & \textbf { Kenny } \\
\hline \textbf { Home } & 20 & 30 \\
\hline \textbf { Summer home } & 15 & 10 \\
\hline \textbf { Retirement account } & 50 & 40 \\
\hline \textbf { Investments } & 10 & 10 \\
\hline \textbf { Other } & 5 & 10 \\
\hline
\end{array}$

In 1974, the United States and Panama negotiated over US involvement and interests in the Panama Canal. Suppose that these were the issues and point values assigned by each side[2]. Apply the Adjusted Winner method.

$\begin{array}{|l|l|l|}
\hline & \textbf { United States } & \textbf { Panama } \\
\hline \textbf { US defense rights } & 22 & 9 \\
\hline \textbf { Use rights } & 22 & 15 \\
\hline \textbf { Land and water } & 15 & 15 \\
\hline \textbf { Expansion rights } & 14 & 3 \\
\hline \textbf { Duration } & 11 & 15 \\
\hline \textbf { Expansion routes } & 6 & 5 \\
\hline \textbf { Jurisdiction } & 2 & 7 \\
\hline \textbf { US military rights } & 2 & 7 \\
\hline \textbf { Defense role of Panama } & 2 & 13 \\
\hline
\end{array}$

[1] From Negotiating to Settlement in Divorce, 1987

[2] Taken from The Art and Science of Negotiation, 1982