Democratic fair allocation of indivisible goods
We study the problem of fairly allocating indivisible goods to groups of agents. Agents in the same group share the same set of goods even though they may have different preferences. Previous work has focused on unani- mous fairness, in which all agents in each group must agree that their group’s sh...
| Автори: | , |
|---|---|
| Інші автори: | |
| Формат: | Conference item |
| Опубліковано: |
International Joint Conferences on Artificial Intelligence
2018
|
| _version_ | 1826302413058867200 |
|---|---|
| author | Segal-Halevi, E Suksompong, W |
| author2 | Lang, J |
| author_facet | Lang, J Segal-Halevi, E Suksompong, W |
| author_sort | Segal-Halevi, E |
| collection | OXFORD |
| description | We study the problem of fairly allocating indivisible goods to groups of agents. Agents in the same group share the same set of goods even though they may have different preferences. Previous work has focused on unani- mous fairness, in which all agents in each group must agree that their group’s share is fair. Under this strict requirement, fair allocations exist only for small groups. We introduce the concept of democratic fairness, which aims to satisfy a certain fraction of the agents in each group. This concept is better suited to large groups such as cities or countries. We present protocols for democratic fair allocation among two or more arbitrarily large groups of agents with monotonic, additive, or binary valuations. Our protocols approximate both envy-freeness and maximin-share fairness. As an example, for two groups of agents with additive valuations, our protocol yields an allocation that is envy-free up to one good and gives at least half of the maximin share to at least half of the agents in each group. |
| first_indexed | 2024-03-07T05:47:10Z |
| format | Conference item |
| id | oxford-uuid:e79b1023-ad43-40e5-a952-84c71b054b61 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T05:47:10Z |
| publishDate | 2018 |
| publisher | International Joint Conferences on Artificial Intelligence |
| record_format | dspace |
| spelling | oxford-uuid:e79b1023-ad43-40e5-a952-84c71b054b612022-03-27T10:40:05ZDemocratic fair allocation of indivisible goodsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:e79b1023-ad43-40e5-a952-84c71b054b61Symplectic Elements at OxfordInternational Joint Conferences on Artificial Intelligence2018Segal-Halevi, ESuksompong, WLang, JWe study the problem of fairly allocating indivisible goods to groups of agents. Agents in the same group share the same set of goods even though they may have different preferences. Previous work has focused on unani- mous fairness, in which all agents in each group must agree that their group’s share is fair. Under this strict requirement, fair allocations exist only for small groups. We introduce the concept of democratic fairness, which aims to satisfy a certain fraction of the agents in each group. This concept is better suited to large groups such as cities or countries. We present protocols for democratic fair allocation among two or more arbitrarily large groups of agents with monotonic, additive, or binary valuations. Our protocols approximate both envy-freeness and maximin-share fairness. As an example, for two groups of agents with additive valuations, our protocol yields an allocation that is envy-free up to one good and gives at least half of the maximin share to at least half of the agents in each group. |
| spellingShingle | Segal-Halevi, E Suksompong, W Democratic fair allocation of indivisible goods |
| title | Democratic fair allocation of indivisible goods |
| title_full | Democratic fair allocation of indivisible goods |
| title_fullStr | Democratic fair allocation of indivisible goods |
| title_full_unstemmed | Democratic fair allocation of indivisible goods |
| title_short | Democratic fair allocation of indivisible goods |
| title_sort | democratic fair allocation of indivisible goods |
| work_keys_str_mv | AT segalhalevie democraticfairallocationofindivisiblegoods AT suksompongw democraticfairallocationofindivisiblegoods |