Research map / Learning theory and algorithms / Submodular and game algorithms
Envy-Free House Allocation under Uncertain Preferences
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies envy-free house allocation under three uncertain-preference models (lottery, compact indifference, joint probability), giving complexity results for finding the allocation with maximum probability of envy-freeness and for the possibly/certainly EF existence problems.
Problem
Computing a house allocation that maximizes the probability of being envy-free when agents have uncertain (probabilistic or weak-order) preferences over houses, plus deciding whether a possibly or certainly EF allocation exists.
Approach
Classifies complexity per uncertainty model: lottery model makes existence problems NP-complete and rules out multiplicative approximation; compact indifference model admits polynomial existence algorithms and an algorithm that either solves Max-ProbEF exactly or certifies probability below any fixed epsilon; joint probability model is NP-complete for certainly-EF and has a 6/5 inapproximability b
Key results
- Lottery model: ExistsPossiblyEF and ExistsCertainlyEF are NP-complete, and Max-ProbEF admits no bounded multiplicative approximation unless P=NP.
- Compact indifference model: finding an f(n,m)-approximation of Max-ProbEF is NP-hard, but for any fixed epsilon there is a polynomial-time algorithm that either computes the optimum or certifies OPT < epsilon, running in O(n^{2/epsilon}) poly time.
- Joint probability model: ExistsCertainlyEF is NP-complete even with six profiles, and no polynomial (6/5 - epsilon)-approximation for Max-ProbEF exists unless P=NP.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the lottery model rather than the compact indifference model | ExistsPossiblyEF · house allocation under uncertain preferences | complexity: in P -> NP-complete | Hurt |
| Use the lottery model rather than the compact indifference model | ExistsCertainlyEF · house allocation under uncertain preferences | complexity: in P -> NP-complete | Hurt |
| Use the joint probability model rather than the compact indifference model | ExistsCertainlyEF · house allocation under uncertain preferences | complexity: in P -> NP-complete | Hurt |
| Use the joint probability model rather than the lottery model | ExistsPossiblyEF · house allocation under uncertain preferences | complexity: NP-complete -> in P | Helped |
| Use the compact indifference model for Max-ProbEF | Max-ProbEF · house allocation under uncertain preferences | approximation | Mixed |
Surprising findings
- Compact indifference model makes existence problems polynomial while Max-ProbEF stays hard to approximate within any polynomial factor.
- Each uncertainty model yields a distinct complexity profile despite similar setup.
Limitations
- Max-ProbEF is inapproximable in the lottery and compact indifference models; positive results only for fixed epsilon additive threshold in compact indifference model.
- Joint probability model has no approximation better than 6/5 and the best achievable ratio is open.
- Results are purely theoretical with no empirical evaluation.
Experimental setup
Metrics: probability of envy-freeness approximation ratio
Builds on: house allocation with ties Pareto optimal allocation under uncertain preferences
Closest papers by meaning
- Almost Envy-Free Allocations of Indivisible Goods or Chores with Entitlements (AAAI 2024 · similarity 0.91)
- The Complexity of Extending Fair Allocations of Indivisible Goods (AAAI 2025 · similarity 0.90)
- Towards Optimal Subsidy Bounds for Envy-Freeable Allocations (AAAI 2024 · similarity 0.90)
- The Complexity of Fair Division of Indivisible Items with Externalities (AAAI 2024 · similarity 0.90)
- Repeated Fair Allocation of Indivisible Items (AAAI 2024 · similarity 0.90)
- On Hierarchies of Fairness Notions in Cake Cutting: From Proportionality to Super Envy-Freeness (NeurIPS 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.