Fairness of Multi-Resource Allocations

homeimgDefinitionlinkDifferentviewslinkMultiresourcelinkInpracticelinkParticipatelinkFurtherinfolink

 

Different Views on Fairness

The list below is an overview of works on fairness for resource allocations. We've focused on research related to computer networks (as we are most familiar with those) but have also included works from other fields. No such list could hope to cover all works on fairness, but we have tried to be reasonably comprehensive. If you know of something we missed, let us know and we will include it!

We have divided the references here into several sections in order to make it easier to look through the papers--some papers, however, may belong in more than one section.

A note about hyperlinking: when available, we have tried to include links to a free online version. In some cases, though, this was not available.

Knapsack Problems

In the context of fairness, the constraints of a multi-dimensional knapsack problem may be viewed as constraints on the capacity of multiple non-substitutable resources (e.g., apples and oranges, or CPU and bandwidth). The knapsack packing problem of fitting items of different shapes into the multi-dimensional knapsack can then be viewed as a discrete resource allocation problem, as explained in Appendix E here.

  1. K. Bretthauer and B. Shetty, “The nonlinear knapsack problem- algorithms and applications,” European Journal of Operational Research, vol. 138, no. 3, pp. 459–472, 2002.
  2. P. Chu and J. Beasley, “A genetic algorithm for the multidimensional knapsack problem,” Journal of Heuristics, vol. 4, no. 1, pp. 63–86, 1998.
  3. J. Dussault, J. Ferland, and B. Lemaire, “Convex-quadratic programming with one constraint and bounded variables,” Mathematical Programming, vol. 36, no. 1, pp. 90–104, 1986.
  4. A. Fréville, “The multidimensional 0–1 knapsack problem: An overview,” European Journal of Operational Research, vol. 155, no. 1, pp. 1–21, 2004.
  5. G. Gallo, P. Hammer, and B. Simeone, “Quadratic knapsack problems,” Combinatorial Optimization, vol. 12, pp. 132–149, 1980.
  6. T. Klastorin, “On a discrete nonlinear and nonseparable knapsack problem,” Operations Research Letters, vol. 9, no. 4, pp. 233–237, 1990.
  7. M. Magazine and M. Chern, “A note on approximation schemes for multidimensional knapsack problems,” Mathematics of Operations Research, pp. 244–247, 1984.
  8. T. Morin and R. Marsten, “An algorithm for nonlinear knapsack problems,” Management Science, vol. 22, no. 10, pp. 1147–1158, 1976.
  9. M. Moser, D. Jokanovic, and N. Shiratori, “An algorithm for the multi-dimensional multiple-choice knapsack problem,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. 80, no. 3, pp. 582–589, 1997.
  10. T. Sharkey, H. Romeijn, and J. Geunes, “A class of nonlinear nonseparable continuous knapsack and multiple-choice knapsack problems,” Mathematical Programming, vol. 126, no. 1, pp. 69–96, 2011.
  11. M. Vasquez, J. Hao et al., “A hybrid approach for the 0-1 multidimensional knapsack problem,” in International Joint Conference on Artificial Intelligence, vol. 17, no. 1. Lawrence Erlbaum Associates Ltd., 2001, pp. 328–333.
  12. H. Weingartner and D. Ness, “Methods for the solution of the multidimensional 0/1 knapsack problem,” Operations Research, vol. 15, no. 1, pp. 83–103, 1967.

Cake-Cutting and Fair Division

The cake-cutting problem, also known as "fair division," is a multi-resource allocation problem that takes into account different user preferences. Most of the research on this problem has been focused towards finding algorithms to compute a "fair" solution.

  1. A. Abdulkadiroglu, T. Sönmez, and M. U. Ünever, "Room assignment-rent division: A market approach," Social Choice and Welfare, vol. 22, no. 3, pp. 515-538, 2004.
  2. S. J. Brams and P. C. Fishburn, "Fair division of indivisible items between two people with identical preferences: Envy-freeness, Pareto-optimality, and equity," Social Choice and Welfare, vol. 17, no. 2, pp. 247-267, 2000.
  3. S. J. Brams, M. A. Jones, and C. Klamler, “Better ways to cut a cake,” Notices of the AMS, vol. 53, no. 11, pp. 1314–1321, 2006.
  4. S. J. Brams and D. L. King, “Efficient fair division: Help the worst off or avoid envy?Rationality and Society, vol. 17, no. 4, pp. 387-421, 2005.
  5. S. J. Brams and A. D. Taylor, Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press, 1996.
  6. P. Edelman and P. Fishburn, “Fair division of indivisible items among people with similar preferences,” Mathematical Social Sciences, vol. 41, no. 3, pp. 327-347, 2001.
  7. D. Herreiner and C. Puppe, “A simple procedure for finding equitable allocations of indivisible goods,” Social Choice and Welfare, vol. 19, no. 2, pp. 415-430, 2002.
  8. C.-J. Haake, M. G. Raith and F. E. Su, “Bidding for envy-freeness: A procedural approach to n-player fair-division problems,” Social Choice and Welfare, vol. 19, no. 4, pp. 723-749, 2002.
  9. F. E. Su, “Rental harmony: Sperner's Lemma in fair division,” The American Mathematical Monthly, vol. 106, no. 10, pp. 930-942, 1999.

