Fair Shares: Feasibility, Domination, and Incentives

• 成果类型: Article
• 署名作者: Babaioff, Moshe; Feige, Uriel
• 署名单位: Hebrew University of Jerusalem; Weizmann Institute of Science
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.0257
• 发表日期: 2025
• 关键词: Indivisible goods

摘要

We consider fair allocation of indivisible goods to n equally entitled agents. Every agent i has a valuation function vi from some given class of valuation functions. A share s is a function that maps (vi, n) to a nonnegative value. A share is feasible if for every allocation instance, there is an allocation that gives every agent i a bundle that is acceptable with respect to vi, one of value at least her share value s(vi, n). We introduce the following concepts. A share is self-maximizing if reporting the true valuation maximizes the minimum true value of a bundle that is acceptable with respect to the report. A share s rho-dominates another share s ' if s(vi, n) >= rho s '(vi, n) for every valuation function. We initiate a systematic study of feasible and self-maximizing shares and a systematic study of rho-domination relation between shares, presenting both positive and negative results.