| paper | d4-conf-aaai-2011-0254 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Exact welfare maximization is polynomial-time solvable in \(m,\tau,L\); the welfare-threshold decision problem belongs to \(\mathrm{P}\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given rational masses \(\mu_t>0\) summing to \(1\), piecewise-constant valuation types \(t\in T\), their common breakpoint partition \(J\), and a per-capita supply \(\beta\) of each interval, choose type bundles \(x_{tI}\in[0,1]\). With \(U_t(x_t)=\sum_{I\in J}x_{tI}V_t(I)\), maximize \(\sum_{t\in T}\mu_t U_t(x_t)\), subject to \(\sum_{t\in T}\mu_t x_{tI}\le\beta\) for every \(I\in J\) and \(U_t(x_t)\ge U_t(x_s)\) for every pair \(t,s\). What is the exact computational complexity in the support size, partition size, and input bit length?
A continuous population with rational type masses \(\mu\), piecewise-constant valuations, and per-capita interval supply \(\beta\). The decision variables \(x_{tI}\) specify each type's bundle; weighted interval constraints enforce supply, type-pair inequalities enforce envy-freeness, and weighted utility is the objective.
Covers Theorem 1's exact optimum for piecewise-constant valuations; leaves the piecewise-linear results (Theorems 3, 6, and 7) and the general-valuation approximation result (Theorem 9) untouched.
The strongest mirror is Theorem 1, proved here through Algorithm 1: for \(n\) agents with piecewise-constant valuations, the algorithm computes an optimal envy-free allocation in polynomial time. The paper offers no named NP-hardness result, so an algorithmic anchor is the right choice.
I would ask: High-Multiplicity Optimal EF Cake Allocation for Piecewise-Constant Types. An instance gives a finite set \(T\) of \(\tau\) valuation types, rational masses \(\mu_t>0\) summing to \(1\), and a rational per-capita cake supply \(\beta>0\). Each type is a complete valuation density \(v_t\), normalized as in the paper and piecewise constant with rational breakpoints and values. The population may contain \(N\) agents, with \(N\mu_t\) of type \(t\), where \(N\) is large and \(\tau\ll N\). The cake inventory scales with population: each interval has \(N\beta\) copies, so scarcity per person stays fixed as \(N\) grows.
Let \(J\) be the intervals formed by all valuation breakpoints. Choose \(x_{tI}\in[0,1]\), the fraction of interval \(I\) in every type-\(t\) member’s bundle. Write \(V_t(I)=\int_I v_t(x)\,dx\) and \(U_t(x_t)=\sum_{I\in J}x_{tI}V_t(I)\). The task is to return an allocation maximizing
\[ \sum_{t\in T}\mu_t U_t(x_t) \]
subject to
\[ \sum_{t\in T}\mu_t x_{tI}\le \beta \quad (I\in J), \qquad U_t(x_t)\ge U_t(x_s) \quad (t,s\in T). \]
These are individual envy constraints: every member of a type receives that type’s bundle, so comparing representative bundles checks envy for all members. Giving identical members a common fractional bundle is also natural here: averaging same-type bundles preserves feasibility and welfare, and the linear valuations preserve the envy inequalities.
I expect Class A. The formulation is a rational linear program with \(\tau|J|\) variables and \(\tau^2\) envy constraints, so it is solvable in polynomial time in the input size, support size, and number of breakpoints. This mirrors the paper’s actual optimization problem: maximize total value subject to envy-freeness. The new continuous object is the population distribution over valuation types; cake remains the divisible good studied in the paper. A plausible regime is a large audience or workforce with a modest number of repeated schedules of preference over time slots, where inventory grows with cohort size but remains scarce per person.
The mirror covers Theorem 1’s piecewise-constant case, not the paper’s full scope. It raises natural next questions about piecewise-linear or Lipschitz type valuations, and about how running time changes when the support of types grows.
My weakest point is the supply scaling. A literal limit of the paper’s fixed one-cake model would make per-person supply vanish as the population grows. This mirror instead fixes \(\beta\), so total inventory grows with the cohort. That is a real co-modification, but it is a plausible one for large allocation settings and keeps the question recognizably about optimal envy-free division. If the authors require a fixed total cake in the limit, I would not claim this mirror answers that regime.
The strongest objection is to the proponent’s specific scaling: \(N\beta\) copies of every interval turn the paper’s one-cake problem into a replicated-resource economy. That is a real model change, even if it may be plausible for repeated schedules or parallel facilities. The proposed LP also restricts \(x_{tI}\le1\), which can rule out allocations in a fixed-cake model.
But a better mirror survives both objections. Start with the paper’s one cake and \(n\) agents, with \(n_t=n\mu_t\) agents of each piecewise-constant valuation type. If each member of type \(t\) receives fraction \(z_{tI}\) of interval \(I\), set \(x_{tI}=nz_{tI}\). Then the single-cake constraint becomes
\[
\sum_t n_tz_{tI}\le1
\quad\Longleftrightarrow\quad
\sum_t\mu_tx_{tI}\le1.
\]
Every utility is scaled by the same factor \(1/n\), so envy comparisons are unchanged, and total welfare becomes \(\sum_t\mu_tU_t(x_t)\). Dropping the upper bound \(x_{tI}\le1\) gives the fixed-cake type-level LP. Because valuations are constant on each common interval, members of a type can receive equal-value subpieces, making this correspondence implementable in the finite cake model.
So Theorem 1 is a genuine computational anchor, not just a result about fractional outcomes: the paper still has finitely many agents, while the mirror represents the population by type masses. Its polynomial-time result is stated in the paper’s [AAAI proceedings version](https://ojs.aaai.org/index.php/AAAI/article/view/7874). The exact type aggregation may make the mirror easy to derive, but “the answer is immediate” is not a permitted objection here; nor does the paper already formulate the population as continuous. There is no identity dependence or vanishing welfare that defeats the fixed-cake version.
My negative case is therefore weak. The proponent’s inventory-scaled formulation needs correction if it is meant to mirror the original one-cake regime, but the corrected type-mass formulation still gives a recognizable and well-posed mirror of Theorem 1. I cannot honestly defeat this anchor.
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.