Bounding the Incentive Ratio of the Probabilistic Serial Rule

The paper has no numbered result satisfying the required computational-anchor criterion. The proposed positive-mass cohort model is a coherent high-multiplicity extension, but it changes unilateral manipulation into coordinated bloc manipulation; a measure-zero unilateral agent cannot affect depletion. The paper therefore fails bit (a), regardless of whether the extension is worth studying.

The objection that survived

A positive-mass cohort must coordinate on the manipulation, whereas the paper studies one unilateral agent; the atomless unilateral version has no depletion influence and incentive ratio \(1\).

What the mirror covers

The proposed mirror targets the incentive-ratio analysis and the Section 4.2 lower-bound construction, while leaving fairness, efficiency, equilibrium, and related-work complexity results uncovered.

Open questions for a prover

The case FOR (proponent)

The strongest honest case is a narrow yes, led by the paper’s main quantitative result rather than by a complexity classification.

The anchor is Theorem 1, proved in this paper: “The incentive ratio of Probabilistic Serial is at most \(2-\frac{1}{2n-1}\).” Section 4.2 gives the matching lower-bound construction, although it is not stated as a separately numbered theorem. The paper has no numbered \(P\), NP-hardness, W[1]-hardness, or FPT result; the NP-hard best-response statement in the related-work section is attributed to Aziz et al. [5], so I do not count it as an anchor from this paper.

A precise mirror would be Cohort-PS-BestResponse\(_\infty\). Let \(O\) be a finite set of resource types. A population consists of finitely many complete agent types \(T\), where a type \(t\) specifies a true strict ranking \(\succ_t\), an additive valuation \(v_t\), and any other parameter used by the mechanism. The population is given by rational masses \(\mu_t\), with \(\sum_t\mu_t=1\). Resources have rational per-capita capacities \(b_o\), \(o\in O\). Thus \(b_o\) represents a mass of parallel copies of resource \(o\), rather than making the outcome space newly continuous.

One type \(a\) is marked as the potential manipulator. A mass \(\alpha\leq\mu_a\) of type-\(a\) agents may jointly submit a different strict ranking \(\rho\), while the remaining population follows a specified reported profile \(\rho_{-a}\). Mass-PS runs exactly the paper’s eating process: type \(t\) consumes its highest-ranked available resource at aggregate rate \(\mu_t\), and the marked cohort consumes at rate \(\alpha\) according to \(\rho\). If \(x_{a,o}(\rho)\) is the amount of resource \(o\) allocated to the marked cohort, its per-agent utility is

\[ U_a(\rho)=\frac{1}{\alpha}\sum_{o\in O}v_a(o)x_{a,o}(\rho). \]

The problem is: given \((O,T,\mu,b,a,\alpha,\rho_{-a})\), find a report \(\rho^\star\) maximizing \(U_a(\rho)\), and output the exact incentive ratio

\[ R_a^\star= \frac{U_a(\rho^\star)} {U_a(\succ_a)}, \]

assuming \(U_a(\succ_a)>0\). Equivalently, its decision version asks whether \(R_a^\star\ge q\) for a rational threshold \(q\).

This is recognizably the authors’ problem: the mechanism is still PS, reports are still ordinal rankings, utilities are still evaluated using the true additive valuation, and the strategic objective is still the incentive ratio. The only population change is that agents with identical complete types are represented by mass. The marked cohort can be interpreted as a repeated class of applicants represented by a common bargaining unit or reporting channel. A more literal unilateral version is obtained by setting \(\alpha=1/N\), where one agent has mass \(1/N\).

The high-multiplicity bridge is exact. If \(\mu_t=n_t/N\), \(\alpha=1/N\), and \(b_o=q_o/N\), multiplying all masses and capacities by \(N\) gives \(n_t\) agents and \(q_o\) unit-capacity copies of resource \(o\). Thus rational clone expansion recovers an ordinary finite PS instance. Conversely, a large recurring assignment market—say, university-course seats, housing lotteries, or public-service slots—can plausibly have millions of applicants but only a moderate number of complete preference/value types. Resource capacities must scale with population: \(q_o=\Theta(N)\) gives fixed per-capita supply, while retaining one isolated copy of each resource as \(N\) grows would be a degenerate regime.

Theorem 1 then supplies the continuous programme with a meaningful boundary. On the \(\alpha=1/N\) clone slice, every finite approximation satisfies

\[ R_a^\star\leq 2-\frac{1}{2N-1}, \]

