Abstract
Allocating multiple scarce items across a set of individuals is an important practical problem. In the case of divisible goods and additive preferences, a convex program can be used to find the solution that maximizes Nash welfare (MNW). The MNW solution is equivalent to finding the equilibrium of a market economy (aka. the competitive equilibrium from equal incomes, CEEI) and thus has good properties such as Pareto optimality, envy-freeness, and incentive compatibility in the large. Unfortunately, this equivalence (and nice properties) breaks down for general preference classes. Motivated by real-world problems such as course allocation and recommender systems, we study the case of additive 'at most one' (AMO) preferences—individuals want at most 1 of each item and lotteries are allowed. We show that in this case the MNW solution is still a convex program and, importantly, is a CEEI solution when the instance gets large but has a 'low rank' structure. Thus, a polynomial time algorithm can be used to scale CEEI (which is in general PPAD-hard) for AMO preferences. We examine whether the properties guaranteed in the limit hold approximately in finite samples using several real datasets.
Introduction
Fairly allocating scarce resources among many individuals is a fundamental challenge at the intersection of economics and computer science. The gold standard for such allocations is the Competitive Equilibrium from Equal Incomes (CEEI), where participants receive equal budgets of artificial currency to purchase goods at market-clearing prices. This mechanism ensures Pareto efficiency, envy-freeness, and strategy-proofness in large markets.
However, CEEI is notoriously difficult to compute, falling into the PPAD-hard complexity class. Real-world systems, such as university course matching, often rely on complex integer-programming heuristics that can take hours to execute. Furthermore, many practical scenarios involve "At Most One" (AMO) constraints—for instance, a student requires only one seat in a specific course. Standard fair division models often fail to incorporate these constraints while maintaining their desirable mathematical properties. This paper introduces a scalable method for fair division in AMO settings by leveraging convex optimization to approximate CEEI efficiently.
Methodology: The AMO-EG Approach
The proposed approach, AMO-EG, extends the Eisenberg-Gale (EG) convex program to accommodate AMO constraints.
- Convex Optimization: The allocation is formulated as a convex program that maximizes Nash Welfare (the product of individual utilities) subject to the constraint that no individual receives more than one unit of any specific item.
- Low-Rank Approximation: The authors demonstrate that in "low-rank" markets—where preferences are governed by a small number of latent factors—this convex program naturally approximates a CEEI solution as the market size increases.
- Theoretical Bridge: By introducing the concept of "approximate twins," the authors prove that the redundancy inherent in large markets (where many individuals share similar preferences) allows the Lagrange multipliers of the convex program to function as market prices, satisfying approximate CEEI conditions.
Experimental Evaluation
The AMO-EG method was evaluated using two primary datasets:
- MovieLens 1M: A standard recommender system dataset used to simulate synthetic markets where users bid on movies as scarce goods.
- HBS Course Allocation: Real-world data from Harvard Business School’s course matching system (936 students, 93 courses), serving as a stress test for the approximation in a finite, non-infinite market.
Key Results and Performance
The transition from Mixed-Integer Programs to convex optimization yields a massive gain in scalability. On the HBS dataset, the AMO-EG solution was computed in just 15 seconds, a significant improvement over the approximately 11 hours required by existing heuristics.
As shown in Figure 5, "price regret" (the degree to which a user feels they missed a better bundle given market prices) and envy both vanish as the number of items in the market increases. Additionally, the system demonstrates robust incentive compatibility; even under targeted "attacks" using Bayesian Optimization to manipulate preferences, potential utility gains for individuals remained marginal (typically under 5%).
Limitations and Future Work
While the theoretical results are robust in the limit, finite markets present specific challenges. In the HBS dataset, which represents a smaller, lopsided market with high demand for few items, price regret can remain non-negligible.
Figure 6 illustrates that while envy remains extremely low, price regret in the course allocation setting centers around 0.2. Furthermore, the current model is restricted to additive preferences and does not yet account for substitutes (e.g., wanting Class A or B, but not both) or complements. Future research will focus on incorporating these complex preference structures while maintaining the computational efficiency of the convex programming framework.
Summary updated