| paper | d4-conf-atal-2014-0429 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable; an allocation of value \(\mathrm{OPT}\) can be computed exactly, with only binary-length dependence on \(k\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4
Given a finite set \(T\) of reviewer types with rational masses \(\mu_t\) summing to \(1\), \(q\) interchangeable paper classes with rational per-capita supplies \(\beta_r\) summing to \(k\), and utilities \(u_t(r)\in\{\upsilon_1,\upsilon_2,\upsilon_3\}\), where \(0\le\upsilon_1<\upsilon_2<\upsilon_3\), what is the maximum \(\lambda\) for which there are nonnegative masses \(x_{t,z}\) assigned to integral bundle patterns \(z\in\mathbb Z_{\ge0}^q\), \(\sum_r z_r=k\), such that \(\sum_z x_{t,z}=\mu_t\), \(\sum_{t,z}z_r x_{t,z}\le\beta_r\) for every class \(r\), and \(x_{t,z}>0\) only if \(\sum_r z_r u_t(r)\ge\lambda\)? Determine the problem's complexity in the number of types, classes, and the input bit length.
A configuration LP over reviewer types \(t\), masses \(\mu_t\), and integral \(k\)-item bundle patterns \(z\); variables \(x_{t,z}\) split each type's mass across bundles, class-use constraints enforce supplies \(\beta_r\), and the objective maximizes the minimum utility \(\lambda\).
The mirror covers Theorem 4's three-utility, complete-availability \(k\)-division question when goods are grouped into interchangeable classes with per-capita supplies. It leaves the paper's other results and settings with individually specified goods outside this mirror.
The strongest mirror is the paper’s three-utility hardness result, because it asks whether the difficulty of a discrete maxmin allocation survives when indistinguishable agents can be represented as mass.
The natural regime is a large review network: \(N\) reviewers each receive exactly \(k\) papers, and the paper supply grows proportionally with \(N\). A reviewer’s type is their complete utility vector over a finite set of paper classes; reviewers with the same vector are indistinguishable for the allocation problem. For example, utilities might come from a form with three allowed scores. The regime has \(N\) much larger than the number \(\tau\) of reviewer types. Papers within a class are distinct indivisible tasks with the same utility to every reviewer type, and class supplies scale with the reviewer population.
My anchor is Theorem 4, proved in this paper by a reduction from 3-Dimensional Matching. It states that for every \(k\ge 2\), every \(\varepsilon>0\), and every three values \(0\le\upsilon_1<\upsilon_2<\upsilon_3\), unless \(P=NP\), there is no polynomial-time \((\rho+\varepsilon)\)-approximation for \(k\)-division with utilities in \(\{\upsilon_1,\upsilon_2,\upsilon_3\}\), where
\[
\rho=\frac{\upsilon_2+(k-1)\upsilon_1}
{\min\{2\upsilon_2,\upsilon_1+\upsilon_3\}+(k-2)\upsilon_1}.
\]
The result holds even when every agent can receive every resource.
I would ask about Three-Level Continuous \(k\)-Division. An instance gives a finite set \(T\) of reviewer types with rational masses \(\mu_t\ge 0\), \(\sum_{t\in T}\mu_t=1\); \(q\) paper classes with rational per-capita supplies \(\beta_r\ge 0\), \(\sum_{r=1}^q\beta_r=k\); and utilities \(u_t(r)\in\{\upsilon_1,\upsilon_2,\upsilon_3\}\) for every type and class. Availability is complete. A person must still receive an integral bundle of exactly \(k\) distinct papers. Represent a bundle by \(z\in\mathbb Z_{\ge0}^q\) with \(\sum_r z_r=k\): repeated class entries mean distinct papers from that class.
The question is to maximize the least utility received by any positive mass of reviewers. A solution gives a value \(\lambda\) and nonnegative masses \(x_{t,z}\), where \(x_{t,z}\) is the mass of type \(t\) assigned bundle pattern \(z\), satisfying
\[
\sum_z x_{t,z}=\mu_t,\qquad
\sum_{t,z}z_r x_{t,z}\le\beta_r\ \ \text{for each }r,
\]
and \(x_{t,z}>0\) only when \(\sum_r z_r u_t(r)\ge\lambda\). Thus each individual still gets an integral bundle; only the mass of a type can be divided among different bundle patterns. Since total supply is \(k\) per unit mass and everyone receives \(k\) items, the supply inequalities use all the stock.
I expect this mirror to be tractable. For a fixed candidate \(\lambda\), these constraints form an LP with a column for each eligible type–bundle pair. There can be exponentially many bundles, but the pricing problem appears polynomial for three utility levels: enumerate the counts of bundle items at each of the three levels, then, within each level, take the cheapest resource classes under the LP’s dual prices. There are only \(O(k^2)\) count choices. The optimum \(\lambda\) is one of the \(O(k^2)\) possible sums of \(k\) values from the three utility levels, so one can test those thresholds. This suggests an exact algorithm polynomial in \(\tau,q,k\), and the input bit length, using standard separation-based LP machinery. It would show how Theorem 4’s discrete approximation hardness can dissolve when the population itself becomes continuous.
This mirror keeps the paper’s maxmin objective, additive utilities, exact \(k\)-item bundles, and three-value restriction. It covers Theorem 4’s complete-availability result, not the whole paper or the unrestricted MaxMin Allocation problem. It generates questions about the formal complexity bound for the LP algorithm, its integrality gap against discrete \(k\)-division, and whether pricing becomes hard again with more utility levels or restricted eligibility.
The weakest point is the regime behind the hardness reduction: its agents may have many distinct utility profiles, and its goods are individually specified. Theorem 4 therefore does not transfer directly to this mass model. The case for the mirror rests on the paper’s own maxmin \(k\)-division problem being a sensible question for large populations with repeated complete types, where supply scales per capita. The continuous model deliberately permits a type’s mass to use several integral bundle patterns; whether the authors accept that as the right high-multiplicity version is the key judgment.
The strongest case against a mirror of Theorem 4 is that its hardness comes from a regime with no evident population multiplicity. In the reduction, each agent encodes a distinct 3-dimensional matching triple: its utility profile records that triple’s coordinates. Thus the hard instances have \(\tau=n\), with the combinatorics in the agent–resource incidence structure, not in repeated agents. If we preserve each good’s identity and each agent’s full utility vector, growing the population does not give a fixed type space with per-capita supplies. To obtain that regime, we must also assume many goods are interchangeable within a fixed set of classes. That may describe some large allocation settings, but it is an added symmetry condition, not something Theorem 4 establishes as natural.
The proponent’s stronger mirror handles this point well. A large review pool with a fixed set of paper classes, three utility levels, and class supplies scaling with population is a coherent high-multiplicity problem. Giving each unit of mass an integral \(k\)-item bundle while allowing a type’s mass to split across bundles is consistent with the programme; using the essential minimum over positive mass avoids the zero-measure-agent problem. The stated pricing approach also looks plausible for that model. I cannot dismiss it by saying that the continuous problem becomes tractable: that would be a valuable result, not a reason the question is unworthy.
So the negative case is that this mirror’s relevance rests on a narrower, more symmetric allocation regime than the paper’s hardness result or its examples justify. But that does not defeat the mirror: a large population with repeated reviewer types and interchangeable paper classes is plausible, and the authors could recognize it as their problem. The regime mismatch makes the case for this particular anchor less direct; it does not support the universal claim that no worthwhile continuous mirror exists.
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.