Envy-free matchings in bipartite graphs and their applications to fair division

DOI10.1016/J.INS.2021.11.059arXiv1901.09527MaRDI QIDQ6154777FDOQ6154777

Authors: Elad Aigner-Horev, Erel Segal-Halevi 

Publication date: 16 February 2024

Published in: Information Sciences (Search for Journal in Brave)

Abstract: A matching in a bipartite graph with parts X and Y is called envy-free if no unmatched vertex in X is a adjacent to a matched vertex in Y. Every perfect matching is envy-free, but envy-free matchings exist even when perfect matchings do not. We prove that every bipartite graph has a unique partition such that all envy-free matchings are contained in one of the partition sets. Using this structural theorem, we provide a polynomial-time algorithm for finding an envy-free matching of maximum cardinality. For edge-weighted bipartite graphs, we provide a polynomial-time algorithm for finding a maximum-cardinality envy-free matching of minimum total weight. We show how envy-free matchings can be used in various fair division problems with either continuous resources ("cakes") or discrete ones. In particular, we propose a symmetric algorithm for proportional cake-cutting, an algorithm for 1-out-of-(2n-2) maximin-share allocation of discrete goods, and an algorithm for 1-out-of-floor(2n/3) maximin-share allocation of discrete bads among n agents.

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

zbMATH Keywords

perfect matchingbipartite graphsmaximum matchingfair divisioncake cuttingmaximin share

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Extremal problems in graph theory (05C35) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Collective choice under dichotomous preferences
• On profit-maximizing envy-free pricing
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Rank-maximal matchings
• Title not available (Why is that?)
• A polynomial-time approximation scheme for maximizing the minimum machine completion time
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximation Algorithms for Computing Maximin Share Allocations
• A note on cake cutting
• Fair enough: guaranteeing approximate maximin shares
• Fair assignment of indivisible objects under ordinal preferences
• Envy-freeness in house allocation problems
• Competitive equilibria in two-sided matching markets with general utility functions
• The lattice of envy-free matchings
• Competitive equilibrium with indivisible goods and generic budgets
• Optimal multi-way number partitioning
• Envy-free matchings with lower quotas
• On the complexity of fair house allocation
• Fair multi-cake cutting
• Meta-Envy-Free Cake-Cutting Protocols

Cited In (2)

• Improved truthful rank approximation for rank-maximal matchings
• Dividing a graphical cake

This page was built for publication: Envy-free matchings in bipartite graphs and their applications to fair division

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