Multicriteria models for fair resource allocation

• Autorzy: Ogryczak W.
• Języki publikacji: EN

Abstrakty

EN

Resource allocation problems are concerned with the allocation of limited resources among competing activities so as to achieve the best performances. However, in systems which serve many users there is a need to respect some fairness rules while looking for the overall efficiency. The so-called Max-Min Fairness is widely used to meet these goals. However, allocating the resource to optimize the worst performance may cause dramatic worsening of the overall system efficiency. Therefore, several other fair allocation schemes are being considered and analyzed. In this paper we show how the concepts of multiple criteria equitable optimization can effectively be used to generate various fair and efficient allocation schemes. First, we demonstrate how the scalar inequality measures can be consistently used in bicriteria models to search for fair and efficient allocations. Further, two alternative multiple criteria models equivalent to equitable optimization are introduced, thus allowing to generate a larger variety of fair and efficient resource allocation schemes.

Słowa kluczowe

EN

multiple criteria optimization; efficiency; fairness; equity; inequality measures

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2007
• Tom: Vol. 36, no 2
• Strony: 303--332
• Opis fizyczny: Bibliogr. 46 poz., wykr.

Twórcy

autor

Ogryczak W.

• Warsaw University of Technology, Institute of Control and Computation Engineering, Nowowiejska 15/19, 00-665 Warsaw, Poland,

Bibliografia

