| paper | Proportional Representation in Matching Markets: Selecting Multiple Matchings under Dichotomous Preferences |
| authors | — |
| venue | AAMAS 2022 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 4.3
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), approval sets \(A_t\subseteq T\), rational \(w_1>w_2>0\), and threshold \(\alpha\), decide whether there exist two type-level mass matchings \(x^1,x^2\) satisfying \(2x^j_{\{t,t\}}+\sum_{u\ne t}x^j_{\{t,u\}}\le\mu_t\), using only pairs approved by at least one endpoint, together with \(z_{t,S}\ge0\) for \(S\subseteq\{1,2\}\), \(\sum_S z_{t,S}=\mu_t\), and \(\sum_{S\ni j}z_{t,S}=p_{t,j}\), where \(p_{t,j}\) is the mass of type \(t\) approving its partner in round \(j\), such that \(\sum_{t\in T}\sum_{S\subseteq\{1,2\}}z_{t,S}\sum_{i=1}^{|S|}w_i\ge\alpha\).
A finite high-multiplicity population of types \(T\) with rational mass distribution \(\mu\) and type-level approval graph \(A\); decision variables are per-round fractional pairings \(x^1,x^2\) and approval-history masses \(z_{t,S}\), with the \(w\)-Thiele mass score as objective.
The mass-flow formulation may erase the paper's individual graph-role combinatorics and its Pareto-optimal candidate restriction, so its relationship to the exact candidate space needs a formal decomposition or rounding proof.
fatal: False
The mirror covers Theorem 4.3's winner-threshold problem for general matching elections with \(k=2\). It leaves the sequential-rule algorithms, bipartite and symmetric algorithms, axiomatic results, and complexity of checking proportionality axioms untreated.
My lead anchor is Theorem 4.3, proved by the authors (with the proof completed in the full version), not merely cited. It states that for every weight sequence \(w\) with \(w_1>w_2>0\), deciding whether a matching election has a size-\(k\) committee of \(w\)-Thiele score at least \(\alpha\) is NP-complete already for \(k=2\), even when every agent approves at most three other agents. The reduction is from the existence of two edge-disjoint perfect matchings in a 3-regular graph. This is exactly the kind of hardness result for which continuization has a meaningful prize: does the hardness survive when the electorate is a high-multiplicity population?
The natural regime is a large repeated matching programme: for example, a university, employer, or training platform runs two rounds of pair programming or collaborative work for a very large cohort. Participants have standardized skill, role, or compatibility profiles. All agents of type \(t\) approve exactly the same types \(A_t\), possibly asymmetrically: a type may approve working with type \(u\) even when \(u\) does not approve working with \(t\). There may be millions of agents but only \(\tau\) substantially distinct profiles, with \(\tau\ll n\). The type includes every feature relevant to approval and matching, so this is genuine high multiplicity rather than an arbitrary grouping of different people.
I would call the continuous problem HM-\(2\)-\(w\)-Thiele Mass-Matching Threshold. An instance consists of a finite type set \(T\), rational masses \(\mu_t\ge 0\) summing to \(1\), approval sets \(A_t\subseteq T\), rational \(w_1>w_2>0\), and a rational threshold \(\alpha\).
A round-\(j\) mass matching is a collection \(x^j_{\{t,u\}}\ge 0\), where \(x^j_{\{t,u\}}\) is the mass of pairs between types \(t\) and \(u\). It must satisfy
\[ 2x^j_{\{t,t\}}+\sum_{u\ne t}x^j_{\{t,u\}}\le \mu_t \]
for every \(t\). A pair type may be used only if at least one endpoint approves the other; otherwise it can simply be deleted without affecting anyone’s score. Let \(p_{t,j}\) be the mass of type \(t\) approving its partner in round \(j\):
\[ p_{t,j} = 2x^j_{\{t,t\}}\mathbf 1[t\in A_t] + \sum_{u\ne t:\,u\in A_t}x^j_{\{t,u\}}. \]
To preserve the paper’s \(w\)-Thiele semantics, the solution also records how agents’ approval experiences overlap across the two rounds. Let \(z_{t,S}\) be the mass of type \(t\) approving exactly the rounds in \(S\subseteq\{1,2\}\). Thus
\[ \sum_{S\subseteq\{1,2\}}z_{t,S}=\mu_t, \]
\[ z_{t,\{1\}}+z_{t,\{1,2\}}=p_{t,1}, \qquad z_{t,\{2\}}+z_{t,\{1,2\}}=p_{t,2}. \]
The question is whether there exist two mass matchings and such a history coupling with
\[ \sum_{t\in T}\sum_{S\subseteq\{1,2\}} z_{t,S}\sum_{i=1}^{|S|}w_i \ge \alpha. \]
A solution is the two-round type-level pairing schedule \((x^1,x^2)\), together with the feasible allocation of agents to approval histories \(z\). The paper’s minimality and Pareto-optimality restrictions can be retained in their mass form, but they do not change the optimum: useless pairs can be removed, and any mass matching that is Pareto-dominated can be replaced by one that weakly increases every type’s approved mass.
This is recognisably the authors’ problem. It still selects exactly two matchings, permits repetition, evaluates each agent by the number of selected matchings she approves, and maximizes the same \(w\)-Thiele objective. The variables \(x\) are not lotteries over outcomes. They are aggregate counts of physical pairings among many agents. If the masses and flows are rational, multiplying by a common denominator produces a finite population containing the required number of copies of every type, and the mass schedule can be implemented by actual matchings. Conversely, every finite typed schedule maps back to these variables.
The expected complexity is Class A. For \(k=2\), the displayed formulation is a linear program with \(O(\tau^2)\) pairing variables and \(4\tau\) history variables. Thus the NP-completeness of Theorem 4.3 is plausibly an indivisibility phenomenon: with one named agent per graph vertex, a vertex cannot serve different neighbours in the same round; with many identical copies of each profile, the corresponding type mass can be distributed among several approved partner types while each individual copy is still used only once. The discrete obstruction from two edge-disjoint perfect matchings is replaced by a capacity-flow problem.
This case covers only Theorem 4.3’s winner-determination problem, not the paper’s axiomatic results or every voting rule. It generates useful follow-up questions: how much finite-population rounding is needed to implement an optimal mass schedule; whether the same approach works for variable \(k\), where approval histories have \(2^k\) possibilities; and whether hardness returns when \(\tau\) approaches \(n\), or when agents have genuinely identity-specific approvals.
The weakest point is semantic rather than computational. The reduction behind Theorem 4.3 uses graph vertices with highly individual roles, so collapsing them into repeated types may destroy the very structure that makes the discrete instance hard. If the intended application is a one-off market of named individuals, this mirror is weak. But in the repeated-cohort settings explicitly contemplated by the paper—pair programming, teaching activities, or recurring shifts—the type-level population is natural, physically implementable, and still asks the paper’s original proportional multi-matching question.
The strongest negative case is that Theorem 4.3’s hardness is tied to indivisible, named vertices. Its reduction encodes the compatibility graph directly in the agents: a vertex cannot simultaneously serve several neighbours in one matching. The proposed \(x^j_{\{t,u\}}\) variables deliberately remove that obstruction by allowing many identical copies of type \(t\) to split across different partner types. The resulting problem is a fractional \(b\)-matching or transportation problem, not really the paper’s original candidate-selection problem.
The \(z\)-variables make this shift especially clear. They couple only whether a type is approved in each round, not which agents are paired across rounds. A more faithful formulation would use a joint measure over the two partners of every individual, with all marginal and matching constraints enforced. But that produces a dilemma: if agents of a type are genuinely indistinguishable, the joint measure projects back to essentially the same flow formulation; if partner identities must be retained to recover the reduction’s combinatorics, the types have become nearly individual agents and the high-multiplicity gain disappears.
One could also argue that the proposed application—large cohorts of students, programmers, or workers with standardized compatibility profiles—is not the paper’s central setting, where approvals may be highly individual. Yet this is not decisive. Repeated cohorts with role-based compatibility are perfectly coherent high-multiplicity instances, and multiplying rational masses by a common denominator really does implement the mass schedule with ordinary finite matchings. The fact that the continuous problem may collapse to a straightforward LP is likewise not a valid objection under ChoCo’s remit: a structural insight followed by continuous optimization is precisely a successful Class A outcome.
Thus the anchor cannot honestly be defeated. The mirror changes the source of difficulty, but that is exactly what a high-multiplicity relaxation is meant to test. There is no existing continuous-population computational treatment in the cited matching literature that blocks it; fractional matching and random matching concern outcome-space continuity instead. The best negative conclusion is therefore only that this mirror may be too routine to yield a rich theory, and that it no longer explains the original NP-hardness. That is a weak objection, not a case that no worthwhile continuous mirror exists.
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.