d4-conf-atal-2009-0013

The mirror I would defend is Mass-STV-LMR Manipulation. A plausible regime is a large, centralized resident placement market represented as a one-to-one market between residents and individual program slots. Many residents and slots could share exact role and preference profiles—for example, standardized profiles by specialty and location—so the population size \(N\) is much larger than the number \(\tau\) of distinct types. This is a particular regime, not a claim that every matching market has high multiplicity.

Let there be \(q\) resident types and \(q\) slot types, with rational masses \(\mu_i\) and \(\nu_j\), each side totaling mass \(1\). A type specifies the agent’s complete ranking of the opposite-side types. A mass matching is a matrix \(x\geq 0\) with row sums \(\mu_i\) and column sums \(\nu_j\). It is stable if no pair of types has positive mass on both sides who would prefer one another to their assigned type: for every \(i,j\), at least one of
\[ \sum_{j':\,j\succ_i j'}x_{ij'} \quad\text{and}\quad \sum_{i':\,i\succ_j i'}x_{i'j} \]
is zero. The male- and female-proposing mass deferred-acceptance procedures give the two extreme stable mass matchings.

The selector follows the paper’s STV-based lexicographical minimal regret idea. Run weighted STV on resident types using slot-type ballots weighted by \(\nu_j\), and conversely to order slot types; fix the quota and deterministic tie-breaking convention as part of the mechanism. For each type, measure regret by its average partner rank, for example
\[ \bar r_i(x)=\frac{1}{\mu_i}\sum_j x_{ij}\operatorname{rank}_i(j). \]
Form the male and female regret vectors in their respective STV orders, take the lexicographically larger vector as the matching’s overall regret, and select the lower-regret one of the two extreme stable matchings. A designated cohort of rational mass \(\eta>0\) may report a different ranking. The decision question is whether some report makes the cohort’s mean rank under its true preferences strictly better. A witness is the alternative ranking; its objective is the cohort’s average gain.

My anchor is Theorem 4, proved in this paper. It says that deciding whether an agent can manipulate the STV-based lexicographical minimal regret stable-marriage procedure is NP-complete. That procedure orders men and women using STV on the other side’s preferences, then chooses between the male- and female-optimal stable matchings by lexicographically minimizing the larger dissatisfaction vector. The proof is given here, adapting the cited STV manipulation construction through a reduction from 3-COVER; it also establishes membership in NP. The result concerns manipulation of the combined stable-marriage procedure, not merely STV in isolation. The theorem’s proof assumes an STV quota of at least half the electorate and fixes tie-breaking.

This is the strongest anchor because the paper presents this combined procedure as its more natural way to make a stable-marriage procedure both gender neutral and hard to manipulate. The proposed mirror preserves the central question: can false preference reporting improve one’s outcome under a procedure that selects a stable matching using population preferences? Making types rank counterpart *types*, weighting STV ballots by mass, and allowing fractional aggregate assignments are co-modifications needed to make the population continuous. Continuity here is of the population; the fractional matching records aggregate assignments.

I would predict Class B, hardness transfers, as a research hypothesis: the paper’s 3-COVER construction places substantial combinatorics in the candidate and preference-type structure, not just in the number of repeated voters. That suggests that large populations with repeated profiles may retain hard strategic choices. But Theorem 4 does not prove this prediction. The continuous question still needs an embedding or a new reduction, and fractional matching could change which deviations succeed.

The serious weakness is that the anchor’s manipulator is one named person, while the mirror’s manipulator is a positive-mass cohort. Also, the mirror scores a type by its average rank when its mass can split among partners; this can change the paper’s individual lexicographic score. If the authors would not accept weighted STV and type-average regret as their procedure’s analogue, this formulation would miss their problem. The theorem covers only manipulation under the STV-based selector—not Theorem 1’s restricted-profile manipulation result, Theorem 2’s artificial procedure, or the gender-neutrality preprocessing theorem.

The next questions are whether the reduction survives weighted ballots and fractional mass assignments; whether manipulation is tractable when \(\tau\) is small; and whether a discrete-to-continuous correspondence preserves the selector’s decisions. Those would locate the boundary between hardness that survives because it lives in the type agenda and hardness that depends on individual agents.