In classical economic theory, the Fisher market provides a elegant way to distribute resources: agents with fixed budgets bid on goods until prices reach a "competitive equilibrium" where supply equals demand. This works perfectly if goods are infinitely divisible, like flour or electricity.
However, most real-world resources are indivisible—you cannot assign half a seat in a classroom or 0.3 of a specific server instance. In these discrete settings, the mathematical beauty of competitive equilibrium often collapses. Because items cannot be split, agents may find themselves with "leftover" budget that cannot buy a whole item, or two agents with identical budgets might "tie" for a single item, leaving no stable price that clears the market.
To bridge this gap, a growing body of research suggests that the key to discrete fairness is not changing the items, but slightly perturbing the agents' budgets.
Breaking Ties with Generic Budgets
The most common reason a competitive equilibrium fails to exist in discrete markets is exact symmetry. If two agents have the exact same budget and the same preferences, but there is only one item they both want, no price can satisfy both. If the price is low, they both demand it (excess demand); if the price is higher than their budget, neither can buy it (excess supply).
Noam Nisan, Inbal Talgam-Cohen, and Moshe Babaioff demonstrate in Competitive Equilibrium with Indivisible Goods and Generic Budgets that this failure is often a "knife-edge" phenomenon. By introducing generic budgets—infinitesimal, random perturbations to agent entitlements—we can break these ties.
This tiny amount of "noise" ensures that no two agents have exactly the same purchasing power, effectively ordering them so that ties in demand are resolved naturally. Their work shows that for two agents with additive preferences, these perturbations guarantee the existence of a competitive equilibrium that is both fair and efficient.
Rounding Fractional Allocations to Integral Ones
If we start with a standard fractional equilibrium (where items can be split), how far must we move to reach a state where every item is assigned as a whole?
Sanath Kumar Krishnamurthy explores this in On the Proximity of Markets with Integral Equilibria. The core insight is that instead of trying to force prices to adjust to indivisible items—which can lead to wild price swings—we should keep prices fixed and adjust the agents' budgets.
Krishnamurthy proves that for any fractional Fisher market, there exists a "nearby" market that admits a perfectly integral equilibrium. The "distance" to this market is remarkably small: the necessary change to any individual's budget is bounded by the price of the single most expensive item in the market. This suggests that the economic distortion required to move from fractional theory to discrete reality is localized and proportional to the value of the goods being traded.
Regularizing Markets with Entrance Fees
When agents are strategic (i.e., they might lie about their preferences to get a better deal), markets face additional instabilities. In markets with "complementary" goods—where an agent only values item A if they also get item B—prices can often drop to zero, causing the market mechanism to fail.
In Nash Social Welfare Approximation for Strategic Agents, Simina Branzei, Vasilis Gkatzelis, and Ruta Mehta show that a small, fixed participation cost or entrance fee acts as a powerful regularizer.
This fee ensures that every resource receives at least a minimum bid, preventing zero-price deadlocks. By slightly reducing the effective budget of each agent through this fee, the mechanism (specifically the Trading Post mechanism) becomes robust enough to achieve a constant-factor approximation of the optimal Nash Social Welfare—the geometric mean of all agents' utilities—even when agents act selfishly.
Why Perturbations Work
Across these papers, the recurring theme is that discreteness creates rigidity. In a perfectly symmetric or "clean" mathematical model, the constraints of indivisible goods create hard boundaries that equilibrium cannot cross.
Budget perturbations work because they:
- Smooth the Demand Curve: Small changes in budget prevent large groups of agents from switching their preferences at the exact same price point.
- Break Mathematical Singularities: They move the market away from "zero-price" or "equal-budget" states where the standard proofs of existence fail.
- Quantify the Gap: They provide a metric (the size of the perturbation) for how "far" a discrete problem is from its ideal fractional counterpart.
By accepting a tiny amount of inequality in budgets, these researchers have found a way to recover the global properties of fairness and efficiency that make market-based allocation so desirable.