| paper | d4-conf-ecai-2023-0323 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3.
statement extracted from the paper’s text layer
Given rational data for three types \(t\), with masses \(\mu_t\) summing to \(1\), additive valuations \(v_t\), budgets \(B_t\), item costs \(c_g\), and per-capita supplies \(q_g\), assign mass \(x_{t,k}\) of each type to integral bundles \(k\in\mathbb{Z}_{\ge 0}^m\). Require \(\sum_k x_{t,k}=\mu_t\), \(\sum_{t,k}x_{t,k}k_g\le q_g\), and budget feasibility for each assigned bundle. Require every positive-mass recipient of bundle \(k\) to satisfy EFx against every bundle \(\ell\) in the allocation’s support, using their type’s valuation and budget. Is there a polynomial-time algorithm, in \(m\) and the rational input bit length, that returns a sparse rational mass allocation with EFx and population NSW at least \(\rho\) times the maximum NSW among budget-feasible allocations with the same mass and supply constraints, for some absolute constant \(\rho>0\)?
A society with three complete agent types and masses \(\mu_t\), receiving integral bundles \(k\) in proportions \(x_{t,k}\). Each type has an additive valuation and budget; item categories have rational per-capita supplies \(q_g\). EFx applies across every bundle in the allocation’s support, and population NSW is \(\exp(\sum_{t,k}x_{t,k}\log v_t(k))\).
The mirror targets Theorem 3’s budget-feasible EFx allocation and constant NSW approximation objective. It does not cover Theorem 1’s two-agent impossibility and approximation bound.
The paper has no numbered theorem classifying a problem as NP-hard, in P, or parameterized-hard. Its strongest named computational anchor is Theorem 3, proved in this paper: for exactly three agents, Procedure \(\threealgoDB\) returns a budget-feasible EFx allocation whose Nash social welfare is within a constant factor of the unrestricted optimum. The proof gives the explicit factor \(1/171\), using \(\alpha=1/35\). That is an approximation-algorithm result, not a running-time classification.
A plausible mirror is Three-Type Continuous Budgeted EFx-NSW. Consider a large population represented by three types. A type \(t\) specifies an agent’s complete additive valuation vector \(v_t\) and budget \(B_t\); its mass \(\mu_t\) is its fraction of the population, with \(\sum_t\mu_t=1\). There is a catalog of \(m\) item types, each with cost \(c_g\) and rational per-capita supply \(q_g\). An individual still receives an *integral* bundle \(k\in\mathbb Z_{\ge0}^m\), feasible for type \(t\) when \(\sum_g c_gk_g\le B_t\). The variable \(x_{t,k}\) is the mass of type \(t\) receiving bundle \(k\), subject to \(\sum_k x_{t,k}=\mu_t\) and \(\sum_{t,k}x_{t,k}k_g\le q_g\) for every item type \(g\). Unused supply is charity.
Fairness applies to the represented individuals, not just to type averages. For every bundle \(k\) assigned to positive mass of type \(t\), every bundle \(\ell\) assigned to positive mass of any type, every integral subbundle \(r\le\ell\) affordable to \(t\), and every item \(g\) in \(r\), require \(v_t(k)\ge v_t(r-e_g)\). Thus each recipient is EFx-safe against every bundle anyone receives, including other recipients of their own type. Define population NSW as \(\exp(\sum_{t,k}x_{t,k}\log v_t(k))\), with value zero if positive mass receives zero utility; compare it with the maximum NSW over allocations satisfying the mass, supply, and budget constraints but not necessarily EFx.
The question to hand a prover is: given the rational type data and supplies in binary, can one find a sparse rational mass allocation that is EFx and achieves \(\rho\cdot\mathrm{OPT}\) NSW for some absolute \(\rho>0\), in time polynomial in \(m\) and the input bit length? The three-type restriction keeps the model close to Theorem 3 while allowing the population to be genuinely continuous. The anchor does not establish that the \(1/171\) guarantee, or any constant guarantee, survives.
A credible regime is a large benefits or equipment programme with three standardized recipient classes: millions of people share a few combinations of valuations and capacity budgets, while the inventory of each item category scales with population. Then \(N\) is large and the number of distinct types is three. A mass assigned to a bundle means that fraction of a class receives that integral bundle. Repeated per-capita inventory is a co-modification needed for this setting; the population remains the continuous object.
I would first pursue Class A, via a configuration LP: for a fixed compatible set of bundles, the mass and supply constraints are linear, and log-NSW is linear in the assigned masses. The hard step is finding a compatible bundle support or solving its pricing problem under budget and EFx constraints. That could instead expose continuum-specific hardness. Further questions include whether solutions have polynomial-size support, how the optimum relates to discrete high-multiplicity instances with \(\mu_t=n_t/N\), and whether the approach extends from three types to arbitrary \(\tau\).
The authors could recognize this as a continuous version of their budget-feasible EFx-versus-NSW problem: it retains additive values, individual budgets, integral bundles, and their fairness and welfare criteria. The paper itself also points toward larger populations by raising the arbitrary-agent case as an open problem.
The weak point is substantial: Theorem 3 handles three named individuals. Its procedure sets aside individual goods and reasons about those three agents’ bundles; it does not allocate mass among many recipients of the same type. In the mirror, one type may be spread across several bundles, and every such bundle must satisfy the cross-recipient EFx comparisons. So the theorem is a strong anchor for the *question*, not evidence that its guarantee transfers.
The strongest objection is that Theorem 3 is about three named agents, not a population of three types. Its construction sets aside one good for each agent, uses EFx allocations for pairs of agents, and reasons about envy among those three bundles. The result gives a constant welfare guarantee, but states no running-time bound; its procedure even starts from a maximum-NSW allocation. So the proposed polynomial-time question does not mirror a complexity result established by the theorem.
The population model also adds substantive structure. Scalable per-capita supplies and the option for each type’s mass to receive several different bundles turn the problem into a market with shared inventories. EFx must hold across every bundle in the allocation’s support, including bundles received by members of the same type. Theorem 3’s three-agent argument does not address these support-wide constraints. If each type were forced to receive just one bundle, the model would be closer to the theorem, but that restriction would discard the natural mass-allocation question.
That objection defeats the claim that Theorem 3 directly supports the proposed continuous algorithm. It does not defeat the better mirror: a large benefits programme with repeated item categories, standardized budgets and valuations, integral individual bundles, and per-capita inventory is a credible high-multiplicity regime. Nor does indivisibility invalidate the mirror: masses can be assigned to integral bundles, preserving the meaning of removing one item for EFx. The paper’s open question about arbitrary numbers of agents also makes this extension recognizable to its authors.
So the honest negative case is limited. The proposed model is substantially broader than Theorem 3, and the theorem gives no basis for expecting its guarantee or an efficient algorithm to transfer. But those are reasons to treat the mirror as a new, difficult extension—not reasons to say it is not worth asking. I cannot make a convincing case that no worthwhile continuous mirror exists in any scenario.
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.