Fair Division in Theory and Practice
[CSE/Poli Sci 245A (Spring 2015)]

Austin's Algorithm and Adjusted Winner

Results and report are due
at the start of class on
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.



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.

Adjusted Winner

Following are the questions our TA Dave posted in class:
  1. 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?
  2. 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)?
  3. 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)?
  4. 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?
  5. How does introducing indivisibility into certain issues affect the final outcome? Which axiom(s) might the algorithm violate?
  6. 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.
  7. 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:

Last modified 06:22:04 CST 30 January 2015