On Fair Division under Heterogeneous Matroid Constraints

DOI10.1613/JAIR.1.13779arXiv2010.07280MaRDI QIDQ6135949FDOQ6135949

Authors: Michal Feldman, Erel Segal-Halevi 

Publication date: 28 August 2023

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

Abstract: We study fair allocation of indivisible goods among additive agents with feasibility constraints. In these settings, every agent is restricted to get a bundle among a specified set of feasible bundles. Such scenarios have been of great interest to the AI community due to their applicability to real-world problems. Following some impossibility results, we restrict attention to matroid feasibility constraints that capture natural scenarios, such as the allocation of shifts to medical doctors, and the allocation of conference papers to referees. We focus on the common fairness notion of envy-freeness up to one good (EF1). Previous algorithms for finding EF1 allocations are either restricted to agents with identical feasibility constraints, or allow free disposal of items. An open problem is the existence of EF1 complete allocations among heterogeneous agents, where the heterogeneity is both in the agents' feasibility constraints and in their valuations. In this work, we make progress on this problem by providing positive and negative results for different matroid and valuation types. Among other results, we devise polynomial-time algorithms for finding EF1 allocations in the following settings: (i) $n$ agents with heterogeneous partition matroids and heterogeneous binary valuations, (ii) 2 agents with heterogeneous partition matroids and heterogeneous additive valuations, and (iii) at most 3 agents with heterogeneous binary valuations and identical base-orderable matroid constraints.

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

zbMATH Keywords

game theoryconstraint satisfactioncomputational social systems

Mathematics Subject Classification ID

Artificial intelligence (68Txx)

Cites Work

• Minimum partition of a matroid into independent subsets
• A THEOREM ON INDEPENDENCE RELATIONS
• Combinatorial auctions with decreasing marginal utilities
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• Exchange systems, matchings, and transversals
• A weighted matroid intersection algorithm
• Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities
• Title not available (Why is that?)
• The computational complexity of matroid properties
• Pairwise kidney exchange
• Optimal approximation for the submodular welfare problem in the value oracle model
• Title not available (Why is that?)
• Priority matchings revisited
• Induced Matroids
• Comments on bases in dependence structures
• Earning limits in Fisher markets with spending-constraint utilities
• Title not available (Why is that?)
• Title not available (Why is that?)
• Course Match: A Large-Scale Implementation of Approximate Competitive Equilibrium from Equal Incomes for Combinatorial Allocation
• Fairly allocating contiguous blocks of indivisible items
• Assigning papers to referees
• On maximin share allocations in matroids
• A Protocol for Cutting Matroids Like Cakes
• Title not available (Why is that?)
• Fair division with multiple pieces
• The Price of Connectivity in Fair Division
• Splitting Necklaces, with Constraints
• Finding fair and efficient allocations when valuations don't add up
• The fair division of hereditary set systems
• Title not available (Why is that?)
• Almost envy-freeness in group resource allocation

Cited In (8)

• Fair division under joint ownership: Recent results and open problems
• Improved maximin guarantees for subadditive and fractionally subadditive fair allocation problem
• Title not available (Why is that?)
• The fair division of hereditary set systems
• Diverse fair allocations: complexity and algorithms
• Fair division with two-sided preferences
• On fair division with binary valuations respecting social networks
• Fair division with minimal withheld information in social networks

This page was built for publication: On Fair Division under Heterogeneous Matroid Constraints

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