| paper | d4-conf-aaai-2021-1042 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: The decision problem is in \(\mathrm{P}\), and a rational witnessing flow can be computed in polynomial time in \(m,\tau,L\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given rational masses \(\mu_t\) of finitely many reported top-\(k\) preference types \(P_t\), and rational category supplies \(q_j\) with \(\sum_j q_j=1\), decide whether there is a feasible assignment flow \(x_{t,j}\ge 0\), with row sums \(\mu_t\) and column sums \(q_j\), whose measurable implementation gives each agent one whole category and is Pareto optimal under every measurable completion of the reported rankings; return such a flow if one exists. Pareto optimality means there is no feasible reassignment that weakly improves almost every agent and strictly improves a positive mass.
A finite set of interchangeable object categories with rational per-capita supplies, and a society represented by rational masses over reported top-\(k\) preference types. The decision variable is a flow \(x_{t,j}\); it can split a type’s mass across categories, while each individual receives one whole category.
Replacing individually distinct unit-capacity objects with interchangeable categories changes the exchange structure, and the paper’s single-pair characterization gives no algorithmic evidence for the mass version.
fatal: False
Covers the existence and construction questions of Theorems 2 and 6; it leaves matching verification in Theorems 1 and 5 and the online elicitation results in Theorems 3, 4, and 7 unanswered.
The strongest honest case is for a continuous mirror of the paper’s existence and computation problems in a large assignment market. Think of a university placing a very large cohort of students into schools or residence types. Each student receives one whole seat; each school has capacity that scales with the cohort. There may be hundreds of thousands of students but far fewer distinct reported top-\(k\) preference lists, so the society has support \(\tau \ll n\). A type is a reported prefix \(P_t\), shared by mass \(\mu_t\); the unreported suffixes remain the uncertainty quantified over in the paper.
To make the market continuous, let \(O=\{o_1,\ldots,o_m\}\) be the finite set of school or seat categories, with rational per-capita supplies \(q_j\), where \(\sum_j q_j=1\). The population has total mass \(1\), with \(\sum_t\mu_t=1\). An assignment is a measurable function from agents to categories, so every agent still gets one whole category; its aggregate form is a flow \(x_{t,j}\geq 0\) with row sums \(\mu_t\) and column sums \(q_j\). Fractional \(x_{t,j}\) means that a fraction of a cohort receives a category, not that an individual receives a fraction of a seat.
Theorem 2, proved in this paper, is my lead anchor. It says that a top-\(k\) profile admits a necessarily Pareto optimal matching if and only if the revealed agent–object pairs contain a matching of size at least \(n-1\); it also gives a polynomial-time algorithm to decide existence and find an NPO matching when one exists. The continuous question is Necessarily Pareto-Optimal Mass Assignment: given rational masses \(\mu_t\), supplies \(q_j\), and top-\(k\) lists \(P_t\), decide whether there is a feasible mass assignment that is Pareto optimal under *every* measurable completion of those lists, and return such an assignment if there is one. For a completion, Pareto improvement means a feasible reassignment that weakly improves almost every agent and strictly improves a positive mass of them. I expect this problem to be tractable, in Class A: finite support and capacity matching suggest a flow-based extension of the paper’s structural argument. The first question for a prover is whether the \(n-1\) threshold has a meaningful mass analogue. Its normalized value tends to \(1\), but that observation alone does not establish a continuous characterization.
A second, distinct anchor is Theorem 6, also proved here. It gives a polynomial-time algorithm that returns a necessarily rank-maximal matching for a top-\(k\) profile if one exists, and returns NO otherwise. The corresponding problem is Necessarily Rank-Maximal Mass Assignment, with the same input and feasible assignments. For each completion, define the signature \(s_\ell\) as the mass assigned to an agent’s \(\ell\)-th-ranked category. The question is whether some feasible assignment has a lexicographically maximal signature under every completion, and, if so, to return it. I tentatively expect Class A here too: capacities suggest lexicographic transportation algorithms, while the paper supplies an algorithmic starting point for handling completion uncertainty. The main further question is whether its polynomial-time reasoning survives when a type’s mass can be split across categories.
These questions preserve the paper’s computational object: one-sided assignment under incomplete ordinal preferences, with a guarantee against every completion. They change the market scale in the natural way for schools or seat categories: supplies grow with the population, and the solution records how much mass receives each category. The answer sought remains an assignment, not a fractional lottery for an individual. The two anchors are separate: NPO asks for immunity to Pareto improvement, while NRM asks for lexicographic rank optimality under all completions.
The paper has no named hardness result, so these anchors cannot support a claim that population continuization dissolves discrete hardness. Their value is instead to ask whether the paper’s tractable existence problems remain tractable when the society is represented by type masses.
My weakest point is the object side. The paper ranks individually distinct objects, while the large-market scenario treats copies within a school or seat category as interchangeable. That co-modification is plausible for school seats, but it can change the exchange structure behind Theorem 2: with interchangeable copies, an unreviewed assignment need not create the same possible trading cycle as an unreviewed individually labelled object. I would not claim the theorem’s \(n-1\) condition transfers. The mirror survives that gap because its central question—whether a robustly PO or rank-maximal assignment exists in a large society with partial rankings—is still recognizably the authors’ problem.
This case covers Theorems 2 and 6 only. I would leave the online elicitation bounds out: their competitive ratios depend on counting individual next-best queries, and a continuous query-cost model would need its own specification before those results had a faithful mirror.
Theorem 2 and Theorem 6 are real computational anchors, so the “no result to mirror” objection does not apply. Nor does identity dependence rule them out: both criteria use preferences and assignments, not agents’ names. A cohort of students with repeated preference lists is a plausible high-multiplicity regime.
The strongest objection is that this paper’s one-to-one structure scales poorly as a population model. Each of its \(n\) agents ranks the same \(n\) individually distinct objects, and each object has capacity one. Growing the population therefore also grows the object set and changes the rankings. To keep a fixed type space, the proposed school model groups objects into categories and gives each category a proportional capacity. That is a coherent assignment problem, and school seats make it plausible. It also replaces the paper’s bijections over distinct objects with flows over interchangeable categories. The authors might recognize that variant, but it is a substantial model change.
That change especially weakens the claimed connection to Theorem 2. Its \(n-1\) threshold hinges on one exceptional agent–object pair: with two agents assigned unrevealed objects, the proof can complete their preferences to make a trade. In a population of total mass one, a single exceptional agent has mass \(1/n\), which vanishes. A positive-mass Pareto improvement is a sensible continuum definition, but it no longer captures that one-pair boundary. Requiring all mass to receive a revealed category gives a clean question; the theorem does not tell us whether that is the right condition or supply its characterization.
Theorem 6 has the same scaling problem in a sharper form. Its algorithm checks full revealed matchings and then tries each possible single unrevealed pair. A mass assignment can split a type across categories and leave positive mass on many unrevealed pairs. The proposed rank signature can be defined for that flow, but robust lexicographic optimality over all completions is a new fractional capacitated problem; the paper’s single-pair structure does not carry over.
Those points make the proposed mirrors weaker than the proponent suggests: neither theorem directly supports its corresponding continuous algorithmic question. They do not establish that the questions are worthless. The capped school model remains a recognizable way to ask for robust Pareto efficiency and rank-maximality in a large market, and the programme explicitly allows such capacity co-modifications. So the honest negative case falls short of the requested universal claim. Its strongest point is that these are mirrors of a substantial capacitated reformulation, rather than continuizations that preserve the paper’s distinctive one-to-one structure.
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.