The Price of Fairness

• 成果类型: Article
• 署名作者: Bertsimas, Dimitris; Farias, Vivek F.; Trichakis, Nikolaos
• 署名单位: Massachusetts Institute of Technology (MIT)
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1100.0865
• 发表日期: 2011
• 页码: 17-31
• 关键词: Optimization; EFFICIENCY

摘要

In this paper we study resource allocation problems that involve multiple self-interested parties or players and a central decision maker. We introduce and study the price of fairness, which is the relative system efficiency loss under a fair allocation assuming that a fully efficient allocation is one that maximizes the sum of player utilities. We focus on two well-accepted, axiomatically justified notions of fairness, viz., proportional fairness and max-min fairness. For these notions we provide a tight characterization of the price of fairness for a broad family of problems.