| paper | d4-conf-ecai-2025-0444 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→other discrete result → its continuous mirror
Answer: Yes; a feasible plan with the required welfare guarantee can be computed in time \(f(m)\operatorname{poly}(\tau,L,1/\epsilon)\), with at most \(\tau+m+1\) atoms. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given rational type masses \(\mu_t\), valuations \(v_t\in\mathbb{Q}_{\ge0}^d\), and per-capita supplies \(q_j\), with cash supply \(\sigma=cv_{\max}\) for fixed \(c>1/2\), compute a finite-support plan \(\pi_t\) over integral bundles \(k\in\mathbb{Z}_{\ge0}^d\) and cash \(r\ge0\). Require \(\pi_t\) to have total mass \(\mu_t\), \(\sum_t\int k_j\,d\pi_t\le q_j\), and \(\sum_t\int r\,d\pi_t\le\sigma\); achieve \(W(\pi)=\exp(\sum_t\int\log(v_t\cdot k+r)\,d\pi_t)\ge(1-\epsilon)F/B(c)\) in time \(f(d)\operatorname{poly}(\tau,L,1/\epsilon)\), where \(F\) is the fractional MNW optimum under the same per-capita supplies.
A continuum of agents with \(\tau\) complete valuation types and masses \(\mu_t\); indivisible good categories have per-capita supplies \(q_j\), and common-value divisible cash has supply \(cv_{\max}\) per capita. A plan assigns each unit of mass an integral bundle and cash, and maximizes population Nash welfare against the type-level fractional MNW benchmark.
The mirror covers Theorem 2's rounding guarantee for mixed MNW with per-capita money; it leaves the thresholds and lower bounds in Theorem 1, Example 1, and Theorems 3–4, as well as the experiments, outside.
The cleanest anchor is Theorem 2, proved in this paper. It says that for any mixed-goods instance and any constant \(c>1/2\), Algorithm A produces an integral allocation with integrality gap at most
\[
B(c)=\max_{\alpha\in[0,1]}\left(\frac{2c}{2c-1+\alpha}\right)^\alpha
\]
when the money supply is \(s=cnv_{\max}\). For example, \(c=1\) gives a bound below \(1.16\), and \(c=2\) gives one below \(1.07\). Algorithm A starts from a fractional MNW allocation, rounds each shared item to an agent with the largest share, compensates agents for their utility losses, and distributes the remaining money. The paper presents this as a polynomial scheme. Its introductory APX-hardness statement for indivisible MNW is attributed to earlier work; it is not a numbered hardness theorem proved here.
My proposed mirror is Mass-MNW-Rounding. Picture a large public benefit programme distributing standardized, indivisible equipment from bulk inventories, with cash available for balancing. Millions of households may be eligible, while their additive valuations over a modest catalog fall into \(\tau\) complete types. For example, a type records the household’s value for every good category, plus any eligibility or price information the problem uses. Inventory grows with the eligible population: a category has \(q_j\) copies per person, and the cash pool has \(\sigma=c v_{\max}\) per person. This scaling keeps the allocation meaningful as the population grows.
Formally, let \(\mu_t\) be the mass of type \(t\), with \(\sum_t\mu_t=1\), and let \(v_t\in\mathbb{Q}_{\ge0}^d\) be its valuation vector over \(d\) good categories. An allocation plan \(\pi_t\) assigns mass of type \(t\) to pairs \((k,r)\), where \(k\in\mathbb{Z}_{\ge0}^d\) is an integral bundle and \(r\ge0\) is cash. Feasibility requires
\[
\pi_t(\mathbb{Z}_{\ge0}^d\times\mathbb{R}_{\ge0})=\mu_t,\qquad
\sum_t\int k_j\,d\pi_t\le q_j,\qquad
\sum_t\int r\,d\pi_t\le\sigma.
\]
Its population Nash welfare is
\[
W(\pi)=\exp\!\left(\sum_t\int\log(v_t\cdot k+r)\,d\pi_t\right).
\]
Thus every individual receives a whole bundle; mass records how much of a type receives each bundle and cash amount.
Define \(F\) as the fractional MNW benchmark:
\[
F=\exp\!\left(
\max_{x_t\ge0,\ r_t\ge0}
\sum_t\mu_t\log(v_t\cdot x_t+r_t)
\right),
\]
subject to \(\sum_t\mu_t x_{tj}\le q_j\) and \(\sum_t\mu_t r_t\le\sigma\). The question is: given rational \((\mu,v,q)\), fixed rational \(c>1/2\), and \(\epsilon>0\), can we output a finite-support mass allocation plan with
\[
W(\pi)\ge (1-\epsilon)\frac{F}{B(c)}
\]
in time \(f(d)\operatorname{poly}(\tau,L,1/\epsilon)\), where \(L\) is the input bit length? The solution is a list of type masses, integral bundles, and cash allocations.
I expect Class A in the parameterized form above. The mass-allocation formulation is a configuration LP: each type’s possible whole bundles and cash amounts are configurations, with type mass and resource supplies as constraints. Column generation would reduce the computational hinge to pricing a configuration; for fixed \(d\), that looks like a plausible FPT target. The central open technical question is whether pricing can be done with the required dependence on \(d\) and bit length. Further questions include whether the factor \(B(c)\) is tight for this population model, and whether a fixed-\(\tau\) instance can preserve a gap above \(1\) even with per-capita money.
The scope is Theorem 2’s mixed-MNW approximation guarantee. It does not claim that exact MNW becomes easy, or cover the paper’s other fairness claims. The mirror is plausible because agents are grouped by the complete valuation information the original problem uses, while goods remain indivisible for each recipient and cash remains divisible. The weakest point is computational: applying the paper’s algorithm after expanding a rational population into \(N\) agents may take time polynomial in \(N\), which can be exponential in \(L\). A compressed algorithm needs the configuration-pricing step to work. That is precisely the question the mirror puts on the table.
The strongest case against this anchor is that the paper already gives its proposed welfare guarantee after expanding a rational type distribution into a finite population. Choose a population size \(N\) that realizes the type masses and per capita inventories exactly, apply Theorem 2 with money \(cNv_{\max}\), then aggregate the resulting agents by type and bundle. Symmetry among agents of the same type lets the fractional benchmark match \(F\). So the bound \(B(c)\) itself is not an open continuous result; the only new claim in the proposed mirror is that the algorithm can avoid expanding \(N\), whose size may be exponential in the input bit length.
That is a real qualification, but it does not defeat the mirror. A runtime polynomial in the expanded population is not a runtime polynomial in \((\tau,L)\), and the proposed configuration problem asks exactly whether the guarantee can be computed from the succinct type description. Theorem 2 does not answer that. Nor does the paper’s fractional allocation model already make the population continuous: the original instance still has finitely many agents.
The natural objections about multiplicity or a vanishing integrality gap also fail. For example, use three types: \(A\) and \(B\), each of mass \(1/4\), and a zero-value type \(P\) of mass \(1/2\). Give \(A\) and \(B\) two personal goods per agent and one shared good per \(A\)-\(B\) pair, with each valued at \(1\) by its intended recipients. With money supply \(1\) per capita, the fractional benchmark can give each rich agent utility \(2.5\) and each \(P\)-agent utility \(2\). An integral allocation leaves half the rich agents at utility \(2\) and half at \(3\), while the \(P\)-agents get \(2\). The gap remains \( \sqrt{2.5/\sqrt{6}} > 1 \) in the population limit, using only three types and three good categories. Thus a repeated-cohort scenario is credible, and the continuum need not erase the phenomenon.
So I cannot honestly make the requested universal negative case. The skeptical point is that the paper’s approximation factor already transfers by finite replication; the proposed contribution is compressed computation, not a new factor bound. But under ChoCo’s stated interest in high-multiplicity computational questions, that is a meaningful question, and I see no fundamental obstruction that rules it out across scenarios.
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.