| paper | Online Elicitation of Necessarily Optimal Matchings |
| authors | Jannik Peters |
| venue | AAAI 2022 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 5
statement extracted from the paper’s text layer
Given finite applicant information types \(P\), house categories \(H\), rational masses \(\mu_p\) with \(\sum_p\mu_p=1\), capacities \(\nu_h\) with \(\sum_h\nu_h=1\), and set-compare transcripts defining feasible rankings \(\mathcal R_p\), does there exist a fixed mass allocation \(x\) with \(\sum_h x_{p,h}=\mu_p\) and \(\sum_p x_{p,h}\le\nu_h\) that is Pareto optimal for every cohort-level completion \((\rho_p)_{p\in P}\in\prod_p\mathcal R_p\)?
A high-multiplicity set-compare NPO-existence problem with applicant masses \(\mu_p\), house capacities \(\nu_h\), mass allocation variables \(x_{p,h}\), and universal Pareto-optimality over feasible cohort rankings.
The proposed model uses one common completion per cohort and divisible house capacities, whereas the paper permits independent completions for named agents and assigns indivisible distinct houses.
fatal: False
The mirror covers Theorem 5's set-compare NPO-existence hardness, but not the online query and competitive-ratio results, hybrid-query results, or rank-maximal results.
The strongest honest mirror is built around Theorem 5, my lead anchor:
“Given partial preferences \(\succ'\) in the set-compare model, it is NP-complete to determine whether a necessarily Pareto-optimal matching exists.”
This theorem is proved in the paper, via the paper’s Theorem 4 and a reduction from \((2,2)\)-E3-SAT. I would not try to mirror the paper’s competitive-ratio results first: their query counts are tied to named individual agents, whereas Theorem 5 already isolates a clean computational decision problem.
The natural regime is a large allocation market with many exchangeable applicants and many repeated positions. Think of annual university or public-housing allocation: there are \(N\) applicants, but only \(\tau\) applicant cohorts, where members of a cohort have the same observed preference information and, in a completed instance, the same ranking of house categories. Each house category \(h\) has capacity \(q_h\), representing many equivalent rooms or positions. The meaningful regime is \(N\gg \tau\), obtained by taking \(K\) copies of every applicant and house role. This is not merely fractionalizing an outcome: each infinitesimal applicant receives one house, while the population of applicants is represented by masses.
Here is the continuous problem I would put before a prover.
Call it Continuous Necessary-Pareto Existence under Set-Compare Information. The instance contains a finite set \(P\) of observed information types, a finite set \(H\) of house categories, rational masses \(\mu_p\ge 0\) with \(\sum_{p\in P}\mu_p=1\), and rational capacities \(\nu_h\ge 0\) with \(\sum_{h\in H}\nu_h=1\). Each \(p\in P\) carries a set of set-compare answers \((S,h)\), meaning that the applicant’s favourite element of \(S\subseteq H\) was reported to be \(h\). Let \(\mathcal R_p\) be the strict rankings of \(H\) consistent with all those answers.
A feasible allocation is a mass matrix \(x=(x_{p,h})\) satisfying \(x_{p,h}\ge 0\), \(\sum_h x_{p,h}=\mu_p\), and \(\sum_p x_{p,h}\le \nu_h\). A completion chooses one ranking \(\rho_p\in\mathcal R_p\) for every information type \(p\). For that completion, \(x\) is Pareto dominated if there is another feasible allocation \(y\) such that the mass assigned to every type can be rearranged from its old houses to its new houses weakly improving every applicant according to \(\rho_p\), with a positive mass strictly improving. The question is whether there exists one allocation \(x\) that is Pareto optimal for every completion \(\rho\). If the answer is yes, the allocation \(x\) is the solution.
The corresponding discrete instance has \(K\mu_p\) copies of each information type and \(K\nu_h\) copies of each house category. Thus the continuous input is the high-multiplicity form of the paper’s problem: the set-compare transcript, the universal quantifier over preference completions, and Pareto optimality are unchanged. Only the population is represented by masses, and identical house copies are represented by capacities.
The original authors should recognize this as their question. Theorem 5 is already about existence of a matching that remains Pareto optimal under every completion of elicited preferences; the continuous problem retains exactly that quantifier and exactly that optimality notion. The capacity version is also not an arbitrary relaxation: it is what one obtains by replacing every one-to-one house in a repeated market by a category containing \(K\) equivalent copies. The one-to-one case is included by setting every capacity to one unit.
My expectation is Class B: hardness should transfer. The reduction behind Theorem 5 is driven by the combinatorics of possible improvement cycles and by the interaction among preference-information constraints. Replicating every hard agent and house role \(K\) times should preserve those interactions while making the population genuinely high-multiplicity. The key lemma still needed is a converse showing that a mass allocation in a no-instance cannot exploit splitting among copies to evade the reduction. If that lemma holds, the discrete NP-hardness survives in the continuous mirror, which is exactly the programme’s Class B phenomenon: the hardness lives in the number of preference and house roles, not in the number of individual people.
That caveat is also the weakest point of the case. The paper’s matching is integral and one-to-one, while the continuous allocation permits different members of one cohort to receive different houses. Fractional or mass splitting might make a no-instance feasible even though no integral matching is necessarily Pareto optimal. If so, the mirror could become tractable through flow or polyhedral methods. But that would be a substantive and useful result, not evidence that the mirror is artificial: it would identify precisely where continuization dissolves the NP-hardness of Theorem 5.
This scope deliberately covers only Theorem 5. It generates several natural follow-ups: whether the hardness survives when \(\tau\) is fixed and only multiplicities grow; whether the mass version admits a flow or separation algorithm; whether allowing completions to split one information cohort among several rankings changes the complexity; and whether the polynomial result of Theorem 11 for necessarily rank-maximal matchings has an analogous continuous max-flow formulation.
The strongest negative case is that Theorem 5 does not lift faithfully to the proposed population model. The paper’s agents have named, individually completed rankings; the set-compare transcript is only partial information about those rankings. A proposed information type \(p\) therefore does not satisfy the programme’s own definition of a type: agents sharing \(p\) need not share the preference that matters to Pareto optimality.
The proponent’s completion model quietly imposes perfect correlation. It chooses one ranking \(\rho_p\) for the entire mass of type \(p\), whereas the paper permits each named agent with the same transcript to have an independent completion. If completions are instead allowed to vary inside a cohort, the state must include a distribution over \((p,\rho)\), or quantify over every measurable allocation of completions within the mass. Then the proposed matrix \(x_{p,h}\) no longer contains enough information to define the paper’s necessary-Pareto property. The two repairs lead to different problems: one changes the uncertainty model, the other changes the state space.
The house side creates a second structural substitution. In the paper, houses are distinct indivisible objects. Replacing them by categories with capacities creates a divisible assignment economy. That may be a sensible new model, but Pareto domination is no longer the paper’s exchange-cycle notion over a single matching. To preserve the original object exactly, one must retain the identities of the house copies and the identities of the agents; that removes the intended aggregation. To aggregate them, one must accept a new mass-transport definition of Pareto efficiency. The issue is not that the notation fails in the limit; it is that identity, indivisibility, and population aggregation cannot all be retained simultaneously here.
The cloning argument is consequently weaker than it appears. Cloning every role \(K\) times gives the same normalized instance for every \(K\): the masses are still the original role proportions, and the capacities are the corresponding proportions. The hard information is carried by the distinct partial-preference roles and house roles, not by a population whose aggregate behavior is newly being computed. That does not make the resulting problem illegitimate, but it makes it a scaled robust-assignment problem rather than an especially compelling continuization of the paper’s elicitation setting.
Nor does the proposed mirror preserve the paper’s central online question. The main results concern adaptive queries, query counts, and competitive ratios against an algorithm knowing the hidden profile. Theorem 5 is a valid static computational anchor, but once one chooses it, the query process disappears. What remains is a new robust-existence problem inspired by the paper, not the paper’s population-scale version of elicitation.
This is enough to reject the proponent’s claim that Theorem 5 already supplies a faithful continuous mirror. It is not enough to establish the requested universal negative. A common-ranking cohort model with interchangeable house capacity is plausible, and the resulting mass Pareto problem could be worthwhile precisely because splitting may change the discrete phenomenon. Theorem 5 is a named computational result, agents are not inherently individuated, and no existing continuous treatment is cited. The honest conclusion is therefore that the negative case is weak: it exposes a serious modelling fork, but it cannot defeat the existence of a worthwhile continuous mirror in every 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.