Platforms routinely split scarce inventory among participants who pay from fixed budgets. Examples include promotional slots handed to small sellers, cloud credits handed to research groups, and ad impressions spread across advertisers. Two research communities model these budgets in incompatible ways. Fair-division researchers treat a budget as a hard limit on what a bundle may cost and then ask whether anyone envies anyone else. Auction theorists treat a budget as a cap on how much an agent's value can count toward efficiency. Their measure, called liquid welfare, counts each agent's contribution as $\min(v_i, B_i)$, the value capped by the budget. In a real market the same budget does both jobs. This note asks what happens when an allocation rule takes that seriously.
The proposal is to study liquid Nash welfare: maximize the product of budget-capped values over allocations whose cost fits each budget. The main hypothesis concerns a natural assumption, individual rationality, meaning every agent values each item at least at its price. Under that assumption, the fact that one number $B_i$ caps both cost and value should give fairness and efficiency guarantees that existing results cannot reach. Those existing results are a tight 1/4 fairness factor for budget-feasible Nash welfare, and constant efficiency only for two or three agents.
Core Claim
Fix $n$ agents and indivisible items. Item $j$ has a monetary price $c_j$, agent $i$ has budget $B_i$ and additive monetary value $v_i$, and an allocation $A$ is feasible if $c(A_i)\le B_i$ for every agent. Unsellable items go to a "charity" pile. The objective is
$$\text{L-NSW}(A)=\Big(\prod_{i=1}^n \min\big(v_i(A_i),B_i\big)\Big)^{1/n}\quad\text{subject to } c(A_i)\le B_i \text{ for all } i.$$
A skeptic will spot immediately that the uncoupled version gives nothing new. Budget-feasible Maximum Nash Social Welfare is Almost Envy-free proves that budget-feasible Nash-welfare maximizers are 1/4-EF1 and Pareto optimal, that the 1/4 is tight, and that the guarantee extends to subadditive valuations. EF1 means envy disappears after removing one item, and $\alpha$-EF1 means it holds up to a factor $\alpha$. Capped additive valuations are subadditive. A Bridge between Liquid and Social Welfare in Combinatorial Auctions with Submodular Bidders shows they are in fact submodular. So "Nash welfare over capped values is 1/4-EF1 with respect to capped values" is a corollary, not a contribution.
The claim here is narrower and testable. Assume individual rationality, $v_{ij}\ge c_j$. Then any agent who has spent close to her budget is also close to value-saturated. That rules out the configuration where a cheap, high-value bundle sits with someone else while the envious agent is stuck. We conjecture that under this coupling, L-NSW maximizers are at least 1/2-EF1 with respect to capped valuations for every $n$. We also conjecture that they retain a constant fraction of optimal liquid welfare $\sum_i \min(v_i(A_i),B_i)$, independent of $n$. The paper EFx Budget-Feasible Allocations with High Nash Welfare motivates the second conjecture. It reaches constant Nash-welfare fractions alongside strong fairness only for $n=2$ (a factor $\sqrt{0.5}$, best possible) and $n=3$ (a factor 1/171), and leaves $n\ge4$ open.
What Prior Work Supplies and Constrains
The liquid welfare line supplies the objective and the structural tools, but not the fairness questions. Liquid Price of Anarchy shows that uncapped welfare can make equilibrium efficiency arbitrarily bad under budgets, while capped welfare restores constants: tight 2 for pure equilibria with fractionally-subadditive bidders. Autobidders with Budget and ROI Constraints gets half of optimal liquid welfare from pacing dynamics without convergence. Utility Maximizer or Value Maximizer builds a truthful 2-approximation of liquid welfare. All three price items through auctions and never ask whether participants envy each other. The proposal keeps their objective and drops their pricing.
The fair-division line constrains what can be hoped for. Finding Fair Allocations under Budget Constraints gives DensestGreedy. It guarantees EF2 for identical valuations, and a 3-good counterexample shows it cannot guarantee EF1. Guaranteeing Envy-Freeness under Generalized Assignment Constraints shows that Nash welfare does not guarantee feasible envy-freeness under agent-specific sizes. That is a warning that our result may hold only when prices are common across agents, which is exactly the regime where the coupling is meaningful. The 2-agent, 3-item instance in EFx Budget-Feasible Allocations with High Nash Welfare, where EF1 and Pareto efficiency cannot coexist, is the first test case. If it survives individual rationality, the coupling buys less than hoped. Constrained Fair and Efficient Allocations shows 1/2-EF1 for Nash welfare under matroid constraints. Our conjectured constant matches theirs, but knapsack constraints are not matroids, so their exchange-based proof cannot be reused directly. Fair Division with Market Values also pairs subjective values with objective prices, but there the prices define a second fairness criterion rather than a spending limit.
We must be honest about one point. Envy measured on capped values is weaker than envy on true values, because an agent already at her budget envies no one. The proposal therefore reports fairness on both scales. The justification for the capped scale is that value beyond what one can pay for is not something a priced market can deliver to that agent.
Research Program
The theoretical work has three parts.
The first part asks whether individual rationality improves the 1/4 factor. We adapt the bundle-partitioning argument of Budget-feasible Maximum Nash Social Welfare is Almost Envy-free to capped objectives and track where the cap and the cost bound coincide. In parallel, we run a computer search for counterexamples, described below. The search will settle whether the right constant is 1/4, 1/2, or something in between.
The second part bounds the liquid price of fairness. This is the worst-case ratio between optimal liquid welfare and the best liquid welfare among feasible allocations that are $\alpha$-EF1 on capped values. We conjecture it is constant under individual rationality and grows with $n$ without it. A lower-bound family showing growth without individual rationality would make the coupling the identifiable source of the gain.
The third part covers computation. Exact L-NSW is at least as hard as budget-feasible Nash welfare, which is already APX-hard. We will therefore give a mixed-integer program: the logarithm of the capped value is concave, so it can be approximated by tangent cuts. We will also design a local-search heuristic and check whether it inherits the fairness guarantee approximately.
Baselines
The naive reference point is budget-feasible round-robin. Agents take turns picking their most valuable remaining item that still fits their budget, and leftovers go to charity. It costs nothing to run and anchors how much any optimization buys.
The strongest existing fair-division method is the budget-feasible Nash-welfare maximizer of Budget-feasible Maximum Nash Social Welfare is Almost Envy-free. We solve it exactly with the same mixed-integer solver, time limit, and instances as L-NSW. This is the most direct competitor: the only difference is the cap. It has a tight theoretical 1/4-EF1 guarantee. No reported empirical EF1 ratio or liquid-welfare result was found on Lacuna for it, nor for DensestGreedy or the generalized-assignment algorithms. The comparison numbers will therefore be produced here.
For $n=2$ and $n=3$ we also run EFx-2A and EFx-3A from EFx Budget-Feasible Allocations with High Nash Welfare, whose proven Nash-welfare fractions are $\sqrt{0.5}\approx0.707$ and 1/171. We run DensestGreedy from Finding Fair Allocations under Budget Constraints as the strongest fast heuristic.
On the efficiency side, the liquid-welfare-optimal allocation with no fairness constraint is the upper reference. For closeness to platform practice, we include a pacing-style allocator in the spirit of Autobidders with Budget and ROI Constraints, run offline on the same instances.
The key ablation runs L-NSW on matched instances with and without individual rationality. We generate instances, then for half of them resample values below price for a random subset of items. This isolates the coupling as the ingredient.
L-NSW counts as beating the Nash-welfare maximizer if it achieves a higher worst-case EF1 ratio on capped values without losing more than a few percent of liquid welfare. In addition, its worst-case EF1 ratio on true values must not fall below 1/4. Beating the pacing baseline means matching its liquid welfare while being substantially fairer.
Why not just…?
Why not just run budget-feasible Nash welfare and measure liquid welfare afterward? This is the strongest threat. Under individual rationality the two maximizers may often coincide. The paired comparison above measures how often they differ and whether the differences fall on the worst-case fairness instances. If they almost never differ, the contribution shrinks to an analysis result: individual rationality improves the constant for ordinary Nash welfare. That would still be worth stating, and the proposal would be reframed around it.
Why not just treat capped valuations as generic subadditive ones and cite the existing theorem? That yields only 1/4-EF1, already known from Budget-feasible Maximum Nash Social Welfare is Almost Envy-free. The whole claim rests on the cap and the cost bound sharing one number under individual rationality. The ablation that removes individual rationality is designed to show whether that link is doing the work.
Why not just use DensestGreedy or another greedy rule? Greedy is fast and may be good on average. However, Finding Fair Allocations under Budget Constraints proves it cannot guarantee EF1, and its liquid welfare has no known guarantee. The worst-case search below will show whether its failures are frequent under individual rationality or confined to contrived instances.
Proposed Experiments
No public budget-feasible fair-division benchmark exists in the file. Fair-division catalog lookups returned nothing usable, and the e-commerce data from Towards Fair Allocation in Social Commerce Platforms and Beyond Advertising is platform-internal. We therefore use three synthetic families.
The first is exhaustive enumeration of all small instances, up to roughly 3 agents and 7 items over a grid of integer values, prices, and budgets. This finds exact worst cases.
The second is adversarial search for worst cases at up to 6 agents. It hill-climbs on instance parameters to minimize each method's EF1 ratio and liquid-welfare fraction, seeded with the published tight and impossibility examples.
The third is platform-like instances that follow the synthetic protocol of Beyond Advertising: 10 sellers with uniformly drawn budgets. Here we use a few hundred priced slots rather than its $10^5$ requests, so that exact mixed-integer solutions stay tractable. We verify heuristics against exact solutions as Towards Fair Allocation in Social Commerce Platforms did. That paper reports greedy Nash heuristics reaching about 99% of the mixed-integer optimum in a different, cardinality-constrained setting, so it is a sanity reference for heuristic quality rather than a target.
The metrics are four: the worst-case and median EF1 ratio on both capped and true values, the fraction of optimal liquid welfare, Pareto optimality with respect to capped values, and solve time.
Two checks decide the project. First, if exhaustive and adversarial search under individual rationality find an L-NSW instance with capped EF1 ratio at or below 1/4, the main conjecture is false. The project then becomes a characterization of where the coupling helps. Second, if the liquid-welfare fraction of L-NSW drops steadily as $n$ grows from 2 to 6 on adversarial instances, the constant-efficiency conjecture fails. If both checks pass, the proof effort for general $n$ is well-founded, and the counterexample search will have supplied the extremal instances that a tight analysis has to handle.
References
- Budget-feasible Maximum Nash Social Welfare is Almost Envy-free
- A Bridge between Liquid and Social Welfare in Combinatorial Auctions with Submodular Bidders
- EFx Budget-Feasible Allocations with High Nash Welfare
- Liquid Price of Anarchy
- Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics
- Utility Maximizer or Value Maximizer: Mechanism Design for Mixed Bidders in Online Advertising
- Finding Fair Allocations under Budget Constraints
- Guaranteeing Envy-Freeness under Generalized Assignment Constraints
- Constrained Fair and Efficient Allocations
- Fair Division with Market Values
- Towards Fair Allocation in Social Commerce Platforms
- Beyond Advertising: Mechanism Design for Platform-Wide Marketing Service "QuanZhanTui"