| paper | Approximations for Indivisible Concave Allocations with Applications to |
| authors | — |
| venue | AAAI 2023 |
| filed under | fairalloc · markets |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 3
Type-Smooth-ANW-infinity: given rational masses \(p_a\) of complete agent types, rational supplies \(q_b\) of item types, utilities \(u_{ab}\), weights \(\eta_a\), smoothing parameter \(\omega\), and integral bundle configurations \(k\) in the nonnegative integer lattice, choose configuration masses \(y_{a,k}\) satisfying \(\sum_k y_{a,k} = p_a\) and \(\sum_{a,k} k_b y_{a,k} = q_b\), maximizing \(\exp\left(\left(\sum_{a,k} y_{a,k} \eta_a \ln\left(\sum_b u_{ab} k_b + \omega\right)\right) / \left(\sum_a p_a \eta_a\right)\right)\).
A continuum of complete agent types with mass \(p_a\) and repeated item types with supply \(q_b\); \(y_{a,k}\) is the mass of type-\(a\) agents receiving integral bundle \(k\), and welfare is the population-weighted smooth Nash objective.
Covers Theorems 1, 3, and 4 as bundle-preserving high-multiplicity analogues; it does not automatically transfer their stated algorithms or cover the paper's integrality-gap characterization, online setting, vector-valued extensions, or fairness directions.
This paper does admit a credible continuous mirror. My lead is its smooth asymmetric Nash-welfare result, Theorem 3. The paper does not contain a named NP-hardness theorem of its own, so the positive case rests on its named approximation theorems rather than on hardness transfer.
The natural regime is a large advertising or allocation market with repeated agent and item types. There are \(N\) advertisers, households, or demand units, but only \(r\ll N\) complete agent types. A type includes the entire utility vector over item categories, the concave valuation, the Nash weight, and any budget or smoothing parameter. There are also many repeated impression or resource opportunities, described by \(s\) item types with supplies \(q_b\). Thus a finite lift has \(Np_a\) agents of type \(a\) and \(Nq_b\) indivisible copies of item type \(b\), with \(N\) potentially enormous while \(r\) and \(s\) remain modest.
Let \(x_{ab}\) be the mass of item type \(b\) assigned to agent type \(a\):
\[ x_{ab}\ge 0,\qquad \sum_a x_{ab}=q_b. \]
The per-agent utility of type \(a\) is
\[ z_a=\frac{1}{p_a}\sum_b u_{ab}x_{ab}. \]
The continuous object is the population composition \(p\) and its type-level allocation \(x\), not a lottery over final outcomes. Rational masses can be cleared to obtain finite replicated instances, while finite allocations can be aggregated into these type-level variables.
My lead anchor is Theorem 3, an original result of this paper whose proof is included in the supplied text. It states that smooth Asymmetric Nash Welfare Maximization has an algorithm running in time \(O(nm^2/(\epsilon\omega))\) with approximation \(O(e^\epsilon/(\omega\ln(1+1/\omega)))\).
The corresponding problem is:
Type-Smooth-ANW\(_\infty\). Given rational type masses \(p_a\), item supplies \(q_b\), utilities \(u_{ab}\), positive type weights \(\eta_a\), smoothing parameter \(\omega\in(0,1]\), and accuracy \(\epsilon\), find a feasible \(x\) maximizing
\[ \operatorname{NW}_\infty(x) = \exp\left( \frac{1}{\bar\eta} \sum_a p_a\eta_a\ln(z_a+\omega) \right), \qquad \bar\eta=\sum_a p_a\eta_a. \]
A solution is a feasible type-level allocation whose value is within the requested multiplicative or additive-logarithmic accuracy of the optimum.
I expect this problem to be Class A. Its log objective is concave in \(x\), and the feasible region is a transportation polytope. Hence it is a finite-dimensional convex-optimization problem whose dimension depends on \(r\) and \(s\), not on the number of named agents. Moreover, the paper’s Weighted Bang-Per-Buck interpretation compresses naturally: all agents of type \(a\) share one bid, and every item type \(b\) is assigned according to the maximum ratio \((\eta_a u_{ab})/b_a\). Theorem 3’s algorithm is therefore not merely an approximation theorem to cite; it suggests a type-compressed dual algorithm.
This is author-recognizable. The paper itself motivates ICA through internet advertising, soft budgets, under-delivery, and repeated impression opportunities. A market with millions of standardized campaigns or demand cohorts is a sensible high-multiplicity version of exactly that setting.
The first secondary anchor is Theorem 1, also an original result of the paper, with its proof deferred to the full version. It gives a \((1+\epsilon)\max_i\mu_i\)-approximation for general differentiable concave-additive valuations, in time \(O(mn\ln(\rho_{\max}/\epsilon)/\epsilon)\).
The associated problem is:
Type-ICA\(_\infty\). Given rational masses \(p_a\), supplies \(q_b\), utility coefficients \(u_{ab}\), and monotone concave differentiable functions \(v_a\), find a feasible \(x\) maximizing
\[ F_\infty(x)=\sum_a p_a v_a(z_a). \]
For a bit-complexity formulation, the \(v_a\) may be supplied by polynomial-time value and derivative oracles, or restricted to an explicitly encoded rational function class. The output is an \(\epsilon\)-optimal allocation, or an allocation satisfying the paper’s curvature-dependent approximation guarantee.
I again expect Class A for the aggregate continuous problem. Maximizing a concave objective over a linear feasible region is convex optimization. The paper’s local-curvature parameter explains what happens to the finite indivisibility loss: Theorem 2 identifies that loss with the integrality gap of the assignment convex program. In the type-level fluid limit, the assignment program itself is the natural object, so the curvature barrier should either become exact or remain only as a finite-precision/rounding term.
The second secondary anchor is Theorem 4, an original result stated in this paper with proof deferred to the full version. It treats piecewise-linear concave valuations satisfying
\[ \min_k(x_{a,k+1}-x_{a,k}) \ge \max_b u_{ab}, \]
and obtains an approximation at most \((1+\epsilon)\max_i\mu_i\le (1+\epsilon)^{4/3}\).
The mirror is:
Type-PL-ICA\(_\infty\). The input is the same type-and-supply data, with every \(v_a\) given by rational concave linear segments satisfying the displayed segment-length condition. Find \(x\) maximizing \(F_\infty(x)\).
This version is particularly clean computationally. Introduce \(z_a\) and a welfare variable \(w_a\); because a concave piecewise-linear function is the lower envelope of its supporting lines, the problem becomes a linear program. I therefore expect this mirror to be Class A, in fact exactly solvable to arbitrary rational precision. It covers the paper’s piecewise-linear allocation result without pretending that fractional outcomes alone are the contribution: the continuous variable is the mass of a large population assigned across repeated item categories.
The scope is deliberately narrow. These mirrors cover the paper’s offline ICA welfare problem and its smooth asymmetric Nash-welfare application. They do not cover the online Devanur–Jain setting, vector-monotone valuations, the paper’s fairness suggestions, or the full finite-item approximation landscape.
The weakest point is real: \(x_{ab}\) represents type-level, per-capita allocation, so it can wash out the indivisible bundle received by any particular agent. If the authors regard indivisibility as the essential question, they may say this has become the divisible problem already distinguished in the introduction.
There is a more faithful follow-up formulation. Let \(y_{a,S}\) be the mass of agents of type \(a\) receiving an integral bundle \(S\). Then
\[ \sum_S y_{a,S}=p_a, \qquad \sum_{a,S} |S|_b\,y_{a,S}=q_b, \]
and the objective is
\[ \sum_{a,S}y_{a,S} v_a\!\left(\sum_b u_{ab}|S|_b\right), \]
or the corresponding weighted logarithmic Nash objective. This preserves indivisible bundles while making the population continuous. It is a configuration LP whose pricing problem may itself be knapsack-like; that could be a genuine Class C boundary. The aggregate \(x\)-mirror is therefore strongest in markets with very many small repeated opportunities, while the configuration version is the right next question when individual bundle integrality must survive.
That concession does not destroy the positive case. The paper’s own convex program, curvature analysis, and smooth Nash-welfare application all point toward a meaningful high-multiplicity allocation theory. The mirror is not “the paper is already continuous”; it is a new question about whether the paper’s algorithms and curvature guarantees compress from millions of named agents to a small number of complete population types.
The strongest negative case is that the proponent’s written mirrors are not actually population continuizations of ICA. They replace indivisible bundles by fractional assignment and then evaluate each type’s valuation at its average utility. Those operations do not commute with concavity.
Take \(N\) identical agents, \(N/2\) identical unit items, \(u_{ij}=1\), and \(v(z)=\log(z+\omega)\). Every finite integral allocation gives half the agents utility \(1\) and half utility \(0\), so the per-agent log welfare is
\[ \tfrac12\log(1+\omega)+\tfrac12\log\omega. \]
The proposed \(x\)-model gives every type average utility \(1/2\), and therefore value
\[ \log(\tfrac12+\omega). \]
The gap is strict and remains constant as \(N\) tends to infinity. Clearing rational masses into a finite replicated instance does not remove it. The proposed model is therefore the divisible-goods relaxation, not the high-multiplicity limit of the indivisible problem.
This defeats the lead anchor, Theorem 3, as stated. Its type-level WBB algorithm is simply a market-style algorithm for the fractional allocation problem. The paper itself already identifies divisible Nash welfare as an Eisenberg–Gale convex-program setting. Smoothing by \(\omega\) does not restore the missing individual bundle structure; it merely makes the fractional objective well behaved.
The same objection defeats Theorem 1. Theorem 2’s curvature parameter is explicitly the integrality gap of the individual assignment convex program. In the proposed \(x\)-mirror, that relaxation has been made into the model, so the central object whose gap the paper characterizes has disappeared. The resulting convex program may be computationally useful, but it is not a continuous version of the theorem’s indivisible welfare problem. It is the standard fluid allocation problem that the introduction distinguishes from ICA.
Theorem 4 fares no better. The piecewise-linear representation does make the \(x\)-problem an LP, but that is precisely because the indivisible allocation has been relaxed away. The segment-length condition controls the effect of assigning one discrete item to one named agent; it says nothing about the distribution of integral bundles among a continuum of agents. Thus the claimed exact LP is not evidence that the paper’s piecewise-linear indivisible result has a continuous mirror.
The advertising story also requires more structure than the proponent acknowledges. To obtain genuine type compression, agents must share their complete utility vectors, valuation functions, weights, smoothing parameters, and every other relevant attribute. The impression side must likewise consist of repeated item categories with identical value vectors. If impressions remain individually contextualized by user, time, and placement—as they normally are—the number of item types grows with the instance and the proposed compression disappears. If both agents and impressions are standardized, that is a plausible new two-sided high-multiplicity market, but it is no longer obviously the setting studied by this paper.
There is, however, a better mirror, and this is where the negative case becomes weak. The faithful population limit should introduce configuration masses \(y_{a,k}\), where \(k\) is an integral bundle-count vector:
\[ \sum_k y_{a,k}=p_a,\qquad \sum_{a,k} k_b y_{a,k}=q_b. \]
The objective is the population average of \(v_a(\sum_b u_{ab}k_b)\), or of the corresponding logarithmic Nash objective. This preserves the fact that every individual receives an indivisible bundle while allowing a continuum of identical agents to be split across different bundles.
That repaired formulation is legitimate and potentially interesting. Its dual pricing problem has the form
\[ \max_{k\in\mathbb Z_{\ge0}^s} \left[ v_a\!\left(\sum_b u_{ab}k_b\right)-\sum_b\pi_b k_b \right], \]
which is a genuine configuration-pricing question and may be tractable, parameterized, or hard depending on the type space. It is exactly the kind of boundary problem the ChoCo programme wants to study.
The best negative claim, then, is limited: the three proposed \(x\)-mirrors fail because they confuse population continuity with divisible outcomes, and the paper’s curvature and WBB results do not survive that correction. But I cannot honestly defend the universal claim that no worthwhile mirror exists. The configuration formulation is a credible high-multiplicity continuation of Theorems 1, 3, and 4, even though it becomes a new configuration-allocation problem rather than a direct type-compressed version of the paper’s algorithms.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.