| paper | Partial strategyproofness: Relaxing strategyproofness for the random assignment problem |
| authors | Timo Mennle, Sven Seuken |
| venue | JET 2021 |
| filed under | fairalloc · markets |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{coNP}\)-complete under promise-preserving polynomial-time many-one reductions; hence \(\mathrm{NP}\)-hard under polynomial-time Turing reductions. · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 7
statement extracted from the paper’s text layer
Given a finite set \(T\) of complete assignment types, rational society masses \(\mu\in\mathbb{Q}^{T}\), per-capita capacities \(q\), and a specified anonymous continuum lift \(\mathcal F\), compute the largest \(r\in[0,1]\) such that for every positive-mass type \(t\), every alternative report \(\rho\), and every truthful-ranking prefix \(j_1\succ\cdots\succ j_K\), \(\sum_{k=1}^{K}r^k x_{\mu,t}(t)_{j_k}\ge\sum_{k=1}^{K}r^k x_{\mu,t}(\rho)_{j_k}\); equivalently, decide whether this degree is at least \(r_0\).
A high-multiplicity random-assignment model with type mass \(\mu_t\), per-capita object capacity \(q_j\), and assignment vectors \(x_{\mu,t}(\rho)\) generated by the continuum mechanism. The decision variable is the incentive degree \(r\), maximized subject to all discounted-dominance inequalities for infinitesimal agents.
For probabilistic serial, a measure-zero deviator cannot affect exhaustion times, so the continuum degree may collapse to \(1\); obtaining a nontrivial finite-degree limit or studying positive-mass manipulation would require a different model.
fatal: False
The mirror covers Proposition 7 and the computational degree of partial strategyproofness, with applications to probabilistic serial and Boston-type mechanisms. It leaves the paper’s axiomatic decompositions, impossibility arguments, and qualitative comparisons outside the mirror.
The strongest honest case is narrow. The paper contains no named NP-hardness, polynomial-time, FPT, or approximation theorem. Its best computational foothold is Proposition 7, proved in this paper, together with the finite computation described in unnumbered Algorithm 1 and Remark 3. Under a strict rule that only complexity classifications count as anchors, this paper has no qualifying anchor. Under the stated exception for a named formulation that the paper actually computes with, Proposition 7 is defensible.
Proposition 7 says the following. Given a setting \((N,M,q)\), a mechanism \(f\), and \(r\in[0,1]\), \(f\) is \(r\)-partially strategyproof if and only if it is \(r\)-discounted-dominance strategyproof. Thus, for every agent, every preference profile, every misreport, and every prefix \(j_1\succ\cdots\succ j_K\) of the agent’s true ranking,
\[ \sum_{k=1}^{K} r^k f_{i,j_k}(P_i,P_{-i}) \;\ge\; \sum_{k=1}^{K} r^k f_{i,j_k}(P_i',P_{-i}). \]
The paper proves that these finitely many inequalities are equivalent to truth-telling maximizing expected utility for every utility function in \(URBI(r)\). Algorithm 1 then computes the largest feasible \(r\), the mechanism’s degree of strategyproofness, by examining the resulting univariate polynomial inequalities. This is the lead anchor.
The corresponding continuous problem would be Continuous Partial-Strategyproofness Degree.
Let \(M=\{1,\ldots,m\}\) be schools or objects, with per-capita capacities \(q_1,\ldots,q_m\), where \(\sum_j q_j\ge 1\). Let \(T\) be the finite set of complete agent types. For ordinary random assignment, a type is a strict ranking \(t=(j_1\succ\cdots\succ j_m)\); if priorities depend on observable categories, those categories are included in the type. A society is a rational distribution \(\mu\in\mathbb{Q}^{T}\), where \(\mu_t\) is the fraction of the population of type \(t\).
The mechanism is a specified anonymous continuum lift \(\mathcal F\) of one of the paper’s assignment mechanisms, such as probabilistic serial. For a population distribution \(\mu\), let
\[ x_{\mu,t}(\rho)\in[0,1]^m \]
be the assignment lottery received by an infinitesimal agent in environment \(\mu\) when it reports ranking \(\rho\). The aggregate assignment must satisfy
\[ \sum_{t\in T}\mu_t x_{\mu,t}(t)_j\le q_j \]
for every object \(j\). In a probabilistic-serial lift, for example, \(\mathcal F\) is the simultaneous-eating process run on type masses; each individual unit of population still receives an integral object in each realization, while \(x_{\mu,t}\) records the type-level lottery.
The problem is: compute
\[ \rho_\infty(\mathcal F,\mu) = \max\left\{ r\in[0,1]: \sum_{k=1}^{K}r^k x_{\mu,t}(t)_{j_k} \ge \sum_{k=1}^{K}r^k x_{\mu,t}(\rho)_{j_k} \right. \]
\[ \left. \text{for every }t\in\operatorname{supp}(\mu),\ \rho\in T,\ K\in\{1,\ldots,m\} \right\}. \]
Equivalently, the decision version asks whether \(\rho_\infty(\mathcal F,\mu)\ge r_0\), and a negative certificate is a type \(t\), report \(\rho\), and prefix \(K\) violating one inequality. By Proposition 7, this is exactly the largest \(URBI(r)\) domain on which truth-telling is guaranteed for every positive-mass type.
The natural regime is a large school district, university system, or housing authority with millions of applicants but relatively few recurring preference and priority types: for example, students from the same neighborhoods, programmes, or demographic categories repeatedly ranking the same schools. The number of agents is enormous, while \(|T|=\tau\) is fixed or comparatively small. This is a genuine high-multiplicity representation: \(\mu_t=n_t/n\) is the compressed version of a finite profile, and capacities are represented per capita. It does not make schools divisible; it makes the population continuous.
The authors should recognise this as their problem. They explicitly study large markets, and Theorem 3(3) proves that if the degree of strategyproofness converges to \(1\) along growing fixed-object markets, then the mechanism is strategyproof in the large. Corollary 1 applies this to probabilistic serial. Those results are not computational anchors, but they provide a direct bridge to the proposed \(\mu\)-based limit.
For an explicitly represented type universe and a mechanism whose aggregate assignment is efficiently computable, I would expect this problem to be Class A. For probabilistic serial, the type-mass process has finitely many exhaustion events, and the degree test produces finitely many univariate polynomial inequalities of degree at most \(m\). Exact algebraic root isolation then gives \(\rho_\infty\). For mechanisms such as adaptive or classic Boston, the same question may expose the computational cost of evaluating the aggregate mechanism itself; that could lead to a genuine hardness boundary.
Useful follow-up questions include whether the continuous degree equals the limit of finite-market degrees, how \(\rho_\infty\) changes under perturbations of \(\mu\), and whether a positive-mass coalition’s coordinated misreport produces a harder mass-transfer problem than an infinitesimal individual deviation.
The weakest point is serious: in a literal atomless probabilistic-serial model, one individual has zero effect on aggregate exhaustion times, so the degree may collapse to \(1\), making the mirror mathematically easy and less novel. Moreover, the paper already proves qualitative strategyproofness in the large. Thus the case is strongest if the contribution is framed as the computational study of the exact degree as a function of a compressed population distribution—not as a claim that the paper itself contains a complexity result.
The proposed anchor does not survive, and on the programme’s strict gate this paper has no qualifying computational anchor at all. Proposition 7 is a reformulation of an incentive condition, not a complexity theorem. Algorithm 1 is a finite exhaustive procedure; Remark 3 establishes computability, not polynomial time, hardness, approximation, or parameterized complexity. There is therefore no named computational result whose continuous-population complexity could be charted.
Even granting Proposition 7 as an anchor, the proposed \(\rho_\infty(\mathcal F,\mu)\) does not preserve the paper’s strategic object. In the finite probabilistic-serial mechanism, one agent’s report changes the exhaustion times because that agent consumes \(1/n\) of an object. That strategic externality is precisely what can make misreporting profitable. In an atomless lift, a tagged agent has measure zero and cannot change any exhaustion time. It faces a fixed availability path determined by \(\mu\), and truthful reporting simply selects the best available object at every instant. Under the standard simultaneous-eating lift, the truthful lottery therefore stochastically dominates every misreport, so the continuum degree is \(1\). This is not merely a disappointing answer: the finite degree’s defining source of manipulation has disappeared.
Theorem 3(3) and Corollary 1 do not rescue the mirror. They already describe the relevant large-market limit, and they do so qualitatively: incentives vanish for probabilistic serial as markets grow. They neither provide a computational problem over \(\mu\) nor show that the exact finite degree converges to a nontrivial continuous quantity. The finite inequalities are especially unsuitable for high-multiplicity approximation: their violations can be of order \(1/n\), while the degree records only whether a violation is positive. Taking the limit loses exactly the sign information needed to compute the finite degree.
There are only two ways to avoid this degeneration. One can retain a tagged atom of mass \(1/n\), but then the model is a continuum society plus a finite individual, not a population continuum. Or one can let a positive mass of a type misreport together. The latter is a legitimate possible research question, but it is coalition manipulation, not partial strategyproofness. It changes \(\mu\), changes the environment faced by every member of the coalition, and requires new choices about coalition utility and coordinated reports. Proposition 7 and Algorithm 1 say nothing about it. Calling that problem a mirror would replace the paper’s central individual-dominant-strategy question with a different one.
There is also a type-space mismatch. The proposed types contain rankings, while the paper’s incentive conclusions depend on cardinal intensities. Two agents with the same ranking but different utilities can differ in whether a manipulation is profitable. Including utilities makes the relevant type space continuous; excluding them means the proposed population is not complete for the incentive problem. If one instead asks for the uniform URBI guarantee, the utility distribution disappears and \(\mu\) contributes only an aggregate environment, not a population of incentive types.
The same problem affects the Boston variants. Priority randomness can be represented in a continuum only by adding priority quantiles or categories to the type, but an individual priority type still has zero mass. A positive-mass deviation again becomes a new coalition problem. Proposition 4 is an axiomatic comparison of finite mechanisms, not a computational result waiting for high-multiplicity analysis.
The honest qualification is that a separately designed continuum theory of coordinated mass manipulation might be worthwhile. I cannot honestly prove that no such new problem could merit study. But it would not be a mirror of the paper’s named results. Against the proposed anchor—and against the claim that this paper supplies a worthwhile continuous-computational mirror—the negative case is strong: continuization either removes the strategic externality, reintroduces a finite tagged agent, or changes the problem into coalition manipulation.
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.