| paper | d4-conf-wine-2018-0013 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
parameterized→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete and \(\mathrm{FPT}\) parameterised by \(\tau\), with exact running time \(2^{|E|+\tau}L^{O(1)}\leq 2^{m(\tau-m)+\tau}L^{O(1)}=2^{O(\tau^2)}L^{O(1)}\). Hardness holds already for unit masses and \(b=0\). · discrete side: parameterized · adjudication: proved
full proof & adversarial review →
Theorem 13
statement extracted from the paper’s text layer
Given finite applicant types \(I\), position types \(J\), rational masses \(\mu_i,\nu_j\), and their weak preferences and acceptability, choose an assignment-mass matrix \(x\) with \(x_{ij}\ge 0\), \(x_{ij}=0\) for unacceptable pairs, and row and column sums bounded by \(\mu_i\) and \(\nu_j\); maximize \(\sum_{ij}x_{ij}\), then minimize \(B(x)=\sum_{(i,j)\text{ mutually acceptable}} A_{ij}(x)C_{ij}(x)\), where \(A_{ij}(x)=\mu_i-\sum_{j'}x_{ij'}+\sum_{j':\,j\succ_i j'}x_{ij'}\) and \(C_{ij}(x)=\nu_j-\sum_{i'}x_{i'j}+\sum_{i':\,i\succ_j i}x_{i'j}\).
The society consists of atomless mass in complete preference types on the two sides. The decision variable \(x_{ij}\) is the mass matched between types \(i\) and \(j\); \(A_{ij}\) and \(C_{ij}\) are the masses that would strictly prefer one another’s types, so their product measures blocking pairs.
The mirror covers Theorem 13 for typed SMTI; it leaves the paper’s other typed matching results and its exception-based hardness results aside.
The strongest mirror is the paper’s core model without exceptions. Its agents already come in complete preference types, with the number of types intended to be much smaller than the population. That makes high multiplicity an instance regime the authors explicitly study, not a new story imposed on their problem.
The anchor is Theorem 13, proved in this paper: TYPED MAX SIZE MIN BP SMTI is fixed parameter tractable when parameterized by the number \(k\) of types. The problem is to find, among all maximum-cardinality matchings in a typed Stable Marriage with Ties and Incomplete Lists instance, one with the fewest blocking pairs. It does not require the matching itself to be stable. The authors prove the result here by expressing the problem as an integer quadratic program.
A plausible regime is a large matching market for placements or jobs: many applicants and positions, but only a modest number of complete preference profiles. For example, applicants might share rankings based on training and location, while positions share rankings based on a few applicant attributes. A type must capture everything relevant to the matching problem, including acceptability and preferences. In that regime the number of agents \(N\) can be far larger than the support size \(\tau\), the number of types with positive mass.
Here is a continuous version of the anchored problem. Let \(I\) be applicant types and \(J\) position types, with rational masses \(\mu_i,\nu_j\ge 0\) satisfying \(\sum_i\mu_i+\sum_j\nu_j=1\). Each type has the paper’s weak preference ordering over types on the other side, including which types are acceptable. Let \(x_{ij}\ge 0\) be the mass of type \(i\) assigned to type \(j\), with \(x_{ij}=0\) unless they find each other acceptable, \(\sum_j x_{ij}\le\mu_i\), and \(\sum_i x_{ij}\le\nu_j\).
For mutually acceptable \(i,j\), define the mass of type-\(i\) agents who would strictly prefer \(j\) to their assignment by
\[
a_{ij}(x)=\mu_i-\sum_{j'}x_{ij'}+\sum_{j':\,j'\prec_i j}x_{ij'},
\]
where unmatched agents count as preferring every acceptable partner. Define \(b_{ij}(x)=\nu_j-\sum_{i'}x_{i'j}+\sum_{i':\,i'\prec_j i}x_{i'j}\) symmetrically. The blocker mass is \(B(x)=\sum_{(i,j)\text{ mutually acceptable}}a_{ij}(x)b_{ij}(x)\), using product measure over pairs of agents. The named continuous problem is Continuous Typed Max-Size Min-Blocker-Mass SMTI: maximize \(\sum_{ij}x_{ij}\), then among those maximizers minimize \(B(x)\). A solution is a mass allocation \(x\) attaining that lexicographic optimum. Each individual still receives one partner; \(x\) records how atomless type populations are divided among assignments.
This is a direct population mirror of Theorem 13’s underlying matching problem. In a finite typed instance with \(N\) agents, set \(\mu_i,\nu_j\) to type counts divided by \(N\), and \(x_{ij}\) to assignment counts divided by \(N\). Then matched cardinality is scaled by \(1/N\) and blocking-pair count by \(1/N^2\). Conversely, any rational feasible allocation can be realized by sufficiently replicating the corresponding typed cohorts. The paper’s existing high-multiplicity analysis supports the regime: it shows that small type support is already a sensible object for this problem. The mirror itself remains distinct, since the paper optimizes over finite integral matchings rather than defining the rational-mass problem.
I expect this question to be tractable parameterized by \(\tau\), though not necessarily by a practical algorithm polynomial in \(\tau\). Its allocation has \(O(\tau^2)\) variables, \(O(\tau)\) mass constraints, and a quadratic objective. Fixed-dimension exact polynomial optimization gives a route of the form \(f(\tau)\operatorname{poly}(L)\), where \(L\) includes the binary encoding of masses and preferences. The key follow-up is whether the objective’s structure yields a useful algorithm, perhaps polynomial in \(\tau,L\), instead of relying on general fixed-dimension methods. Another question is how quickly discrete optima on finite replications converge when the replication size does not exactly realize an optimal mass allocation.
This case covers Theorem 13’s typed SMTI result, not the paper as a whole. In particular, I would leave the exception-based hardness results outside this mirror: named exceptional targets can make complete preference types proliferate with the instance, so they do not automatically preserve a small-support regime.
The weak point is the blocker objective. Counting discrete blocking pairs has a clear meaning; in a continuum, individual pairs have zero mass, so the mirror uses the product-measure mass of blocking pairs. That is the natural normalization of the paper’s objective, but it does not make Theorem 13’s integer-quadratic proof carry over unchanged. The continuous objective is still a nonconvex quadratic optimization problem. That gap is a genuine computational question, and it is also why the mirror is more than simply renaming the paper’s finite typed instances.
The strongest objection is that the proposed mirror may add little computational leverage. Theorem 13 already reduces the finite problem to a quadratic objective over counts of type-pair assignments. Scaling those counts by population size gives the proposed mass variables; the continuous problem replaces the integer lattice with a rational polytope. The paper’s FPT result has already compressed the population to those aggregate variables, so the mirror may look more like a relaxation of the same count-space problem than a new use of continuous optimization.
That objection is weak under ChoCo’s criteria. A continuous mirror need not produce a faster algorithm to be worth asking, and the paper’s existing high-multiplicity result supports the regime rather than colliding with it. The theorem is a named computational result, and large populations with few complete preference types are precisely a plausible instance regime.
The proposed blocker objective also survives scrutiny. For each pair of types, the agents who strictly prefer one another’s types to their assignments form two cohorts; their product measure is exactly the limiting normalized count of blocking pairs. In the paper’s basic typed model, identities within a type do not affect preferences or blocking, so the mass allocation loses no information the objective needs. Rational allocations can be realized by replication. A more careful treatment of the two sides’ normalization would be routine.
I cannot honestly defeat this anchor. Its continuous version is well-posed, its population interpretation is credible, and its bridge to the finite theorem is unusually direct. The best negative case is that its algorithmic novelty may be modest because the paper already works with type-pair counts. That is an opportunity-cost argument, not a reason the mirror fails the programme’s test.
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.