| paper | d4-conf-atal-2017-0012 |
| 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 witnessing pair with rational interval endpoints can be returned in time polynomial in \(m,\tau,L\) whenever equality fails. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite category set \(H\), rational per-capita capacities \(q_h\) summing to \(1\), and paired ranking types \(s=(t_s,t'_s)\) with rational masses \(\kappa_s\) summing to \(1\), consider two profiles on the same atomless unit-mass population and the same feasible allocations, where each person receives one category and category \(h\) is assigned to mass \(q_h\). Decide whether the majority edge weights agree between the profiles for every pair of feasible allocations \(f,g\), where each edge weight is the integral of the assigned individuals' pairwise ranking comparisons. If not, return a pair of allocations witnessing unequal edge weights.
Use an atomless unit-mass population partitioned into \(\tau\) paired types \(s=(t_s,t'_s)\) with rational masses \(\kappa_s\), over a finite category set \(H\) with rational per-capita supplies \(q_h\). Each person receives one category. For two allocations, \(z_{s,h,h'}\) records the mass of type \(s\) receiving \(h\) in the first and \(h'\) in the second; the edge-weight difference is linear in these joint masses, and feasible joint masses form a finite polytope.
The mirror covers Theorem 1's majority-graph equivalence question. It leaves aside the paper's uniqueness results, experimental findings, and incompatibility results.
I see one defensible, narrow mirror. The paper has no named NP-hardness result, and its theorems about weak envy-freeness and weak strategyproofness are impossibility results, not complexity classifications. The strongest computational anchor is Theorem 1, together with the paper’s stated polynomial-time consequence. It says that two assignment problems on the same agents and houses induce identical weighted majority graphs if and only if their decompositions are rotation equivalent: each decomposition divides the houses into ordered blocks, every agent ranks each block above the later blocks, and the rankings within corresponding blocks agree up to a cyclic shift. The paper says this equivalence can be checked in polynomial time. The theorem is stated here; its proof is omitted for space and referred to the authors’ workshop version [14].
A plausible high-multiplicity setting is a large school or public-service assignment with many interchangeable places in each of a fixed set of categories. A student’s type is their complete ranking over those categories. To compare two preference profiles, the society is divided into cohorts whose members share a pair of rankings: one under each profile being compared. There may be millions of students but only \(\tau\) such paired types. Each category has a rational per-capita capacity \(q_h\), with \(\sum_h q_h=1\); in a finite instance of size \(N\), that corresponds to \(Nq_h\) places. Every individual still receives one category. A cohort can split across categories because it contains divisible population mass, not because an individual’s assignment is fractional.
The continuous question I would hand to a prover is Continuous Majority-Graph Equivalence. Its input is a finite category set \(H\), rational capacities \(q\), and a list of paired ranking types \(s=(t,t')\) with rational masses \(\kappa_s\) summing to one. Use the same atomless population and the same feasible assignment set in both profiles: a feasible assignment is a measurable map \(f:[0,1]\to H\) such that the mass assigned to \(h\) is \(q_h\). For rankings \(t\), let \(\phi_t(h,h')\) be \(1\) if \(t\) prefers \(h\) to \(h'\), \(-1\) if it prefers \(h'\), and \(0\) if they are the same category. The edge weight for assignments \(f,g\) in the first profile is \(w(f,g)=\int_0^1\phi_{t(u)}(f(u),g(u))\,du\); in the second profile use \(t'(u)\). The question is whether these edge weights agree for every pair of feasible assignments \(f,g\). A “no” answer should include a witness pair.
This problem has a finite linear description. Let \(z_{s,h,h'}\) be the mass of paired-type cohort \(s\) assigned \(h\) in \(f\) and \(h'\) in \(g\). These nonnegative variables must sum to \(\kappa_s\) within each cohort, and to \(q_h\) and \(q_{h'}\) across the first and second assignment, respectively. The difference between the two graphs’ edge weights is then
\[
\Delta(z)=\sum_{s=(t,t')}\sum_{h,h'\in H}z_{s,h,h'}\bigl(\phi_t(h,h')-\phi_{t'}(h,h')\bigr).
\]
Because cohorts are atomless, every feasible \(z\) can be realized by assignments \(f,g\). Thus the graphs agree exactly when the minimum and maximum of \(\Delta\) over this polytope are both zero. Two linear programs decide the question and return a witness if they disagree, in time polynomial in \(|H|\), \(\tau\), and the input bit length. I expect this mirror to be tractable. It also preserves a consequence emphasized in the paper: identical majority graphs give identical sets of popular assignments.
The authors could recognize the question: it asks when two assignment environments give the same majority comparisons, the subject of Theorem 1, and the paper specifically notes that assignment quotas can be accommodated. The scope is deliberately limited to that graph-equivalence result. It does not claim to mirror the paper’s uniqueness findings or its incompatibility results, and it does not turn its popular-random-assignment computation into a population-continuity result.
The weakest point is that the mirror replaces \(n\) individually named houses and the graph on \(n!\) bijections with a fixed set of categories and quota-feasible assignments of a continuum. That is a real model extension, not a direct limit theorem; the paper’s rotation-equivalence characterization does not itself establish the continuous result above. The mirror is strongest as a plausible new computational question motivated by Theorem 1, not as a claim that this paper already contains a continuous-population analysis.
The only anchor is Theorem 1 and its polynomial time check for whether two assignment problems induce the same majority graph. It is a genuine computational anchor: the paper gives a structural characterization of a property that can be decided efficiently.
The strongest mirror is close to the proponent’s version. Take many interchangeable students, a fixed set of school categories, and per capita capacities for those categories. Give each cohort a pair of rankings, one for each profile being compared. For any two feasible allocations, their joint assignments reduce to masses \(z_{s,h,h'}\): how much of cohort \(s\) receives category \(h\) in the first allocation and \(h'\) in the second. The edge weight difference is linear in \(z\), and the feasible masses form a finite polytope. Testing whether all edge weights agree is therefore an LP question. This is a coherent high multiplicity model, and the paper itself notes that quotas can be accommodated. It is hard to argue that the authors would fail to recognize the majority comparison as their subject.
The case against rests on how much of Theorem 1 this mirror leaves behind. Its rotation equivalence concerns permutations of individually named houses: every house appears exactly once in every assignment. Under the continuous model, houses become categories with mass capacities, and allocations become measurable maps, identified up to changes on zero mass. The LP tests equality of two linear functionals over feasible joint flows; it does not continue the paper’s rotation equivalence characterization. If the mirror keeps houses individually distinct, a growing population requires a growing supply of distinct houses, which removes the fixed finite category regime that makes the high multiplicity model useful.
That leaves a worthwhile objection about the mirror’s closeness to this result, rather than a decisive objection to asking the question. The capacity model is a deliberate extension, but it is natural for school or service assignment, and it retains a clear computational problem. Its LP may be immediate, yet the programme explicitly accepts tractable mirrors. I cannot honestly defeat this anchor on the supplied grounds: the strongest continuous version survives, so the universal negative case is weak.
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.