Democratic fair allocation of indivisible goods

DOI10.1016/J.ARTINT.2019.103167zbMATH Open1482.91106arXiv1709.02564OpenAlexW2952411634MaRDI QIDQ2289012FDOQ2289012

Authors: Erel Segal-Halevi, Warut Suksompong 

Publication date: 20 January 2020

Published in: Artificial Intelligence (Search for Journal in Brave)

Abstract: 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 unanimous 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. For two groups with arbitrary monotonic valuations, we give an efficient protocol that guarantees envy-freeness up to one good for at least $1/2$ of the agents in each group, and prove that the $1/2$ fraction is optimal. We also present other protocols that make weaker fairness guarantees to more agents in each group, or to more groups. Our protocols combine techniques from different fields, including combinatorial game theory, cake cutting, and voting.

Full work available at URL: https://arxiv.org/abs/1709.02564

Recommendations

• Fair allocation of indivisible goods: the two-agent case
• Almost envy-freeness in group resource allocation
• Fair enough: guaranteeing approximate maximin shares
• Fair assignment of indivisible objects under ordinal preferences
• Approximate maximin shares for groups of agents

zbMATH Keywords

resource allocationsocial choicefair divisiondemocratic fairness

Mathematics Subject Classification ID

Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Cites Work

• Title not available (Why is that?)
• Collective choice under dichotomous preferences
• Positional games
• Rental Harmony: Sperner's Lemma in Fair Division
• On a combinatorial game
• Stable matchings and preferences of couples
• Paths to stability for matching markets with couples
• Fair Allocation of Indivisible Goods
• Splitting necklaces
• How to Cut a Cake Fairly
• Fair division under ordinal preferences: computing envy-free allocations of indivisible goods
• Envy-free cake divisions cannot be found by finite protocols
• On the fair division of a heterogeneous commodity
• A theory of a heterogeneous divisible commodity exchange economy
• Fair enough: guaranteeing approximate maximin shares
• Which is the fairest (rent division) of them all?
• Title not available (Why is that?)
• Fairly allocating contiguous blocks of indivisible items
• Title not available (Why is that?)
• A constructive proof of a permutation-based generalization of Sperner's lemma
• Social integration in two-sided matching markets
• Introduction to the theory of fair allocation
• Asymptotic existence of fair divisions for groups
• Approximate maximin shares for groups of agents
• Competitive equilibrium with indivisible goods and generic budgets
• Envy-free revenue approximation for asymmetric buyers with budgets
• Monotonicity and competitive equilibrium in cake-cutting
• Computing a small agreeable set of indivisible items
• Simultaneous approximation of constraint satisfaction problems
• The price of connectivity in fair division
• Fair and square: cake-cutting in two dimensions
• Almost envy-freeness in group resource allocation
• Democratic fair allocation of indivisible goods
• Rent division among groups

Cited In (24)

• Fair cake-cutting among families
• When do envy-free allocations exist?
• The price of fairness for indivisible goods
• Communication complexity of discrete fair division
• Fairness for multi-self agents
• Consensus Halving for Sets of Items
• Fair in the Eyes of Others
• Fair sharing under dichotomous preferences
• Fair division with allocator's preference
• Fair allocation of indivisible goods: the two-agent case
• How to cut a cake fairly: a generalization to groups
• Closing gaps in asymptotic fair division
• Fair Allocation of Indivisible Goods
• Almost envy-freeness for groups: improved bounds via discrepancy theory
• Almost envy-freeness in group resource allocation
• Democratic fair allocation of indivisible goods
• Distributed fair allocation of indivisible goods
• Picking sequences and monotonicity in weighted fair division
• Portioning using ordinal preferences: fairness and efficiency
• Fair division of indivisible goods: recent progress and open questions
• Stable matching with multilayer approval preferences: approvals can be harder than strict preferences
• The price of connectivity in fair division
• Fair allocation of group tasks according to social norms
• Computing a small agreeable set of indivisible items

This page was built for publication: Democratic fair allocation of indivisible goods

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2289012)