We study the problem of how to fairly and efficiently allocate indivisible items (goods) to agents under budget constraints. Each item has a specific size, and each agent has a budget that limits the total size of the items received. To better explore efficiency, we introduce the concept of tightness, where all agents are tight. An agent is considered as tight if adding any unallocated item to her bundle would exceed her budget. Interestingly, we observe that every Pareto optimal (PO) allocation can be extended into a tight allocation while maintaining the values of the agents’ bundles. We achieve an overall negative result for general even identical binary valuations: there exists no allocation meeting both tightness and envy-freeness up to any item (EFX), and even relaxing it to any desired approximate EFX still has been proved impossible. However, for single-valued valuations, we illustrate that an EFX and tight allocation always exist, and it can be computed using a polynomial algorithm. For identical single-valued valuations, we establish the existence of 1/2-EFX and PO allocations, with the approximation ratio being the best possible. To further our efforts to study fairness and efficiency, we introduce a relaxed concept of tightness, partial tightness (PT), in which only the unenvied agents are tight. We find that 1/2-EFX and PT allocations are achievable by providing a pseudo-polynomial time algorithm.

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

Finding Fair and Efficient Allocations Under Budget Constraints

  • Yuanyuan Wang,
  • Xin Chen,
  • Qizhi Fang,
  • Qingqin Nong,
  • Wenjing Liu

摘要

We study the problem of how to fairly and efficiently allocate indivisible items (goods) to agents under budget constraints. Each item has a specific size, and each agent has a budget that limits the total size of the items received. To better explore efficiency, we introduce the concept of tightness, where all agents are tight. An agent is considered as tight if adding any unallocated item to her bundle would exceed her budget. Interestingly, we observe that every Pareto optimal (PO) allocation can be extended into a tight allocation while maintaining the values of the agents’ bundles. We achieve an overall negative result for general even identical binary valuations: there exists no allocation meeting both tightness and envy-freeness up to any item (EFX), and even relaxing it to any desired approximate EFX still has been proved impossible. However, for single-valued valuations, we illustrate that an EFX and tight allocation always exist, and it can be computed using a polynomial algorithm. For identical single-valued valuations, we establish the existence of 1/2-EFX and PO allocations, with the approximation ratio being the best possible. To further our efforts to study fairness and efficiency, we introduce a relaxed concept of tightness, partial tightness (PT), in which only the unenvied agents are tight. We find that 1/2-EFX and PT allocations are achievable by providing a pseudo-polynomial time algorithm.