Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.23251 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908526254751744 |
|---|---|
| author | Wang, Yuanyuan Wei, Tianze |
| author_facet | Wang, Yuanyuan Wei, Tianze |
| contents | We study the fair allocation problem of indivisible items with subsidy. In this paper, we focus on the notion of fairness - equitability (EQ), which requires that items be allocated such that all agents value the bundle they receive equally. First, we study the upper bounds of the minimum required subsidy to achieve EQ in different item settings and provide the corresponding lower bounds. Second, we consider the bounded subsidy for achieving EQ and another popular notion of fairness - envy-freeness (EF), and give a characterization of allocations that can achieve both EQ and EF. Finally, we analyze the bounds of subsidy of allocations achieving fairness and efficiency (utilitarian social welfare or Nash welfare) and design several polynomial-time algorithms to compute the desired allocation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_23251 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Achieving Equitability with Subsidy Wang, Yuanyuan Wei, Tianze Computer Science and Game Theory We study the fair allocation problem of indivisible items with subsidy. In this paper, we focus on the notion of fairness - equitability (EQ), which requires that items be allocated such that all agents value the bundle they receive equally. First, we study the upper bounds of the minimum required subsidy to achieve EQ in different item settings and provide the corresponding lower bounds. Second, we consider the bounded subsidy for achieving EQ and another popular notion of fairness - envy-freeness (EF), and give a characterization of allocations that can achieve both EQ and EF. Finally, we analyze the bounds of subsidy of allocations achieving fairness and efficiency (utilitarian social welfare or Nash welfare) and design several polynomial-time algorithms to compute the desired allocation. |
| title | Achieving Equitability with Subsidy |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2505.23251 |