| paper | Position-Based Matching with Multi-Modal Preferences |
| authors | — |
| venue | AAMAS 2022 |
| filed under | coalition · matching |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 4.7
statement extracted from the paper’s text layer
Given finite applicant and position type sets \(A\) and \(B\), rational masses \(\mu\) and \(\nu\), finitely many layers with type-level positional scores \(p^\ell_{ab}\) and \(q^\ell_{ba}\), and a rational feasible transport plan \(\pi^0\), decide whether there exists another feasible plan \(\pi'\) with the same marginals such that \(E_\ell(\pi') \le E_\ell(\pi^0)\) for every layer and \(E_{\ell^\star}(\pi') < E_{\ell^\star}(\pi^0)\) for some layer, where \(E_\ell(\pi)=\sum_{a,b}\pi_{ab}(p^\ell_{ab}+q^\ell_{ba})\).
A high-multiplicity, nonatomic two-sided matching model with type masses \(\mu\) and \(\nu\), transport variables \(\pi_{ab}\), type-level block or positional scores, and linear Pareto-domination constraints over all layers.
Exact named-agent rankings and the reduction's identity-specific positional swaps disappear under finite type couplings; preserving them may require an internal rank or quantile coordinate whose size grows with the population.
fatal: False
The mirror covers Theorem 4.4 and the Egal part of Theorem 4.7, but not the other scoring rules, the LSum results, or the parameterized ( k,t ) results.
The strongest positive case is a genuine one, although I would present it as an author-recognisable extension mirror rather than a literal clone of every strict, named-agent instance. My lead anchor is Theorem 4.4, proved in this paper: “LMax-Egal is NP-hard,” by reduction from 3SAT.
Consider a large centralized placement market of applicants and positions: for example, national residency, university, or civil-service allocation. There may be \(N\) applicants and \(N\) positions, with \(N\) in the millions, but only \(\tau_A\) applicant types and \(\tau_B\) position types. A type contains the complete information used by the model: its preferences in every layer, and all attributes relevant to those preferences. Layers can represent salary, location, professional fit, working conditions, or other criteria. This is close to the paper’s own applicant–company motivation, but in a regime where many agents share the same categorical profile.
Let \(A\) and \(B\) be the finite sets of applicant and position types, with rational masses \(\mu_a\) and \(\nu_b\). A feasible decision is a transport plan \(\pi=(\pi_{ab})\), where \(\pi_{ab}\) is the mass of type \(a\) assigned to type \(b\), subject to \(\sum_b\pi_{ab}=\mu_a\) and \(\sum_a\pi_{ab}=\nu_b\). This does not give an individual a fractional position: an atomless type population can be partitioned into submasses, each assigned wholly to one position type.
For every layer \(\ell\), let \(p^\ell_{ab}\) be the position of type \(b\) in type \(a\)’s preference list, and \(q^\ell_{ba}\) the reciprocal position. Define the per-capita Egalitarian dissatisfaction of \(\pi\) in layer \(\ell\) as \(E_\ell(\pi)=\sum_{a\in A}\sum_{b\in B}\pi_{ab}(p^\ell_{ab}+q^\ell_{ba})\).
The precise continuous problem is:
\(\mathrm{LMax\text{-}Egal}_\infty\): given \(A,B,\mu,\nu\), all layer-position scores, and a rational bound \(D\), decide whether there exists a feasible transport plan \(\pi\) satisfying \(E_\ell(\pi)\le D\) for every layer \(\ell\).
This preserves the paper’s two-sided one-to-one matching, all preference layers, the positional dissatisfaction measure, and the minimax requirement across layers. Only the population representation changes. If all masses are rational, clearing denominators turns \(\mu,\nu,\pi\) into multiplicities of finitely many clone types and integer numbers of type-to-type matches; conversely, every finite matching induces such a transport plan. The original threshold \(d\) is replaced by the normalized threshold \(D=d/N\).
I expect \(\mathrm{LMax\text{-}Egal}_\infty\) to be in Class A. The variables are the \(|A||B|\) entries of \(\pi\); the marginal constraints and every layer constraint are linear. Thus feasibility is a rational linear program, and minimizing the worst-layer dissatisfaction is obtained by adding a variable \(z\) with \(E_\ell(\pi)\le z\). The NP-hardness of Theorem 4.4 therefore disappears in this population regime, because the integral assignment of individual clones has become an aggregate mass-matching problem. This does not claim that the paper’s 3SAT hardness was caused by population multiplicity; it identifies exactly the kind of hardness that the continuous mirror is designed to test.
The mirror generates useful follow-up questions: what is the integrality gap between the continuous optimum and a finite matching of clones; when can a continuous solution be rounded with bounded additive loss; and which side constraints—quotas, capacities, or minimum service levels—preserve the transportation-LP structure?
A second, genuinely distinct anchor is Theorem 4.7, also proved here: “LPareto-Egal-Determine and LPareto-Balc-Determine are co-NP-hard,” by reduction from 3-Partition. I would mirror only its Egal part. Define \(\mathrm{LPareto\text{-}Egal\text{-}Determine}_\infty\) as follows: the input is the same typed population and a rational feasible transport plan \(\pi^0\); the question is whether there exists another feasible plan \(\pi'\) such that \(E_\ell(\pi')\le E_\ell(\pi^0)\) for every layer and \(E_{\ell^\star}(\pi')<E_{\ell^\star}(\pi^0)\) for at least one layer.
This problem should also be in Class A. To test domination, solve an LP over \(\pi'\) with the transportation constraints and the inequalities \(E_\ell(\pi')\le E_\ell(\pi^0)\). Strict improvement in at least one layer is equivalent to \(\sum_\ell E_\ell(\pi')<\sum_\ell E_\ell(\pi^0)\), so exact rational LP optimization decides whether a dominating plan exists. Hence checking continuous Pareto-optimality is polynomial, despite the paper’s co-NP-hardness result for integral matchings. Further questions include computing or approximating the entire Pareto frontier, selecting a point by layer weights, and determining whether co-NP-hardness returns when the matching must be integral rather than nonatomic.
The weakest point is fidelity at the level of preference positions. The paper gives every named agent a strict ranking of every named opposite-side agent, whereas the continuous mirror ranks counterpart types or categories. That introduces type-level ties or block positions, and the transport plan removes the identity-sensitive integrality of the original matching. If a referee insists on strict named-agent rankings and integral pairings, this is not a direct mirror. I would therefore label it an extension mirror. The case remains credible because the paper’s substantive object—matching two populations under several positional preference layers—is unchanged, and its own motivating applications naturally contain repeated applicant and institution profiles. The construction also respects the programme’s high-multiplicity discipline: idiosyncratic preferences become separate types, while the proposed regime concerns markets where \(N\gg \tau_A+\tau_B\).
This case deliberately covers only Theorem 4.4 and Theorem 4.7. I would not stretch it to the \((k,t)\)-parameterized results, since selecting exactly \(k\) agents or \(t\) layers requires a separate positive-mass interpretation.
The strongest negative case is that the proponent’s transport plan changes the paper’s central object. In this paper, a preference list is a permutation of named opposite-side agents, and dissatisfaction is the position of a particular named partner. Identity is therefore not incidental metadata.
For Theorem 4.4, the 3SAT construction exploits exactly this. In a clause layer, the positions of particular agents such as \(q_1\) and \(\bar w_i\) are exchanged in the list of a particular \(u_i\). If \(b\) is instead a type containing many positions, there is no single coefficient \(p^\ell_{ab}\) representing the position of “type \(b\)” in \(a\)’s list. Replacing individual rankings by rankings of types creates block preferences or ties and removes the literal-specific swaps on which the reduction operates. Retaining strict positions requires adding an internal rank or quantile coordinate to each type; then the finite transport variable \(\pi_{ab}\) is insufficient, and the type space effectively grows with the number of individuals.
The applicant–company scenario does not automatically cure this problem. Applicants who rank named companies differently are different complete types under the programme’s own definition. If companies with the same coarse attributes are treated as indistinguishable, the result is a new category-assignment problem with block preferences, not the paper’s position-based matching problem. Thus the proposed \(\mathrm{LMax\text{-}Egal}_\infty\) is best described as an extension mirror, or a fractional relaxation, rather than a high-multiplicity version preserving the paper’s positional semantics.
The same objection is sharper for Theorem 4.7. Its 3-Partition reduction encodes the integers \(a_i\) in exact positions such as \(3mB+1-a_i\) in individual preference lists. Once those identities are replaced by type-to-type coefficients, the layer score becomes simply \(E_\ell(\pi)=c^\ell\cdot\pi\). Testing whether \(\pi^0\) is dominated is then ordinary multiobjective transportation feasibility:
\[ c^\ell\cdot\pi'\le c^\ell\cdot\pi^0 \]
for every layer, with strict improvement in at least one layer. The co-NP-hard matching problem has disappeared together with the individual positional information. Again, preserving the original rank positions requires a richer object than a finite type coupling.
That is the best case against both anchors: the clean LPs arise only after replacing named-agent rankings by type-level costs, so they do not demonstrate that the paper’s computational questions survive continuization.
However, this negative case is not strong enough to support the universal conclusion requested. A market in which applicants rank job categories, hospitals rank applicant categories, and dissatisfaction is defined by block rank or average quantile rank is a coherent, author-recognisable model. Its transport formulation is exactly the kind of Class A result the programme seeks. Theorem 4.7’s continuous Pareto test is especially difficult to dismiss: it is a natural aggregate analogue, not merely a malformed restatement.
So I would insist that these be labelled extension mirrors rather than literal continuizations, with the type-level ranking and rounding bridge made explicit. But I could not honestly argue 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.