Contiguous Allocation of Indivisible Items on a Path
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915097800081408 |
|---|---|
| author | Kawase, Yasushi Roy, Bodhayan Sanpui, Mohammad Azharuddin |
| author_facet | Kawase, Yasushi Roy, Bodhayan Sanpui, Mohammad Azharuddin |
| contents | We study the problem of allocating indivisible items on a path among agents. The objective is to find a fair and efficient allocation in which each agent's bundle forms a contiguous block on the line. We say that an instance is \emph{$(a, b)$-sparse} if each agent values at most $a$ items positively and each item is valued positively by at most $b$ agents. We demonstrate that, even when the valuations are binary additive, deciding whether every item can be allocated to an agent who wants it is NP-complete for the $(4,3)$-sparse instances. Consequently, we provide two fixed-parameter tractable (FPT) algorithms for maximizing utilitarian social welfare, with respect to the number of agents and the number of items. Additionally, we present a $2$-approximation algorithm for the special case when the valuations are binary additive, and the maximum utility is equal to the number of items. Also, we provide a $1/a$-approximation algorithm for the $(a,b)$-sparse instances. Furthermore, we establish that deciding whether the maximum egalitarian social welfare is at least $2$ or at most $1$ is NP-complete for the $(6,3)$-sparse instances, even when the valuations are binary additive. We present a $1/a$-approximation algorithm for maximizing egalitarian social welfare for the $(a,b)$-sparse instances. Besides, we give two FPT algorithms for maximizing egalitarian social welfare in terms of the number of agents and the number of items. We also explore the case where the order of the blocks of items allocated to the agents is predetermined. In this case, we show that both maximum utilitarian social welfare and egalitarian social welfare can be computed in polynomial time. However, we determine that checking the existence of an EF1 allocation is NP-complete, even when the valuations are binary additive. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_04318 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Contiguous Allocation of Indivisible Items on a Path Kawase, Yasushi Roy, Bodhayan Sanpui, Mohammad Azharuddin Computer Science and Game Theory We study the problem of allocating indivisible items on a path among agents. The objective is to find a fair and efficient allocation in which each agent's bundle forms a contiguous block on the line. We say that an instance is \emph{$(a, b)$-sparse} if each agent values at most $a$ items positively and each item is valued positively by at most $b$ agents. We demonstrate that, even when the valuations are binary additive, deciding whether every item can be allocated to an agent who wants it is NP-complete for the $(4,3)$-sparse instances. Consequently, we provide two fixed-parameter tractable (FPT) algorithms for maximizing utilitarian social welfare, with respect to the number of agents and the number of items. Additionally, we present a $2$-approximation algorithm for the special case when the valuations are binary additive, and the maximum utility is equal to the number of items. Also, we provide a $1/a$-approximation algorithm for the $(a,b)$-sparse instances. Furthermore, we establish that deciding whether the maximum egalitarian social welfare is at least $2$ or at most $1$ is NP-complete for the $(6,3)$-sparse instances, even when the valuations are binary additive. We present a $1/a$-approximation algorithm for maximizing egalitarian social welfare for the $(a,b)$-sparse instances. Besides, we give two FPT algorithms for maximizing egalitarian social welfare in terms of the number of agents and the number of items. We also explore the case where the order of the blocks of items allocated to the agents is predetermined. In this case, we show that both maximum utilitarian social welfare and egalitarian social welfare can be computed in polynomial time. However, we determine that checking the existence of an EF1 allocation is NP-complete, even when the valuations are binary additive. |
| title | Contiguous Allocation of Indivisible Items on a Path |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2401.04318 |