| paper | Funding Public Projects: A Case for the Nash Product Rule |
| authors | F. Brandl, F. Brandt, Matthias Greger, Dominik Peters, C. Stricker, Warut Suksompong |
| venue | WINE 2021 |
| filed under | multiwinner · pb |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: \(\text{Polynomial-time solvable}\) · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a finite project set \(A\), finite type set \(T\), rational masses \(\mu_\theta\ge 0\) with \(\sum_{\theta\in T}\mu_\theta=1\), per-agent contributions \(c_\theta>0\), and utility vectors \(u_\theta:A\to\mathbb{Q}_{\ge 0}\), let \(V=\sum_{\theta\in T}\mu_\theta c_\theta\) and \(U_\theta(\delta)=\sum_{a\in A}u_\theta(a)\delta(a)\). Compute \(\widehat{\delta}\in\Delta(V)\) such that \(\sum_{\theta\in T}\mu_\theta c_\theta\log U_\theta(\widehat{\delta})\ge\max_{\delta\in\Delta(V)}\sum_{\theta\in T}\mu_\theta c_\theta\log U_\theta(\delta)-\varepsilon\).
A continuum of donor types with mass \(\mu_\theta\); each unit of type \(\theta\) contributes \(c_\theta\) and has utility vector \(u_\theta\). The decision variable is a common funding distribution \(\delta\in\Delta(V)\), optimized for the weighted log-Nash objective \(F_\mu(\delta)=\sum_\theta\mu_\theta c_\theta\log U_\theta(\delta)\), with update \(f_\mu(\delta)(a)=\delta(a)\sum_\theta\mu_\theta c_\theta u_\theta(a)/U_\theta(\delta)\).
The mirror covers Theorem 2 and Section 4.2's computation and dynamic approximation of the Nash funding allocation. It leaves aside Theorem 1 on decomposability, the contribution incentive-compatibility theorem, and the impossibility propositions.
My strongest positive case is a single lead mirror anchored in the paper’s named computational result, Theorem 2. The paper has no named NP-hardness, polynomial-time, FPT, or approximation-complexity theorem, so this cannot support a Class B hardness-transfer story. But Theorem 2 is a genuine algorithmic convergence theorem, and it gives a natural Class A population mirror.
The appropriate setting is a large donor-coordination or employee charity-matching programme. There are millions of donors but only a finite menu of utility-and-budget profiles: donors in the same type have the same utility vector over the charity catalogue, the same budget, and the same per-capita contribution. Let \(A\) be the finite set of projects and \(T\) the finite set of donor types. Type \(\theta\) has mass \(\mu_\theta\), utility function \(u_\theta:A\to\mathbb{Q}_{\ge 0}\), and contribution \(c_\theta>0\). The masses satisfy \(\sum_{\theta\in T}\mu_\theta=1\), and the monetary mass of type \(\theta\) is \(w_\theta=\mu_\theta c_\theta\). Thus the per-capita pool is
\[ V=\sum_{\theta\in T}w_\theta. \]
The regime is \(N\) in the millions, with \(\tau=|T|\) fixed or at least much smaller than \(N\): for example, a large employer uses a finite survey or contribution menu, producing many repeated donor types. This is a genuine high-multiplicity regime. The type is complete for the computation because utility, budget, and contribution are all included among the attributes that affect the rule.
The lead problem is:
\[ \textsc{Continuum-Nash-Funding}_{\varepsilon}. \]
Given \(A,T,\mu,u,c\), output a funding distribution \(\widehat{\delta}\in\Delta(V)\), where \(\delta(a)\) is the per-capita amount assigned to project \(a\), such that
\[ F_{\mu}(\widehat{\delta}) \ge \max_{\delta\in\Delta(V)}F_{\mu}(\delta)-\varepsilon, \]
where
\[ U_\theta(\delta)=\sum_{a\in A}u_\theta(a)\delta(a) \]
and
\[ F_{\mu}(\delta) = \sum_{\theta\in T}w_\theta\log U_\theta(\delta). \]
Equivalently, \(\widehat{\delta}\) must \(\varepsilon\)-approximate the weighted Nash product
\[ \prod_{\theta\in T}U_\theta(\delta)^{w_\theta}. \]
The decision variable is the common project-funding distribution \(\delta\); the contribution schedule is part of the instance, just as the finite paper’s contribution profile \(C\) is fixed when it studies computation of \(\nash(C)\). Types with zero monetary mass are ignored, and we assume every positive-mass type has at least one project of positive utility.
The exact population analogue of the paper’s dynamic is
\[ f_\mu(\delta)(a) = \delta(a) \sum_{\theta\in T} w_\theta \frac{u_\theta(a)}{U_\theta(\delta)}. \]
Starting from a full-support distribution \(\delta^0\), define \(\delta^{k+1}=f_\mu(\delta^k)\). This is not merely an analogy: if a finite electorate is grouped into clone types, with \(\mu_\theta=n_\theta/N\), then after scaling the finite funding distribution by \(1/N\), the finite Nash objective becomes the same weighted objective up to a positive scaling and an additive constant. Rational masses can therefore be expanded into a finite population, while a repeated finite population compresses exactly into this type distribution.
The anchor is Theorem 2, proved in this paper, although its proof adapts an argument of Cover (1984). In full, the theorem says: if every contribution is positive and \(\delta^0\) has full support, then the induced sequence \((\delta^k)_{k\in\mathbb{N}}\) has log Nash values \(F(\delta^k)\) converging to the optimum Nash value. If the Nash distribution is unique, then the distributions \(\delta^k\) themselves converge to that Nash distribution. The theorem is therefore mirrored directly by the convergence claim for \(f_\mu\) above.
I would expect \(\textsc{Continuum-Nash-Funding}_{\varepsilon}\) to be Class A. The objective is concave over an \(m\)-dimensional simplex, and the paper explicitly states that the Nash product can be computed to arbitrary precision by convex programming. The population version has only the type-weighted sum in place of the finite-agent sum. The dynamic supplies an interpretable decentralized approximation, while convex optimization supplies the natural complexity-theoretic route. Exact computation should not be demanded: the paper’s own example produces irrational Nash allocations, so the right output notion is approximation.
The authors should recognize this as their problem rather than a tractable substitute. It preserves their projects, cardinal utilities, contribution weights, pool, Nash-product objective, and dynamic update rule. What changes is precisely the population representation: millions of repeated donors are represented by masses rather than named individuals. The fact that the finite and continuous formulations correspond exactly on rational clone profiles is evidence for the mirror, not a collision; the continuous problem asks for algorithms whose complexity depends on \(m\), \(\tau\), and encoding length rather than on the enormous number of donor copies.
The scope should remain narrow. I would not claim that Theorem 2 automatically continuizes the paper’s contribution incentive-compatibility theorem. In an atomless population, one individual has zero effect on the aggregate distribution, so individual contribution incentives require a separate positive-mass coalition or finite-atom formulation. The mirror covers the computation of the Nash allocation after a contribution profile is given, which is already a substantive result in the paper’s Section 4.2.
The further questions are whether the dynamic admits a polynomial iteration bound in \(m,\tau\), input length, and \(\log(1/\varepsilon)\); how to round a continuous allocation back to a finite donor population; whether the result survives an implicit or very large type catalogue; and what the correct type-level notion of contribution incentive-compatibility should be.
The weakest point is that Theorem 2 proves convergence, not a formal polynomial-time bound. The paper’s stronger computational claim about convex programming is unnumbered. Thus, under an extremely strict anchor rule requiring a named \(P\), NP-hardness, FPT, or approximation theorem, this paper is a weak source. Moreover, the finite-type problem is a high-multiplicity compression of the paper’s finite-agent formula, not a new continuum-specific phenomenon. Still, it is a faithful population mirror with a clear tractable optimization problem, and it uses the paper’s own central computational object rather than replacing it with an unrelated mean-field model.
The proponent’s only serious anchor is Theorem 2, and it is weaker than claimed. It proves asymptotic convergence of an iteration, not a polynomial-time, approximation, parameterized, or complexity result. There is no iteration bound in \(m\), \(\tau\), input length, and \(\log(1/\varepsilon)\), so the dynamic is not, as stated, an approximation algorithm with a computable stopping guarantee. The paper’s sentence that convex programming computes the Nash product to arbitrary precision is an unnumbered observation attributed to earlier work. Under the programme’s named-anchor rule, this is at best borderline computational source material.
More importantly, the proposed continuous problem fails the active-variable test. For a type \(\theta\) with mass \(\mu_\theta\) and per-agent contribution \(c_\theta\), the objective is
\[ \sum_{\theta} \mu_\theta c_\theta \log U_\theta(\delta). \]
If \(\mu_\theta=n_\theta/N\), expanding each type into \(n_\theta\) clones gives
\[ \sum_{i=1}^{N} C_i\log U_i(\delta) = N\sum_{\theta}\mu_\theta c_\theta\log U_\theta(\delta). \]
The positive factor \(N\) does not affect the maximizer. The proposed population model is therefore exactly the paper’s finite objective after grouping identical summands. The same is true of the dynamic:
\[ f_\mu(\delta)(a) = \delta(a)\sum_{\theta}\mu_\theta c_\theta \frac{u_\theta(a)}{U_\theta(\delta)}. \]
It is simply Theorem 2’s finite update with equal terms collected. The population mass is never transferred, allocated, or optimized; it is only a coefficient on a fixed project-side convex program. Thus no new mass-transport LP, separation problem, integrality issue, or continuum-specific computational phenomenon appears.
The donor or employee-matching story is perfectly sensible as a high-multiplicity regime. That is not the objection. The objection is that the paper’s computation already ignores identity and already admits arbitrary positive real contribution weights. Making millions of repeated donors explicit as a distribution provides a useful data-compression dictionary, but it does not turn the paper’s result into a computational question about a continuous society. If \(\tau\) remains finite and explicit, the number of people disappears before the optimization begins. If the type catalogue is implicit, infinite, or accessed through an oracle, that is a new information-model problem, not a continuization of Theorem 2.
The paper’s more distinctive contribution-incentive result does not rescue the mirror. A single atomless agent has zero effect on \(\mu\), \(V\), and \(\delta\), so individual contribution incentive-compatibility becomes vacuous. Replacing the individual by a positive-mass type or cohort creates a coalition-deviation property, with different quantifiers and different changes to the Nash weights. A finite-atom/nonatomic hybrid preserves strategic individuals, but then the strategic content is carried by the atoms rather than by the continuous population. These may be worthwhile new models, but they are not faithful mirrors of the paper’s individual theorem.
So the strongest negative verdict is that this paper supplies no qualifying, worthwhile ChoCo anchor. The proposed problem is a valid weighted Nash-welfare formulation and a legitimate high-multiplicity representation, but it is a thin quotient of the existing model, not a population-continuization that opens a computational landscape. The honest weakness in this case is that, if exact high-multiplicity restatements are accepted as sufficient and Theorem 2 is treated as an algorithmic anchor, the proponent’s mirror should receive a modest green. What it cannot support is the stronger claim that the paper contributes a substantive continuous-computational problem.
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.