| paper | Utilitarians Without Utilities: Maximizing Social Welfare for Graph Problems Using Only Ordinal Preferences |
| authors | Ben Abramowitz, Elliot Anshelevich |
| venue | AAAI 2018 |
| filed under | fairalloc · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: A deterministic ordinal \(2\)-approximation exists and runs in time polynomial in \(m=\tau\), \(L\), and \(\log(b+1)\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu\), an integer degree bound \(b\), and ordinal rankings of partner types, output a symmetric link-mass matrix \(x\) using only those rankings. Require \(x_{tu}\ge0\), \(x_{tu}=x_{ut}\), \(x_{tt}\le\mu_t/2\), and \(2x_{tt}+\sum_{u\ne t}x_{tu}\le b\mu_t\) for every \(t\). For every symmetric nonnegative type-level utility matrix \(w\) consistent with the rankings, require \(W_w(x)\ge\frac12\max_{y\text{ feasible}}W_w(y)\), where \(W_w(x)=\sum_{t<u}w_{tu}x_{tu}+\sum_t w_{tt}x_{tt}\).
A high-multiplicity complete-graph collaboration market with interchangeable types \(T\), population masses \(\mu\), type-level ordinal rankings, symmetric latent utilities \(w_{tu}\), and per-agent degree capacity \(b\). The decision variables are normalized masses of links between type pairs, with additive welfare \(W_w(x)\) and only ordinal information available to the algorithm.
The proposed bulk Ordinal Greedy rule is not yet proved to be refinement-independent or to inherit the factor-\(2\) guarantee exactly after finite clone realization and parity handling.
fatal: False
The mirror covers Theorem 5 and its tight factor-\(2\) guarantee for maximum-weight \(b\)-matching; it leaves the general ABC and AB results, MST, TSP, planar-subgraph, and pairwise-stability results unmirrored.
The strongest honest case is a Class A mirror of Theorem 5, for continuous typed \(b\)-matching. This is an algorithmic anchor rather than a hardness anchor: the paper contains no named NP-hardness or completeness theorem.
The anchor is Theorem 5, proved in this paper:
For any ABC System on \(G\) with \(c=n\) and \(\mathcal A\) equal to all subgraphs of \(G\), Ordinal Greedy constructs a solution within a factor of \(2\) of optimum, and this bound is tight.
Because \(c=n\) removes the component-size constraint and \(\mathcal A\) imposes no restriction, the problem is precisely Maximum Weight \(b\)-Matching: every agent may participate in at most \(b\) edges. The theorem applies for every \(b\), with arbitrary nonnegative symmetric hidden edge weights and only ordinal information available to the algorithm. Its tightness already holds for \(b=1\): with agents \(u_1,u_2,v_1,v_2\), weight-one edges \(u_1u_2\), \(v_1v_2\), and \(u_1v_1\), and weight-zero edge \(u_2v_2\), suitable preferences make Ordinal Greedy choose \(u_1v_1\) and then \(u_2v_2\), obtaining value \(1\), while the optimum obtains value \(2\).
My lead mirror is the following problem.
Consider a large collaboration market containing \(N\) agents divided into \(\tau\) recurring cohorts \(T=\{1,\ldots,\tau\}\). A cohort might be specified by occupation, seniority, location, and collaboration role. Agents in the same cohort have the same collaboration preferences, the same degree limit \(b\), and the same latent utility for each cohort of possible partners. Think of a large annual population of otherwise interchangeable professionals, rather than a seven-person committee with individually idiosyncratic relationships. Here \(N\) is large while \(\tau\) is fixed or moderate.
The input is a rational mass vector \(\mu\), where \(\mu_t\) is the fraction of agents in cohort \(t\), together with an ordinal ranking \(\succ_t\) of partner cohorts for every \(t\). There is an unknown symmetric type-level utility \(w_{tu}=w_{ut}\ge0\), consistent with the rankings: if \(u\succ_t v\), then \(w_{tu}\ge w_{tv}\). Agents within a cohort are anonymous, so ties between particular clones inside one partner cohort are immaterial; an arbitrary strict refinement can be used in a finite blow-up.
The decision variable is a symmetric matrix of link masses \(x\). For \(t\ne u\), \(x_{tu}\) is the number of \(t\)-to-\(u\) links per unit population; \(x_{tt}\) is the number of links between distinct agents of type \(t\), again normalized by \(N\). Feasibility is
\[ x_{tu}\ge0,\qquad x_{tu}=x_{ut},\qquad 2x_{tt}+\sum_{u\ne t}x_{tu}\le b\mu_t \]
for every type \(t\). The factor \(2\) reflects that an internal type-\(t\) link consumes one degree at each endpoint. For a latent utility matrix \(w\), the normalized welfare is
\[ W_w(x)=\sum_{t<u}w_{tu}x_{tu}+\sum_t w_{tt}x_{tt}. \]
The continuous problem, which I would call \(\mathrm{Ordinal\ Typed}\ b\text{-Matching}_\infty\), is:
Given \((T,\mu,b,\succ)\), output a feasible link-mass matrix \(x\), using only the ordinal rankings, such that for every symmetric \(w\) consistent with those rankings,
\[ > W_w(x)\ge \frac{1}{2}\max_{y\text{ feasible}}W_w(y). > \]
The natural algorithm is a type-level version of Ordinal Greedy. It repeatedly chooses an undominated available type pair according to the current ordinal information and sends as much remaining mass as the residual degree capacities permit. Thus mass is genuinely active: the algorithm decides how much of each cohort participates in each kind of link. It is not merely using \(\mu\) as a passive coefficient in an unchanged committee or project problem.
This is a recognizable continuous analogue of the paper’s question. The agents still form a maximum-utility network subject to degree constraints; utilities are still latent and only ordinal information is available; the output is still a feasible \(b\)-matching. The only substantive change is that repeated, interchangeable agents are represented by their masses. For rational \(\mu\), clearing denominators produces a finite population with \(N\mu_t\) clones of each type. Conversely, projecting a finite matching onto cohort pairs produces \(x\). With sufficiently large \(N\), parity and rounding effects vanish, and the normalized objective converges to \(W_w(x)\).
I would expect this mirror to be tractable, in Class A. The paper’s charging proof for Theorem 5 is local to degree constraints and does not use connectivity, named identities, or geometry. Those are precisely the features that survive cohort aggregation. A finite blow-up of the typed instance gives an ordinary instance to which Theorem 5 applies; taking the normalized high-multiplicity limit should yield the factor \(2\) guarantee. With \(w\) known, the continuous optimization problem is itself a finite linear program over the \(x_{tu}\), and the ordinal algorithm should not need to solve that LP or know \(w\).
The further questions are useful rather than cosmetic. One should prove an exact rational-clone theorem, including the realization of every relevant \(x\) by a simple finite \(b\)-matching and the treatment of parity. One should determine whether a canonical type-level Ordinal Greedy achieves factor \(2\) exactly or only \(2+o(1)\) before rounding. It is also worth asking whether heterogeneous degree limits, bipartite cohort markets, or type-dependent link costs preserve the result. Finally, if one adds component-size or attachment constraints, the mirror may cease to be straightforward: type-pair masses do not by themselves preserve connectivity or planarity.
I would not claim that this covers the paper’s MST, TSP, or planar-subgraph results. Those constraints depend on relational structure that marginal type masses can erase. The proposed mirror deliberately covers only Theorem 5, where the underlying \(b\)-matching problem has no such global structural constraint.
The weakest point is that the paper’s original input gives every named agent a strict ordering over other named agents, whereas the mirror gives each cohort a ranking over anonymous partner cohorts. That is an extension of the input semantics, not a literal replacement of \(n\) by \(\mu\). The case survives because the chosen high-multiplicity scenario makes identities irrelevant: utilities are constant on type pairs, and the only feasibility constraint is per-agent degree. In that regime the type-pair link masses retain the computational object rather than replacing it with a different social-choice problem.
The only serious anchor is Theorem 5, and I cannot honestly defeat it. The proposed typed \(b\)-matching mirror is a sensible high-multiplicity regime: agents are interchangeable for every feature relevant to the problem, welfare is additive over links, and the degree constraint is preserved by the mass inequalities. This is exactly the kind of population continuization the programme permits.
The strongest objection is that Ordinal Greedy is defined on named edges. Once many agents share a type, the type-level rankings do not specify how ties among individual clones are refined. Different refinements can produce different matchings, while the mass vector \(\mu\) alone cannot recover those critical iterations. Moreover, the proposed rule that sends “as much mass as possible” along a type pair is not literally the paper’s Ordinal Greedy algorithm; it is a new bulk operation whose factor-\(2\) guarantee still requires proof.
That objection does not survive the best repair. One can fix a canonical measurable refinement, or define the continuous algorithm directly on residual type capacities. For rational \(\mu\), any resulting mass solution can be approximated by finite \(b\)-matchings after clearing denominators; conversely, finite matchings project to type-pair masses. Since the paper’s charging proof is local to degree constraints and additive edge welfare, its charges can be normalized and aggregated. The factor-\(2\) guarantee should therefore pass to the limit, with only parity and rounding issues.
Nor can this be rejected because it is “already continuous” or because the answer may be inherited from the finite theorem. The existing result is finite, and the proposed question still asks for a formal continuous model, a precise clone-realization theorem, and an ordinal algorithm over masses. High multiplicity is evidence for the mirror, not a collision.
The MST, TSP, and planar-subgraph results would be much weaker anchors because type-pair masses erase connectivity and planarity. But Theorem 5 needs only the \(b\)-matching anchor, and that anchor survives. The honest negative case is therefore weak: at most, it shows that the proponent has stated a plausible mirror whose algorithmic and realization details remain to be proved, not 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.