Democratic fair allocation of indivisible goods

DOI10.1016/J.ARTINT.2019.103167MaRDI QIDQ2289012zbMATH OpenOpenAlexFDO

Authors Erel Segal-Halevi, Warut Suksompong

Publication date 20 January 2020

Published in Artificial Intelligence (Search for Journal in Brave)

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

zbMATH Keywords

resource allocationsocial choicefair divisiondemocratic fairness

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(24)

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

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)