Network Resource Allocation

Fairness in network resource allocation has traditionally focused on bandwidth allocation in linked networks, though there has also been considerable research on, e.g., radio allocation in wireless networks. In another example, fair scheduling incorporates the time-dimension of resource availability. Some of these fairness theories can be applied to generic "resources," while others are more scenario-specific.

  1. S. K. Baruah, N. K. Cohen, C. G. Plaxton, and D. A. Varvel, “Proportionate progress: A notion of fairness in resource allocation,” Algorithmica, vol. 15, no. 6, pp. 600–625, 1996.
  2. T. Bonald and L. Massoulié, “Impact of fairness on Internet performance,” in ACM SIGMETRICS Performance Evaluation Review, vol. 29, no. 1. ACM, 2001, pp. 82–91.
  3. M. Bredel and M. Fidler, “Understanding fairness and its impact on quality of service in IEEE 802.11,” in Proceedings of IEEE INFOCOM. IEEE, 2009, pp. 1098–1106.
  4. M. Dianati, X. Shen, and S. Naik, “A new fairness index for radio resource allocation in wireless networks,” in Proceedings of the 2005 IEEE Wireless Communications and Networking Conference, vol. 2. IEEE, 2005, pp. 712–717.
  5. A. Ghodsi, M. Zaharia, B. Hindman, A. Konwinski, S. Shenker, and I. Stoica, “Dominant resource fairness: Fair allocation of multiple resource types,” in Proceedings of the 8th USENIX NSDI. USENIX Association, 2011, pp. 24–37.
  6. Z. Han, Z. Ji, and K. J. R. Liu, "Fair Multiuser Channel Allocation for OFDMA Networks using Nash bargaining solutions and coalitions," IEEE Transactions on Communications, vol. 53, no. 8, pp. 1366-1376, 2005.
  7. R. Jain, D .M. Chiu, and W. R. Hawe, A quantitative measure of fairness and discrimination for resource allocation in shared computer system. Eastern Research Laboratory, Digital Equipment Corp., 1984.
  8. C. Joe-Wong, S. Sen, T. Lan, and M. Chiang, “Multi-resource allocation: Fairness-efficiency tradeoffs in a unifying framework,” Proceedings of IEEE INFOCOM. IEEE, 2012, pp. 1206-1214.
  9. F. P. Kelly, A. K. Maulloo, and D. K. H. Tan, “Rate control for communication networks: Shadow prices, proportional fairness and stability,” The Journal of the Operational Research Society, vol. 49, no. 3, pp. 237–252, 1998.
  10. C. E. Koksal, H. Kassab, and H. Balakrishnan, “An analysis of short-term fairness in wireless media access protocols (poster session),” ACM SIGMETRICS Performance Evaluation Review, vol. 28, no. 1, pp. 118–119, 2000.
  11. A. Kumar and J. Kleinberg, “Fairness measures for resource allocation,” in Proceedings of IEEE FOCS. IEEE, 2000, pp. 75-85.
  12. T. Lan and M. Chiang, “An axiomatic theory of fairness in resource allocation,” George Washington University, , Tech. Rep., 2011.
  13. T. Lan, D. Kao, M. Chiang, and A. Sabharwal, “An axiomatic theory of fairness in network resource allocation,” in Proceedings of IEEE INFOCOM. IEEE, 2010, pp. 1–9.
  14. M. Marsan and M. Gerla, “Fairness in local computing networks,” Proceedings of IEEE ICC, 1982.
  15. L. Massoulié and J. Roberts, “Bandwidth sharing: Objectives and algorithms,” IEEE/ACM Transactions on Networking, vol. 10, no. 3, pp. 320–328, 2002.
  16. R. Mazumdar, L. G. Mason, and C. Douligeris, “Fairness in network optimal flow control: Optimality of product forms,” IEEE Transactions on Communications, vol. 39, no. 5, pp. 775–782, 1991.
  17. J. Mo and J. Walrand, “Fair end-to-end window-based congestion control,” IEEE/ACM Transactions on Networking, vol. 8, no. 5, pp. 556–567, 2000.
  18. A. Odlyzko, “Network neutrality, search neutrality, and then ever-ending conflict between efficiency and fairness in markets,” in Review of Network Economics, vol. 8, no. 1, March 2009, pp. 40–60.
  19. R. Srinivasan and A. K. Somani, “On achieving fairness and efficiency in high-speed shared medium access,” IEEE/ACM Transactions on Networking, vol. 11, no. 1, pp. 111–124, 2003.
  20. A. Tang, J. Wang, and S. H. Low, “Counter-intuitive throughput behaviors in networks under end-to-end control,” IEEE/ACM Transactions on Networking, vol. 14, no. 2, pp. 355–368, 2006.
  21. M. Uchida and J. Kurose, “An information-theoretic characterization of weighted alpha-proportional fairness,” in Proceedings of IEEE INFOCOM. IEEE, 2009, pp. 1053–1061.
  22. J. Wong, J. Sauve, and J. Field, “A study of fairness in packet-switching networks,” IEEE Transactions on Communications, vol. 30, no. 2, pp. 346–353, 1982.
  23. Y. Yang and H. Casanova, “Rumr: Robust scheduling for divisible workloads,” in Proceedings of the 12th IEEE Symposium on High Performance and Distributed Computing. IEEE, 2003.
  24. M. Zaharia, D. Borthakur, J. Sen Sarma, K. Elmeleegy, S. Shenker, and I. Stoica, “Delay scheduling: A simple technique for achieving locality and fairness in cluster scheduling,” in Proceedings of the 5th European Conference on Computer Systems. ACM, 2010, pp. 265–278.
  25. Y. Zhou and H. Sethu, “On achieving fairness in the joint allocation of buffer and bandwidth resources: Principles and algorithms,” Computer Networks, vol. 50, no. 13, pp. 2239-2254, 2006.
  26. Y. Zhou and H. Sethu, “On achieving fairness in the joint allocation of processing and bandwidth resources: Principles and algorithms,” IEEE/ACM Transactions on Networking, vol. 13, no. 5, pp. 1054-1067, 2005.
  27. M. Zukerman, L. Tan, H. Wang, and I. Ouveysi, “Efficiency-fairness tradeoff in telecommunication networks,” IEEE Communications Letters, vol. 9, no. 7, pp. 643–645, 2005.

