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

DOI10.1016/J.INS.2021.11.059MaRDI QIDQ6154777zbMATH OpenFDO

Authors Elad Aigner-Horev, Erel Segal-Halevi

Publication date 16 February 2024

Published in Information Sciences (Search for Journal in Brave)

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)

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.

Recommendations

• Approximate envy-freeness in graphical cake cutting
• Envy-free matchings with one-sided preferences and matroid constraints
• On envy-free perfect matching
• Envy-freeness in house allocation problems
• The envy-free matching problem with pairwise preferences

Cites work

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

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)