| paper | Tradeoffs Between Information and Ordinal Approximation for Bipartite Matching |
| authors | Elliot Anshelevich, Wennan Zhu |
| venue | SAGT 2017 |
| filed under | coalition · matching |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Yes. The deterministic simultaneous-eating algorithm computes a rational coupling in time polynomial in \(m,\tau,L\) and guarantees welfare at least \(1/(\sqrt2+1)\) times the optimum for every compatible hidden utility matrix. · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given finite type sets \(\mathcal X\) and \(\mathcal Y\), rational mass distributions \(\mu^X\) and \(\mu^Y\), and an ordinal ranking of \(\mathcal Y\)-types for every \(\mathcal X\)-type, compute an ordinal-only randomized mass coupling \(\pi\) with marginals \(\mu^X\) and \(\mu^Y\) such that, for every hidden utility matrix \(w\) consistent with the rankings and satisfying \(w_{ij}\le w_{ij'}+w_{i'j}+w_{i'j'}\), \(\mathbb E[\sum_{i,j}w_{ij}\pi_{ij}]\ge \frac{1}{\sqrt{2}+1}\max_{\pi'}\sum_{i,j}w_{ij}\pi'_{ij}\).
A finite-type high-multiplicity matching model: type masses \(\mu^X_i\) and \(\mu^Y_j\) are coupled by variables \(\pi_{ij}\ge 0\) with the prescribed marginals; the omniscient benchmark maximizes \(\sum_{i,j}w_{ij}\pi_{ij}\), while the ordinal algorithm uses only rankings and masses.
The fluid RSD process is not canonically defined by a uniform random ordering of a continuum, and finite blow-up guarantees alone do not establish an efficiently computable aggregate process independent of the limiting construction.
fatal: False
The mirror covers Theorems 1 and 3, concerning full and partial one-sided ordinal information. It leaves the two-sided results in Theorems 4 and 5, total-order result in Theorem 6, restricted-weight result in Theorem 7, and the lower-bound examples untreated.
There is a credible continuous mirror here. My lead is a high-multiplicity version of the paper’s one-sided ordinal matching problem, with the paper’s partial-information theorem as a second anchor. The case is algorithmic rather than hardness-based: the paper contains no named NP-hardness or parameterized-complexity result to use honestly.
Take two large populations, \(X\) and \(Y\), each normalized to mass \(1\). A type in \(X\) is a complete applicant profile: it has the same ordinal preferences over \(Y\)-types and the same latent utility against every \(Y\)-type. A \(Y\)-type likewise represents interchangeable units with the same latent compatibility profile. Let their type distributions be \(\mu^X\) and \(\mu^Y\), over finite type sets \(\mathcal X\) and \(\mathcal Y\), with \(|\mathcal X|=\tau_X\), \(|\mathcal Y|=\tau_Y\), and \(\tau_X+\tau_Y\ll N\), where \(N\) is the number of applicants and units.
The hidden utility matrix \(w_{ij}\) is not revealed to the algorithm. It must satisfy the paper’s cross-metric condition \(w_{ij}\le w_{ij'}+w_{i'j}+w_{i'j'}\), and each \(X\)-type’s ordinal ranking must be consistent with its row of \(w\). A matching is represented by a mass-coupling \(\pi\), where \(\pi_{ij}\) is the mass of \(X\)-type \(i\) assigned to \(Y\)-type \(j\), with \(\sum_j\pi_{ij}=\mu^X_i\) and \(\sum_i\pi_{ij}=\mu^Y_j\). This is not giving an individual a fractional house: every finite realization gives each person one integral match; \(\pi\) records the aggregate fractions.
The natural benchmark is \(W^*_\infty(w)=\max_{\pi}\sum_{i,j}w_{ij}\pi_{ij}\), while an ordinal algorithm must choose \(\pi\) using only \((\mu^X,\mu^Y)\) and the revealed rankings. For rational masses, this is exactly the high-multiplicity version of the finite problem: replace each type by \(N\mu_i\) identical copies, and aggregate an integral matching. Conversely, rational mass couplings can be realized by sufficiently large blow-ups. Thus this is a population continuization, not merely a fractional-relaxation reformulation.
My lead problem is Continuous One-Sided Ordinal Matching. Its instance consists of finite type sets \(\mathcal X,\mathcal Y\), rational population distributions \(\mu^X,\mu^Y\), and a complete ordinal ranking of \(Y\)-types for every \(X\)-type. A solution is an ordinal-only randomized procedure producing a feasible mass-coupling \(\pi\), such that for every hidden utility matrix \(w\) compatible with the rankings and the cross-metric condition, it satisfies \(\mathbb E[\sum_{i,j}w_{ij}\pi_{ij}]\ge\frac{1}{\sqrt 2+1}W^*_\infty(w)\).
The anchor is Theorem 1, proved in this paper. It states that for a complete bipartite graph with \(|X|=|Y|=N\), Algorithm 1—random serial dictatorship, which repeatedly chooses an \(X\)-agent uniformly at random and matches it to its most-preferred remaining \(Y\)-agent—returns a perfect matching \(M\) satisfying \(\mathbb E[w(M)]\ge\frac{1}{\sqrt2+1}w(\operatorname{OPT}(G))\). The continuous algorithm is the fluid/high-multiplicity version of exactly that procedure: process infinitesimal \(X\)-mass in random serial order, assign each unit to its highest-ranked remaining \(Y\)-mass, and aggregate the resulting assignments.
I would expect this problem to be Class A. The residual state consists only of finitely many type masses, and the omniscient benchmark is a transportation LP. The remaining technical task is to represent the fluid RSD process efficiently, but nothing in the model suggests that the continuum introduces a new combinatorial obstruction.
The second anchor is Theorem 3, also proved in this paper. It states that when only the top \(\alpha N\) preferences of every \(X\)-agent are available, Algorithm 2 runs random serial dictatorship for \(\alpha N\) matches and then completes the matching uniformly at random; its expected welfare satisfies \(\mathbb E[w(M)]\ge\frac{1}{3-(2-\sqrt2)\alpha}w(\operatorname{OPT}(G))\).
Its continuous counterpart is Continuous Prefix-Ordinal Matching. The instance is as above, together with \(\alpha\in[0,1]\). For every \(X\)-type, the input reveals only the first \(\alpha\) units of \(Y\)-mass in its preference order; a boundary type may be split because its copies are interchangeable. The solution must process \(\alpha\) units of \(X\)-mass using only those prefixes, then complete the residual \(X\)- and \(Y\)-mass by the product coupling, equivalently by a uniformly random matching in a finite blow-up. The required guarantee is, for every compatible hidden \(w\), \(\mathbb E[W_w(\pi)]\ge\frac{1}{3-(2-\sqrt2)\alpha}W^*_\infty(w)\).
This is a particularly natural continuization because the paper’s information parameter already measures a fraction of the population. At \(\alpha=0\), the rule reduces to random matching and gives the factor \(3\); at \(\alpha=1\), it becomes the full-information-about-rankings setting of Theorem 1. I would again expect Class A, with the interesting open question being whether the paper’s tradeoff is tight in the finite-type continuum and whether the optimal welfare-information curve can be computed exactly.
The regime is plausible in a recurring housing or placement market: millions of applicants and units, but perhaps dozens of standardized applicant profiles and unit profiles. The authors would recognize the mirror because it retains their complete matching objective, hidden numerical utilities, metric restriction, ordinal information model, and randomized approximation criterion. Only the population representation changes from many named copies to type masses. It is not a weakened problem whose tractability comes from replacing matching by an arbitrary fractional outcome.
The weakest point is that Theorems 1 and 3 prove finite-\(N\) guarantees, not a polynomial-time fluid-limit theorem. A continuous RSD process cannot simply be described as a uniformly random permutation of an uncountable population; it needs a definition through finite blow-ups or an equivalent finite-type flow, plus a convergence and representation argument. That is a real obligation for the mirror. Still, the approximation inequalities hold uniformly for every blow-up size, and the space of normalized couplings is compact, so the guarantee should survive passage to the high-multiplicity limit.
The strongest negative case is that both anchors are high-multiplicity translations of finite approximation theorems, not genuinely new continuous computational problems. In the paper, the substantive object is an ordinal algorithm competing with an omniscient matching. Once agents are grouped into finitely many interchangeable \(X\)- and \(Y\)-types, the only surviving object is a finite transportation coupling. The random serial order, named agents, and individual matching decisions disappear into type masses.
For Theorem 1, this criticism is technically sharp but not decisive. If the agents retain distinct preference or utility profiles, then there is no useful multiplicity: the type space has essentially \(N\) types, and the proposed continuum gives no compression. If agents are instead standardized into finitely many types, then for rational masses one simply takes \(N\mu_i^X\) and \(N\mu_j^Y\) identical copies. The finite theorem applies to every such blow-up, and after dividing by \(N\) and taking a limit it immediately yields the continuous guarantee. The fluid RSD process is just the deterministic aggregate limit of finite RSD; its state has finitely many masses and can be simulated by a short greedy event process.
Thus the mirror does not reveal a new obstruction, separation problem, or complexity phenomenon. It restates a theorem uniformly valid on all finite blow-ups. One could ask for the optimal ordinal coupling or the exact information–welfare curve, but that is a new robust mechanism-design problem rather than the continuous counterpart of Theorem 1. Moreover, with type-homogeneous utilities, randomization matters only through its expected coupling, so the individual matching layer has already been eliminated.
The same objection applies even more strongly to Theorem 3. The paper already parameterizes information by \(\alpha N\). Replacing that count by \(\alpha\) units of \(Y\)-mass merely turns the prefix into a mass prefix; splitting a boundary type is the obvious high-multiplicity operation. For every rational \(\alpha\), the finite proof applies to a sufficiently large blow-up, and the completion by a uniform random matching converges to the corresponding product coupling. The bound therefore transfers mechanically:
\[
\mathbb{E}[W(M)]\ge
\frac{1}{3-(2-\sqrt{2})\alpha}W^*.
\]
There is no new continuum-specific computational content in the tradeoff; it is the same interpolation between RSD and random matching, with sums replaced by normalized sums.
One might object that the paper’s agents are points in a metric space, so repeated identical types are artificial. But that only defeats one application story. Standardized applicant and employer profiles, repeated housing categories, or large cohorts of interchangeable units are perfectly coherent high-multiplicity regimes, and the programme explicitly treats such regimes as admissible. Conversely, retaining the original individuality forfeits the proposed continuum. This gives a real modelling fork, but not a universal impossibility.
Nor is “the result is already known from the finite theorem” a valid objection under the programme’s rules. The continuous question can remain worthwhile even when its answer follows by a blow-up argument. Likewise, calling these results distortion bounds does not remove them: the paper gives named approximation algorithms and explicit guarantees, which are computational results in the programme’s sense.
So the best negative conclusion is limited: the proponent has shown a legitimate high-multiplicity mirror, but has not yet shown a particularly rich ChoCo research problem. The proposed versions mostly transfer existing guarantees rather than expose a new complexity landscape. That may justify ranking them below bribery, control, or Inv-Perm-Max. It does not support the requested universal claim that no worthwhile continuous mirror exists. Both anchors survive the stronger modelling 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.