• ATKINSON, A.B. (1970) On the Measurement of Inequality. J. of Economic Theory 2, 244-263.
• DALTON, H. (1920) The Measurement of the Inequality of Income. Economic Journal 30, 348-361.
• DENDA, R., BANCHS, A. and EFFELSBERG, W. (2000) The Fairness Challenge in Computer Networks. Lect Notes Comp. Sci. 1922, 208-220.
• ERKUT, E. (1993) Inequality Measures for Location Problems. Location Science 1, 199-217.
• IBARAKI, T. and KATOH, N. (1988) Resource Allocation Problems, Algorithmic Approaches. MIT Press, Cambridge.
• KALISZEWSKI, I. (2004) On non-interactive selection of the winner in multiple criteria decision making. In: T.Trzaskalik, ed., Modelowanie preferencji a ryzyko ‘03, 195-211.
• KELLY, F., MAULOO, A. and TAN, D. (1997) Rate Control for Communication Networks: Shadow Prices, Proportional Fairness and Stability. J. Oper. Res. Soc. 49, 206-217.
• KLEIN, R.S., LUSS, H. and ROTHBLUM U.G. (1993) Minimax Resource Allocation Problems with Resource-Substitutions Represented by Graphs. Operations Research 41, 959-971.
• KOSTREVA, M.M. and OGRYCZAK, W. (1999) Linear Optimization with Multiple Equitable Criteria. RAIRO Rech. Oper. 33, 275-297.
• KOSTREVA, M.M., OGRYCZAK, W. and WIERZBICKI, A. (2004) Equitable Aggregations and Multiple Criteria Analysis. European Journal of Operational Research 158, 362-367, 2004.
• LEWANDOWSKI, A. and WIERZBICKI, A.P. (1989) Aspiration Based Decision Support Systems - Theory, Software and Applications. Springer, Berlin.
• LUSS, H. (1999) On Equitable Resource Allocation Problems: A Lexicographic Minimax Approach. Operations Research 47, 361-378.
• MARCHI, E. and OVIEDO, J.A. (1992) Lexicographic Optimality in the Multiple Objective Linear Programming: The Nucleolar Solution. European J. of Operational Research 57, 355-359.
• MARSH, M.T. and SCHILLING D.A. (1994) Equity Measurement in Facility Location Analysis: A Review and Framework. European J. of Operational Research 74, 1-17.
• MARSHALL, A.W. and OLKIN, I. (1979) Inequalities: Theory of Majorization and Its Applications. Academic Press, New York.
• MO, J. and WALRAND, J. (2000) Fair End-to-End Window-Based Congestion Control. IEEE/ACM Trans, on Networking 8, 556-567.
• MÜLLER, A. and STOYAN, D. (2002) Comparison Methods for Stochastic Models and Risks. Wiley, New York.
• NASH, J.F. (1950) The Bargaining Problem. Econometrica 18, 155-162.
• OGRYCZAK, W. (1997) Linear and Discrete Optimization with Multiple Criteria: Preference Models and Applications to Decision Support (in Polish). Warsaw Univ. Press, Warsaw.
• OGRYCZAK, W. (2000) Inequality Measures and Equitable Approaches to Location Problems. European J. of Operational Research 122, 374-391.
• OGRYCZAK, W. (2001) Comments on Properties of the Minimax Solutions in Goal Programming. European J. of Operational Research 132, 17-21.
• OGRYCZAK, W. (2002) Multiple Criteria Optimization and Decisions under Risk. Control and Cybernetics 31, 975-1003.
• OGRYCZAK, W., MILEWSKI, M. and WIERZBICKI, A. (2006) On Fair and Efficient Bandwidth Allocation by the Multiple Target Approach. 2006 NGI - Next Generation Internet Design and Engineering, IEEE, 48-55.
• OGRYCZAK, W. and RUSZCZYNSKI, A. (1999) From Stochastic Dominance to Mean-Risk Models: Semideviations as Risk Measures. European J. of Operational Research 116, 33-50.
• OGRYCZAK, W. and RUSZCZYŃSKI, A. (2002) Dual Stochastic Dominance and Related Mean-Risk Models. SIAM J. on Optimization 13, 60-78.
• OGRYCZAK, W. and ŚLIWIŃSKI, T. (2002) On Equitable Approaches to Resource Allocation Problems: the Conditional Minimax Solution. J. of Telecommunications and Information Technology 3, 40-48.
• OGRYCZAK, W. and ŚLIWIŃSKI, T. (2003) On Solving Linear Programs with the Ordered Weighted Averaging Objective. European J. of Operational Research, 148, 80-91.
• OGRYCZAK, W. and ŚLIWIŃSKI, T. (2006) On Direct Methods for Lexicographic Min-Max Optimization. Lect. Notes Comp. Sci. 3982, 774-783.
• OGRYCZAK, W., ŚLIWIŃSKI, T. and WIERZBICKI, A. (2003) Fair Resource Allocation Schemes and Network Dimensioning Problems. J. of Telecommunications and Information Technology 3, 34-42.
• OGRYCZAK, W. and TAMIR, A. (2003) Minimizing the Sum of the k Largest Functions in Linear Time. Information Processing Letters 85, 117-122.
• OGRYCZAK, W. and WIERZBICKI, A. (2004) On Multi-Criteria Approaches to Bandwidth Allocation. Control and Cybernetics 33, 427-448.
• PIGOU, A.C. (1912) Wealth and Welfare. Macmillan, London.
• PIÓRO, M., MALICSKÓ. G. and FODOR, G. (2002) Optimal Link Capacity Dimensioning in Proportionally Fair Networks. Lect. Notes Comp. Sci. 2345, 277-288.
• PIÓRO, M. and MEDHI, D. (2004) Routing, Flow and Capacity Design in Communication and Computer Networks. Morgan Kaufmann Publ., San Francisco.
• RAWLS, J. (1958) Justice as Fairness. Philosophical Review LXVII, 164-194.
• RAWLS, J. (1971) The Theory of Justice. Harvard Univ. Press, Cambridge.
• RAWLS, J. and KELLY, E. (2001) Justice as Fairness: A Restatement. Harvard Univ. Press, Cambridge.
• ROCKAFELLAR, R.T. (1970) Convex Analysis. Princeton Univ. Press.
• ROTHSCHILD, M. and STIGLITZ, J.E. (1973) Some Further Results nn the Measurement of Inequality. J. of Economic Theory 6, 188-204.
• SEN, A. (1973) On Economic Inequality. Clarendon Press, Oxford.
• STEINHAUS, H. (1949) Sur la division pragmatique. Econometrica 17, 315-319.
• STEUER, R.E. (1986) Multiple Criteria Optimization: Theory, Computation & Applications. Wiley, New York.
• VINCKE, PH. (1992) Multicriteria Decision-Aid. Wiley, New York.
• WIERZBICKI, A.P. (1982) A Mathematical Basis for Satisficing Decision Making. Mathematical Modelling 3, 391-405.
• YAGER, R.R. (1988) On ordered weighted averaging aggregation operators in multicriteria decision making. IEEE Tr. Sys. Man Cyber. 18, 183-190.
• YOUNG, H.P. (1994) Equity in Theory and Practice. Princeton Univ. Press, Princeton.