Fair Shares: Feasibility, Domination, and Incentives
研究了在不可分割物品公平分配中，如何定义一种份额，使得每个代理人报告真实估值能最大化其最低可接受价值，并分析了不同份额之间的支配关系。
We consider fair allocation of indivisible goods to n equally entitled agents. Every agent i has a valuation function v i from some given class of valuation functions. A share s is a function that maps [Formula: see text] 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 v i , one of value at least her share value [Formula: see text]. 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 ρ-dominates another share [Formula: see text] if [Formula: see text] for every valuation function. We initiate a systematic study of feasible and self-maximizing shares and a systematic study of ρ-domination relation between shares, presenting both positive and negative results. Funding: The research of M. Babaioff is supported in part by a Golda Meir Fellowship. The research of U. Feige is supported in part by the Israel Science Foundation [Grant 1122/22].