Fair allocation of indivisible items among agents with budget constraints has received considerable attention recently. In this model, each agent has a budget, and each item has a specific size and homogeneous or heterogeneous valuations for all the agents. In a fair allocation, each agent receives a bundle of items with total size no more than her budget, meanwhile the EF1 (envy-freeness up to one item) fairness holds between any agents. To avoid a trivial and meaningless solution in which all bundles are empty, we invoke the well-studied concept PoF (price of fairness), the worst-case ratio between the maximum total valuation without and with the fairness guarantee to capture the efficiency loss induced by fairness. In this paper, the PoFs are extensively studied in various settings. We first investigate an algorithm outputting an EF1 allocation with the total valuation at least \(\frac{1}{2n}\) of the maximum total valuation (without EF1 requirement), where n is the number of agents. It implies that PoF is at most 2n. Meanwhile, we give an instance to show that PoF is at least \(n - \epsilon \) . Then a special case that the valuation of an item is identical for all the agents is considered. We establish an algorithm which outputs an EF1 allocation with the total valuation at least \(\frac{1}{2}\) of the maximum total valuation. That is to say, an algorithm with PoF of 2 is devised. And we give a lower bound of \(2 - \frac{1}{n}\) . Finally, the scenario of two agents is discussed. An algorithm with PoF of \(\frac{3}{2}\) is constructed when all the agents have identical valuation for an item. For different valuations, we improve the upper bound of PoF to 3.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

The Price of Fairness for Budget-Feasible EF1 Allocations

  • Tingwei Hu,
  • Lili Mei,
  • Zhen Wang,
  • Guochuan Zhang

摘要

Fair allocation of indivisible items among agents with budget constraints has received considerable attention recently. In this model, each agent has a budget, and each item has a specific size and homogeneous or heterogeneous valuations for all the agents. In a fair allocation, each agent receives a bundle of items with total size no more than her budget, meanwhile the EF1 (envy-freeness up to one item) fairness holds between any agents. To avoid a trivial and meaningless solution in which all bundles are empty, we invoke the well-studied concept PoF (price of fairness), the worst-case ratio between the maximum total valuation without and with the fairness guarantee to capture the efficiency loss induced by fairness. In this paper, the PoFs are extensively studied in various settings. We first investigate an algorithm outputting an EF1 allocation with the total valuation at least \(\frac{1}{2n}\) of the maximum total valuation (without EF1 requirement), where n is the number of agents. It implies that PoF is at most 2n. Meanwhile, we give an instance to show that PoF is at least \(n - \epsilon \) . Then a special case that the valuation of an item is identical for all the agents is considered. We establish an algorithm which outputs an EF1 allocation with the total valuation at least \(\frac{1}{2}\) of the maximum total valuation. That is to say, an algorithm with PoF of 2 is devised. And we give a lower bound of \(2 - \frac{1}{n}\) . Finally, the scenario of two agents is discussed. An algorithm with PoF of \(\frac{3}{2}\) is constructed when all the agents have identical valuation for an item. For different valuations, we improve the upper bound of PoF to 3.