| paper | Popular and Dominant Matchings with Uncertain and Multimodal Preferences |
| authors | Gergely Csáji |
| venue | IJCAI 2024 |
| filed under | coalition · matching |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 10
statement extracted from the paper’s text layer
Given finite applicant types \(T\), houses \(B\), rational masses \(\mu_t\) with \(\sum_{t\in T}\mu_t=1\), rational capacities \(\kappa_b\), common acceptability edges, and \(\ell\) strict preference profiles \(\succ_t^i\), does there exist a measurable assignment, including a last-resort house, with type-to-house masses \(x_{t,b}\) such that every type mass is assigned, house capacities are respected, and the assignment is popular against every competing assignment in every layer, using the mass-weighted vote margin \(\Delta_i(M,N)\)?
An atomless population partitioned into type classes of masses \(\mu_t\), with decision variables \(x_{t,b}\ge0\) representing assigned mass; popularity is characterized by the intersection of each layer's first and pseudo-second edges plus the saturated-admirer constraints \(a_i(b)\ge\kappa_b\), yielding a rational capacitated-flow feasibility problem.
The mirror covers the one-sided \(\text{HA-POPULAR-MULTILAYER}\) result in Theorem 10, supported by Theorems 7 and 8; it leaves the uncertainty variant, the two-sided popularity results, and the dominant-matching results unmirrored.
This paper does admit a credible continuous mirror, but the strongest case is deliberately narrow: the one-sided capacitated-house-allocation part, not the two-sided results.
My lead anchor is Theorem 10, proved in this paper. It states that \( \text{HA-POPULAR-MULTILAYER} \) and \( \text{HA-POPULAR-UNCERTAIN} \) are solvable in polynomial time. I would mirror only the multilayer part directly.
The natural regime is a large allocation market with many applicants but relatively few applicant types: for example, mass allocation of students to course sections, residents to housing categories, or applicants to capacity-constrained public services. An applicant type records every feature relevant to the problem: eligibility, acceptable houses, and rankings in each preference layer. There may be millions of applicants but only \( \tau \) distinct types. Houses are resource categories with capacities that scale with population. Thus a house of capacity \(q_b\) in an \(N\)-applicant instance becomes capacity \( \kappa_b=q_b/N \), rather than remaining a fixed indivisible object.
The multiple layers can represent different legitimate preference profiles: for example, two policy criteria, two forecast scenarios, or two modes in which applicants rank the same allocation options. The requirement is still the paper’s requirement: one matching must be popular in every layer.
I would state the continuous problem as follows.
Continuous HA-Popular-Multilayer. An instance consists of a finite applicant-type set \(T\), a finite set of houses \(B\), rational type masses \( \mu_t\ge 0 \) with \( \sum_{t\in T}\mu_t=1 \), rational house capacities \( \kappa_b\ge0 \), a common acceptability graph \(E\subseteq T\times B\), and \( \ell \) strict preference profiles \( \succ_t^1,\ldots,\succ_t^\ell \). A last-resort house can be added, exactly as in the paper, so that every applicant can be assigned.
The population is an atomless set partitioned into type classes of masses \( \mu_t \). A matching assigns every individual to one acceptable house, with house \(b\) receiving mass at most \( \kappa_b \). For two matchings \(M\) and \(N\), define the layer-\(i\) vote margin by
\( \Delta_i(M,N)=\int \bigl(\mathbf{1}[M(\omega)\succ_\omega^i N(\omega)]-\mathbf{1}[N(\omega)\succ_\omega^i M(\omega)]\bigr)\,d\omega \).
The question is whether there exists a matching \(M\) such that \( \Delta_i(M,N)\ge0 \) for every alternative matching \(N\) and every layer \(i\). A solution is the matching itself, represented computationally by the mass-flow variables \(x_{t,b}\), where \(x_{t,b}\) is the mass of type \(t\) assigned to house \(b\).
This is not merely “replace counts by weights.” The predicate remains universal popularity against every competing matching, and the action remains an indivisible assignment for each individual. Only the aggregate representation is continuous.
The paper’s Theorem 8 supplies the exact finite certificate needed to solve this problem. For layer \(i\), let \(f_i(t)\) be the first house of type \(t\), and let \(a_i(b)=\sum_{t:f_i(t)=b}\mu_t\) be the mass of admirers of \(b\). Define the pseudo-second house \(s_i(t)\) exactly as in the paper, replacing admirer counts and integer capacities by \(a_i(b)\) and \( \kappa_b \): if the first house is not over-demanded, it is also the pseudo-second house; otherwise choose the most preferred house whose admirer mass is below capacity. Let \(E_i\) contain the edges \((t,f_i(t))\) and \((t,s_i(t))\).
A mass flow \(x\) is a solution precisely when
\( \sum_b x_{t,b}=\mu_t \) for every type \(t\),
\( \sum_t x_{t,b}\le\kappa_b \) for every house \(b\),
\(x_{t,b}=0\) whenever \((t,b)\notin\bigcap_i E_i\),
and, for every layer \(i\) and house \(b\) with \(a_i(b)\ge\kappa_b\), no non-admirer mass is assigned to \(b\), namely \( \sum_{t:f_i(t)\ne b}x_{t,b}=0 \).
These are flow constraints after deleting prohibited edges. Hence feasibility, and an actual witnessing mass assignment, can be found in polynomial time in \( \tau \), \( |B| \), \( \ell \), and the encoding length of the rational data. This is the continuous analogue I would hand to a prover.
The high-multiplicity correspondence is unusually clean here. If every \( \mu_t \) and \( \kappa_b \) has denominator \(N\), replace mass \( \mu_t \) by \(N\mu_t\) applicant clones and capacity \( \kappa_b \) by \(N\kappa_b\). The admirer thresholds, pseudo-second houses, admissible edges, and flow constraints become exactly those of the finite instance. Conversely, any finite clone assignment aggregates to a feasible mass flow. Because the one-sided popularity characterization in Theorem 7 depends only on first choices, pseudo-second choices, admirer sets, and capacities, no information relevant to popularity is lost by grouping identical applicants. The continuous problem is therefore a genuine high-multiplicity relaxation, not a fractional allocation problem in which one person receives fractions of several houses.
The authors should recognize this as their problem. It preserves the one-sided HA model, the multilayer input, the common matching requirement, and the original head-to-head definition of popularity. It does not replace popularity by maximum matching or by layerwise feasibility. The only change is that a large population of indistinguishable applicants is represented by rational masses and that capacities are normalized per capita.
I expect this mirror to fall in Class A. The original theorem already identifies the structural reason: popular matchings are restricted to a sparse first/pseudo-second graph, after which ordinary matching machinery solves the problem. In the continuous version, that structure becomes even more natural: the result is a finite rational flow problem over type-house pairs.
This anchor covers Theorem 10’s \( \text{HA-POPULAR-MULTILAYER} \) result, proved here, with Theorem 8 as its structural support and Theorem 7 as the cited characterization from Manlove and Sng. It does not claim to mirror Theorem 5 or Theorem 6, the two-sided NP-completeness results, nor the dominant-matching results in Theorem 4.
The obvious further questions are whether the same construction works for the paper’s uncertainty model, where possible rankings may vary independently within a type; whether \(k\)-robust popularity admits a comparable mass characterization; and whether a two-sided continuous model can retain enough partner identity to make popularity and dominance meaningful. Those are not automatic extensions. In particular, two-sided preferences rank named partners, so simply replacing agents by marginal type masses may erase identity information that the original problem uses.
That is also the weakest point of the positive case: it covers only the one-sided subproblem, and its success depends on the special structural theorem for capacitated house allocation. A referee could reasonably say that the continuous mirror is therefore not a mirror of the paper’s central two-sided hardness results. I would concede that. But it does not undermine the narrower claim: Theorem 10 gives a precise, author-recognizable, rational-clone-faithful continuous population problem, with a genuine polynomial-time mass algorithm and no vacuous atomless-agent effect. One emphatic mirror of a named result is enough for this paper to qualify.
I cannot honestly defeat this anchor. The strongest negative attack is that the proposed model is merely a weighted restatement of Theorem 10: for rational \(\mu_t\) and \(\kappa_b\), scale by a common denominator and clone type \(t\) \(N\mu_t\) times. Popularity margins, admirer thresholds, pseudo-second houses, and capacities then become exactly those of the finite instance, with margins multiplied by \(N\).
But under ChoCo’s rules, that is evidence for the mirror, not against it. High multiplicity is precisely the intended regime, and the type-level flow can be exponentially more compact than the clone instance when \(N\) is binary-encoded. The fact that every flow can be implemented by partitioning an atomless type class does not fractionalize individual assignments; each individual still receives one house.
The other possible objections also fail. Large populations of applicants with repeated preference vectors and capacities scaling with population are plausible in housing, public-service allocation, and course-section assignment. Applicant identity is irrelevant in this one-sided model once the complete preference vector across layers is included in the type. The popularity predicate does not vanish in the limit: vote margins become mass differences, and the admirer-capacity thresholds remain meaningful. Nor must the layers themselves be continuous; only the population is being continuized.
This is not an existing continuous computational treatment. The paper’s matching algorithm and related high-multiplicity machinery are supporting prior art, not a novelty collision. At most, the mirror is narrower than the paper’s two-sided results and algorithmically modest. That does not defeat it: one named polynomial result is enough, and this one has an exact clone dictionary, a sensible population regime, and a genuine compressed flow formulation.
So the universal negative case is weak here. Theorem 10’s one-sided multilayer result survives as a credible Class A continuous mirror.
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.