| paper | d4-conf-wine-2019-0032 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Solvable in time polynomial in \(m,\tau,L\). · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem O.3
Given an explicit alternative set \(\mathcal A\), rational type masses \(\mu_t>0\) summing to \(1\), rational valuations \(v_t(A)\), and a disagreement alternative \(D\), compute the lexicographically maximal ascending utility quantile among per-type utilities \(u_t\) satisfying \(\sum_t\mu_tu_t=B=\max_{A\in\mathcal A}\sum_t\mu_tv_t(A)\), \(u_t\ge v_t(D)\), and \(\sum_t x_tu_t\le\max_{A\in\mathcal A}\sum_t x_tv_t(A)\) for every \(x\in\prod_t[0,\mu_t]\), where \(B\) is maximum welfare. The selected alternative must attain \(B\), and transfers \(p_t=u_t-v_t(A^*)\) must balance in mass.
Types are complete valuation vectors over an explicit alternative set, with rational masses \(\mu_t\). A type receives per-person utility \(u_t\); a welfare-maximizing alternative \(A^*\) is selected and type-level transfers \(p_t=u_t-v_t(A^*)\) satisfy \(\sum_t\mu_tp_t=0\). Domination is \(u_t\ge v_t(D)\), and the anticore applies to every subpopulation mass vector \(x\in\prod_t[0,\mu_t]\). These fractional-coalition constraints imply that feasible utilities lie in the downward closure of the convex hull of alternative valuation vectors; with total welfare fixed at \(B\), they lie in the convex hull of welfare-maximizing alternatives, intersected with domination constraints. The objective is lexicographic maximization of the ascending population utility quantile.
The mirror covers the general hardness and submodular tractability branches of Theorem O.3. It leaves the paper’s existence, decomposition, continuity, and comparisons with other solution concepts unmirrored.
The strongest anchor is Theorem O.3, proved in this paper. It has two sides. First, when the number of alternatives is polynomially bounded in the number of agents and a disagreement alternative is given, even a weakly polynomial time algorithm for computing the lex-max solution would imply \(P=NP\). Second, when \(W_{\max}\) is submodular, the lex-max solution is computable in strongly polynomial time; this extends to arbitrarily many alternatives when \(W_{\max}\) is available through a value oracle. The paper gives the hardness reduction from maximum independent set; the gap hardness used as its starting point is cited from earlier work.
My lead mirror is Continuous Lexmax-WS. A plausible setting is a large community choosing one of several public projects, with transfers used to share the resulting welfare. The paper’s apartment example has only a few renters, but its underlying model is broader: agents have cardinal valuations over alternatives, utilities are quasi-linear, and transfers are budget balanced. A community with many members drawn from a smaller set of stakeholder profiles fits that model. A type \(t\) is the member’s complete valuation vector \(v_t:\mathcal A\to\mathbb Q\); its mass \(\mu_t\) is its fraction of the population. The input lists the \(\tau\) positive-mass types and their rational masses.
For each type, choose a per-person utility \(u_t\). The selected alternative \(A^*\) must maximize total welfare, so its welfare is \(B=\max_{A\in\mathcal A}\sum_t\mu_t v_t(A)\). Utilities must satisfy \(\sum_t\mu_tu_t=B\), and a type-level transfer \(p_t=u_t-v_t(A^*)\) must balance, \(\sum_t\mu_tp_t=0\). Given a disagreement alternative \(D\), domination requires \(u_t\ge v_t(D)\) for every type. The continuum anticore requires, for every subpopulation mass vector \(x\) with \(0\le x_t\le\mu_t\),
\[
\sum_t x_tu_t\le \max_{A\in\mathcal A}\sum_t x_tv_t(A).
\]
Thus the constraints cover every measurable subpopulation, including a fraction of a type.
Among feasible utility vectors, select the one that lexicographically maximizes the population’s ascending utility quantile function. Equivalently, sort utilities across agents by their population mass and compare the resulting weighted quantile step functions at their first differing interval. This recovers the paper’s sorted-vector lex-max objective when each person has mass \(1/n\). Type-level utilities are a natural representation here: the input is symmetric within a type, and the paper’s finite lex-max utility vector is unique, so identical agents receive identical utilities. A solution consists of a welfare-maximizing alternative and balanced transfers implementing that utility profile.
The computational question is: with \(|\mathcal A|\) polynomial in \(\tau\), can we compute a feasible solution whose per-type utilities are within \(\epsilon\) of the continuous lex-max utilities, in time polynomial in the support size, valuation magnitude, input bit length, and \(1/\epsilon\)? The paper’s theorem makes this a recognizable question about its underlying solution concept, not an encoding question. Its hardness branch motivates asking whether the general continuous problem remains hard; its submodular branch marks a plausible tractable regime. I expect the unrestricted mirror to be hard, provisionally Class C. The submodular case should be a Class A candidate if the finite-agent submodularity and value-oracle conditions have a suitable mass-valued counterpart.
The mirror’s weakest point is the hardness classification. The paper’s reduction uses one agent per graph vertex. In the continuum model, subcoalitions may take arbitrary fractions of each type, adding anticore constraints that the finite reduction did not face. So the reduction does not by itself prove transferred hardness; it needs a continuous adaptation. Class B is plausible because the graph combinatorics remain in the types and alternatives, but I would not claim it until that adaptation is proved. A related limitation is that the reduction uses as many types as vertices, so it demonstrates a continuous-population question without showing a small-support computational gain.
This mirror covers Theorem O.3’s complexity landscape, not the paper’s entire normative contribution or its many comparisons with other sharing rules. The scenario shift from roommates to a large community is plausible under the paper’s own model, while keeping the distinctive question intact: compute the paper’s lex-max welfare-sharing solution for a society described by type masses.
Theorem O.3 is a real computational anchor: it proves hardness for computing lex-max when \(W_{\max}\) is unrestricted, and strong polynomial tractability under submodularity. The best mirror is not the apartment example but a large cooperative choosing among public projects, where many members share complete valuation and disagreement types. That is a plausible high-multiplicity regime, and the paper’s utility and transfer model still makes sense there.
The strongest objection is that the proposed mass-valued anticore changes the feasible utility set substantially. For per-capita utilities \(u_t\), its constraints are
\[
\sum_t x_tu_t\le \max_A\sum_t x_tv_t(A)
\quad\text{for every }x\in[0,\mu].
\]
Because these inequalities are homogeneous, every nonnegative direction can be scaled down to fit inside \([0,\mu]\). They therefore constrain \(u\) against every nonnegative weight vector, not just against whole-agent coalitions as in the finite paper. Equivalently, \(u\) must lie in the downward closure of the convex hull of the alternative valuation vectors. Together with \(\sum_t\mu_tu_t=\max_A\sum_t\mu_tv_t(A)\), positive type masses force \(u\) into the convex hull of the valuation vectors of welfare-maximizing alternatives.
That is a different redistribution geometry from the paper’s finite-agent anticore. A type may be split into arbitrarily small coalitions, and those coalitions impose weighted constraints the finite model does not have. The maximum-independent-set reduction consequently does not transfer as written; the additional fractional-coalition constraints may change the problem. Restricting coalitions to whole types would avoid that change, but would be a poor nonatomic model when members of a type are meant to be interchangeable units of mass.
This is a strong reason to withhold any claim that the continuous version inherits Theorem O.3’s hardness classification. It is not a strong reason to reject the mirror itself: the fractional-coalition anticore is a natural continuum interpretation, and computing its lex-max sharing rule remains a question the authors could recognize as theirs. The paper’s continuity in valuations does not already answer it. So the honest negative case is weak: the proposed hardness story is unproved and the continuum changes the core, but I cannot make 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.