On Fair Division under Heterogeneous Matroid Constraints
From MaRDI portal
Publication:6135949
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) 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.
Recommendations
Cites work
- scientific article; zbMATH DE number 1953186 (Why is no real title available?)
- scientific article; zbMATH DE number 5047784 (Why is no real title available?)
- A THEOREM ON INDEPENDENCE RELATIONS
- A protocol for cutting matroids like cakes
- A weighted matroid intersection algorithm
- Almost envy-free allocations with connected bundles
- Almost envy-freeness in group resource allocation
- Approximating the Nash social welfare with budget-additive valuations
- Assigning papers to referees
- Combinatorial auctions with decreasing marginal utilities
- Comments on bases in dependence structures
- Course Match: A Large-Scale Implementation of Approximate Competitive Equilibrium from Equal Incomes for Combinatorial Allocation
- Earning limits in Fisher markets with spending-constraint utilities
- Exchange systems, matchings, and transversals
- Fair division with multiple pieces
- Finding fair and efficient allocations when valuations don't add up
- Induced Matroids
- Matching under preferences
- Maximizing a monotone submodular function subject to a matroid constraint
- Minimum partition of a matroid into independent subsets
- Nash social welfare for indivisible items under separable, piecewise-linear concave utilities
- Near fairness in matroids
- On maximin share allocations in matroids
- Optimal approximation for the submodular welfare problem in the value oracle model
- Pairwise kidney exchange
- Priority matchings revisited
- Splitting necklaces, with constraints
- The computational complexity of matroid properties
- The fair division of hereditary set systems
- The price of connectivity in fair division
Cited in
(8)- Improved maximin guarantees for subadditive and fractionally subadditive fair allocation problem
- On fair division with binary valuations respecting social networks
- scientific article; zbMATH DE number 7650858 (Why is no real title available?)
- Fair division with minimal withheld information in social networks
- Diverse fair allocations: complexity and algorithms
- The fair division of hereditary set systems
- Fair division under joint ownership: Recent results and open problems
- Fair division with two-sided preferences
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)
