We consider the problem of allocating m indivisible items to a set of n heterogeneous agents, aiming at computing a proportional allocation by introducing subsidy (money). It has been shown by Wu et al. (WINE 2023) that when agents are unweighted a total subsidy of n/4 suffices (assuming that each item has value/cost at most 1 to every agent) to ensure proportionality. When agents have general weights, they proposed an algorithm that guarantees a weighted proportional allocation requiring a total subsidy of \((n-1)/2\) , by rounding the fractional bid-and-take algorithm. In this work, we revisit the problem and the fractional bid-and-take algorithm. We show that by formulating the fractional allocation returned by the algorithm as a directed tree connecting the agents and splitting the tree into canonical components, there is a rounding scheme that requires a total subsidy of at most \(n/3 - 1/6\) .

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

Tree Splitting Based Rounding Scheme for Weighted Proportional Allocations with Subsidy

  • Xiaowei Wu,
  • Shengwei Zhou

摘要

We consider the problem of allocating m indivisible items to a set of n heterogeneous agents, aiming at computing a proportional allocation by introducing subsidy (money). It has been shown by Wu et al. (WINE 2023) that when agents are unweighted a total subsidy of n/4 suffices (assuming that each item has value/cost at most 1 to every agent) to ensure proportionality. When agents have general weights, they proposed an algorithm that guarantees a weighted proportional allocation requiring a total subsidy of \((n-1)/2\) , by rounding the fractional bid-and-take algorithm. In this work, we revisit the problem and the fractional bid-and-take algorithm. We show that by formulating the fractional allocation returned by the algorithm as a directed tree connecting the agents and splitting the tree into canonical components, there is a rounding scheme that requires a total subsidy of at most \(n/3 - 1/6\) .