The Efficiency of Fair Division

1. Anshelevich, E., Dasgupta, A., Kleinberg, J.M., Tardos, E., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. SIAM J. Comput. 38(4), 1602–1623 (2008)

   Article  MathSciNet  MATH  Google Scholar 

2. Asadpour, A., Saberi, A.: An approximation algorithm for max-min fair allocation of indivisible goods. SIAM J. Comput. 39(7), 2970–2989 (2010)

   Article  MathSciNet  MATH  Google Scholar 

3. Aumann, Y., Dombb, Y.: The efficiency of fair division with connected pieces. In: Proceedings of the 6th International Workshop on Internet and Network Economics (WINE’10). LNCS, vol. 6484. Springer, Berlin, pp. 26–37 (2010)

   Google Scholar 

4. Bansal, N., Sviridenko, M.: The Santa Claus problem. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC ’06), pp. 31–40 (2006)

   Chapter  Google Scholar 

5. Bateni, M., Charikar, M., Guruswami, V.: Maxmin allocation via degree lower-bounded arborescences. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC ’09), pp. 543–552 (2009)

   Chapter  Google Scholar 

6. Bezáková, I., Dani, V.: Allocating indivisible goods. SIGecom Exch. 5(3), 11–18 (2005)

   Article  Google Scholar 

7. Bouveret, S., Lang, J.: Efficiency and envy-freeness in fair division of indivisible goods: Logical representation and complexity. J. Artif. Intell. Res. 32, 525–564 (2008)

   MathSciNet  MATH  Google Scholar 

8. Brams, S.J., Taylor, A.D.: An envy-free cake division protocol. Am. Math. Mon. 102(1), 9–18 (1995)

   Article  MathSciNet  MATH  Google Scholar 

9. Brams, S.J., Taylor, A.D.: Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press, Cambridge (1996)

   Book  MATH  Google Scholar 

10. Brams, S.J., Taylor, A.D., Zwicker, W.S.: A moving-knife solution to the four-person envy free cake division problem. Proc. Am. Math. Soc. 125(2), 547–554 (1997)

    Article  MathSciNet  MATH  Google Scholar 

11. Buchbinder, N., Naor, J.: Fair online load balancing. In: Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA ’06), pp. 291–298 (2006)

    Chapter  Google Scholar 

12. Chakrabarty, D., Chuzhoy, J., Khanna, S.: On allocating goods to maximize fairness. In: Proceedings of the 50th Annual Symposium on Foundations of Computer Science (FOCS ’09), pp. 107–116 (2009)

    Google Scholar 

13. Chevaleyre, Y., Endriss, U., Estivie, S., Maudet, N.: Reaching envy-free states in distributed negotiation settings. In: Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI ’07), pp. 1239–1244 (2007)

    Google Scholar 

14. Chevaleyre, Y., Endriss, U., Maudet, N.: Allocating goods on a graph to eliminate envy. In: Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI ’07), pp. 700–705 (2007)

    Google Scholar 

15. Deng, X., Qi, Q., Saberi, A.: On the complexity of envy-free cake cutting. Manuscript, arXiv:0907.1334 [cs.GT] (2009)

16. Edmonds, J., Pruhs, K.: Cake-cutting really is not a piece of cake. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’06), pp. 271–278 (2006)

    Chapter  Google Scholar 

17. Even, S., Paz, A.: A note on cake-cutting. Discrete Appl. Math. 7, 285–296 (1984)

    Article  MathSciNet  MATH  Google Scholar 

18. Golovin, D.: Max-min fair allocation of indivisible goods. Technical Report, Carnegie Mellon University, CMU-CS-05-144, (2005)

19. Kleinberg, J., Rabani, Y., Tardos, E.: Fairness in routing and load balancing. J. Comput. Syst. Sci. 63(1), 2–20 (2001)

    Article  MathSciNet  MATH  Google Scholar 

20. Kumar, A., Kleinberg, J.: Fairness measures for resource allocation. SIAM J. Comput. 36(3), 657–680 (2006)

    Article  MathSciNet  MATH  Google Scholar 

21. Lenstra, J.K., Shmoys, D.B., Tardos, E.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46, 259–271 (1990)

    Article  MathSciNet  MATH  Google Scholar 

22. Lipton, R., Markakis, E., Mossel, E., Saberi, A.: On approximately fair allocations of indivisible goods. In: Proceedings of the 5th ACM Conference on Electronic Commerce (EC ’04), pp. 125–131 (2004)

    Chapter  Google Scholar 

23. Magdon-Ismail, M., Busch, C., Krishnamoorthy, M.S.: Cake-cutting is not a piece of cake. In: Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS ’03), LNCS, vol. 2607, pp. 596–607. Springer, Berlin (2003)

    Google Scholar 

24. Procaccia, A.: Thou shalt covet thy neighbor’s cake. In: Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI ’09), pp. 239–244 (2009)

    Google Scholar 

25. Robertson, J.M., Webb, W.A.: Cake-Cutting Algorithms: Be Fair if You Can. AK Peters Ltd, Wellesley (1998)

    MATH  Google Scholar 

26. Saberi, A., Wang, Y.: Cutting a cake for five people. In: Proceedings of the 5th International Conference on Algorithmic Aspects in Information and Management (AAIM ’09), pp. 292–300 (2009)

    Chapter  Google Scholar 

27. Steinhaus, H.: The problem of fair division. Econometrica 16, 101–104 (1948)

    Google Scholar 

28. Stromquist, W.: How to cut a cake fairly. Am. Math. Mon. 87(8), 640–644 (1980)

    Article  MathSciNet  MATH  Google Scholar 

29. Stromquist, W.: Envy-free cake divisions cannot be found by finite protocols. Electron. J. Comb. 15, R11 (2008)

    MathSciNet  Google Scholar 

30. Tadenuma, K., Thomson, W.: The fair allocation of an indivisible good when monetary compensations are possible. Math. Soc. Sci. 25(2), 117–132 (1993)

    Article  MathSciNet  MATH  Google Scholar 

31. Woeginger, G.J., Sgall, J.: On the complexity of cake-cutting. Discrete Optim. 4, 213–220 (2007)

    Article  MathSciNet  MATH  Google Scholar 

Download references