Theories from Economics and Sociology

Many of these works introduce axiomatic definitions of fairness, which tend to be applicable to general resource distributions. Some of these works, however, often focus on distributions of income or wealth. Most of the axioms in the fairness definitions are similar, though an "axiom" of one theory may often be a "property" of another.

  1. R. Aaberge, “Axiomatic characterization of the Gini coefficient and Lorenz curve orderings,” Journal of Economic Theory, vol. 101, no. 1, pp. 115–132, 2001.
  2. K. J. Arrow, “The theory of risk aversion,” Essays in the theory of risk- bearing, pp. 90–120, 1971.
  3. A. B. Atkinson, “On the measurement of inequality,” Journal of Economic Theory, vol. 2, no. 3, pp. 244–263, 1970.
  4. D. K. Fadeev, “Zum Begriff der Entropie einer endlichen Wahrschein-lichkeitsschemas,” in Arbeiten zur Informationstheorie I. Deutscher Verlag der Wissenschaften, 1957, pp. 85–90.
  5. J. F. Nash, “The bargaining problem,” Econometrica, vol. 18, no. 2, pp. 155–162, 1950.
  6. A. Renyi, “On measures of entropy and information,” in Fourth Berkeley Symposium on Mathematical Statistics and Probability, 1961, pp. 547–561.
  7. L. S. Shapley, "A Value for n-Person Games," in Contributions to the Theory of Games, Volume II. Princeton, NJ: Princeton University Press, 1953, pp. 307–317, Annals of Mathematical Studies, vol. 28.
  8. H. Varian, “Equity, envy, and efficiency,” Journal of Economic Theory, vol. 9, no. 1, pp. 63–91, 1974.

Political Theories of Fairness

In a political context, the fairness of resource distributions is often viewed as a form of justice. Political works on fairness tend to be less mathematical and more philosophical, but some political principles (e.g., John Rawls' "justice as fairness") may be translated into mathematical axioms. (This section is perhaps the least comprehensive, due to the vast literature on political philosophy.)

  1. S. Brams, P. Edelman, and P. Fishburn, “Paradoxes of fair division,” The Journal of Philosophy, vol. 98, no. 6, pp. 300–314, 2001.
  2. S. C. Kolm, Justice and Equity. MIT Press, 1970, Trans. See, H. F.
  3. J. Rawls, A Theory of Justice. Cambridge, MA: Harvard University Press, 1971.
  4. J. Rawls and E. Kelly, Justice as Fairness: A Restatement. Belknap Press, 2001.
  5. A. Sen and W. Bernard, Utilitarianism and Beyond. Cambridge University Press, 1982.