Austin's Algorithm and Adjusted Winner
Results and report are due
at the start of
Wednesday, Feb 4
In lecture, we studied Austin's algorithm,
in which two parties can agree on exactly what is 1/2 of a cake.
In this lab you will program the technique,
apply it to some data, and write a short report about your results.
You are encouraged to work in groups of up to 3 people on this project.
Your group submits just one report, coauthored by all group members.
- Testing: each is 100x100 data points in a CSV file
- Homogeneous Use this same data set for each player's preferences.
- 1/2 chcolate, 1/2 vanilla: same cake but two different views
- Abstract Israel 1000x1000 CSV file
The program you write should simulate Austin's Algorithm. One player will
call stop, receive a second knife and continue moving the knives
as described in lecture until the other player calls stop.
Following are the questions our TA Dave posted in class:
- In the Massoud piece, the author bundles security and boundaries and shows how the allocation and final pay-offs would differ. What other issues might be bundled, and how would it affect the division and welfare of the two sides?
- In the real world, two sides are often not aiming for a strictly equitable outcome. A common example is in the settlement of a divorce, the two sides may have to find a 60/40 split. How would the allocation change if, say, Israel has greater bargaining power and the division is not equitable but rather it is predetermined that Israel should fare better and receive 1.5 times the points that Palestine receives (a 60/40 split)?
- How would you change the adjusted winner algorithm to accommodate a third player? Imagine a separatist Israeli group that has some claim over the contested land was given a seat at the bargaining table. Which axiom(s) would your new algorithm violate (envy-freeness, efficiency, equitability)?
- How would the algorithm change if the issues were not independent? For example, Palestinians might value allowing Palestinian refugees' right of return, but if Palestine were granted both sovereignty and control of the occupied territory, the issue would be moot. Can the procedure be adjusted to allow for changing preferences as certain issues are won/lost? In other words, how would the algorithm account for non-additive preferences?
- How does introducing indivisibility into certain issues affect the final outcome? Which axiom(s) might the algorithm violate?
- Massoud briefly mentions variation in the survey responses across issues. How robust is the final allocation of items to slight variations in the point totals reported by the two sides? You can play with the Massoud example to answer the question.
- The AW procedure (naively) assumes honesty between the players. If one side has privileged information, what would their best strategy be? What if both sides have a knowledge of how the other player will value issues? What would their optimal strategy be? Is there an equilibrium? To answer this example, try playing with the 2-person, 3-good divorce example given in lecture.
For now, look these over with the idea of picking one that you will think about
between now and Wednesday February 4. Look below to see what we would
like to get from
you in your write-up.
Report (due Feb 4, start of class)
Write between 2-5 pages describing the results you have seen. In your
report, include the following:
- The names of the people in your group
- Reponses to the following:
For each of the cakes:
describe the results of your application of Austin's algorithm.
- How close was your solution to being equitable?
- How dependent was your result on the knife-moving direction?
- Adjusted Winner
- Which question did your group consider?
- What approach do you propose to find answers to the question?
You do not need to have working code yet to obtain answers. We want
to see the approach you would take to address the question.
Last modified 06:22:04 CST 30 January 2015