so the tagged-agent continuum limit has the natural universal candidate bound \(R_a^\star\leq 2\). The lower-bound construction in Section 4.2 explains why \(2\) is the right target: repeat every role and every resource \(k\) times, and let the entire marked role type submit the common manipulation. The number of agents is then \(k n\), while the number of types is only about \(n\); taking \(k\gg n\) gives genuine high multiplicity, and the compressed dynamics reproduce the paper’s ratio \(2-\frac{1}{2n-1}\), which approaches \(2\) as \(n\) grows.

I would expect unrestricted Cohort-PS-BestResponse\(_\infty\) to be Class B rather than automatically tractable. The combinatorics live in the manipulator’s ordering of resources and in the sequence of depletion events, not merely in named-agent identities. A singleton-type restriction recovers finite PS best response, and the paper itself cites NP-hardness for general additive valuations. By contrast, fixed \(m\) or fixed \(\tau\) versions are plausible Class-A candidates: the mass process is piecewise linear, rational event times can be simulated, and the paper’s Lemma 1—“Lemma 1 of Wang et al. [27],” cited rather than proved here—suggests that dichotomous valuations may suffice for worst-case analysis.

The scope is deliberately limited to strategic manipulation and incentive-ratio bounds. It does not claim to mirror the paper’s fairness, Pareto-efficiency, equilibrium, or ex-post lottery discussions.

The weakest point is substantial: a literal atomless individual has no aggregate influence, so unilateral manipulation can become a tagged best-response problem rather than the paper’s finite pivotal-agent problem. To retain the paper’s lower-bound mechanism one must allow a positive-mass cohort to coordinate, which is an extension from unilateral deviation to bloc deviation. Also, Theorem 1’s correction term depends on finite \(n\), so the continuum result \(2\) is a proposed limiting question, not a theorem already established by the paper. Under a strict requirement that the anchor itself be a numbered complexity classification, this paper has no qualifying anchor. Under the broader interpretation that a sharp computational incentive bound counts, however, Cohort-PS-BestResponse\(_\infty\) is a credible, author-recognizable continuous population mirror.

The case AGAINST (opponent, writing after the proponent)

The negative case begins with the programme’s own threshold: this paper has no qualifying computational anchor. Its only numbered main result, Theorem 1, is an extremal incentive bound, not a complexity classification, algorithm, or approximation theorem. The NP-hardness statement in the related-work section belongs to Aziz et al. [5], not to this paper. Thus Cohort-PS-BestResponse\(_\infty\) is not a continuization of a computational result proved here; it is a new problem extrapolated from the paper’s motivation.

Even granting Theorem 1 as an anchor, the proposed continuum exposes a fundamental identity problem. In an atomless population, one individual has zero mass and cannot affect resource depletion. Once the aggregate PS trajectory is fixed, a representative agent faces an exogenous set of available items at every time. Reporting the true ranking is then pointwise optimal, because it always selects the available item of highest true value. Hence

\[ U_a(\rho^\star)=U_a(\succ_a) \]

and the incentive ratio is \(1\). The paper’s nontrivial gain comes precisely from the manipulator’s own consumption changing depletion times and therefore other agents’ future choices. That feedback disappears for a measure-zero individual.

The proponent’s repair—giving the manipulator a positive mass \(\alpha\)—does not preserve the paper’s problem. If \(\alpha=1/N\), the model retains a single-agent deviation but the influence vanishes in the continuum limit. If \(\alpha>0\), all agents in a cohort must coordinate on the same lie; this is bloc or coalition manipulation, whereas the paper studies unilateral manipulation by one agent. The lower-bound replication in Section 4.2 survives only because the entire repeated manipulator cohort deviates together. Calling that cohort a “type” does not turn it into one individual; high multiplicity identifies interchangeable agents but does not authorize replacing a unilateral deviation by a coordinated mass deviation.

One can of course study that new cohort problem. With rational masses and capacities, however, it is simply a weighted PS process that can be clone-expanded into a finite PS instance. The resulting question may be worthwhile in its own right, but the paper supplies neither its objective nor its complexity classification, and Theorem 1 does not establish a continuous theorem about it. The limit \(2\) is merely the limit of the finite formula along a specially chosen sequence of coordinated-clone instances.

The remaining negative case is therefore not airtight: a new paper on coalition manipulation in high-multiplicity PS could plausibly be useful. But it would be a new strategic model, not a continuous population mirror of this paper’s named result. Under the programme’s stricter computational standard, this paper should not be greened on the basis of Theorem 1.

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.