| paper | d4-conf-aaai-2022-1550 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: \(R^*(\mu,b)=1\) for every admissible input. A deterministic causal policy family attains this limiting ratio. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\), and symmetric nonnegative pair utilities \(b_{tu}\), consider every even scale \(q\) for which \(q\mu_t\) is integral. People of each type arrive in uniformly random order, and a causal policy must pair everyone without rejection. What is the supremal limiting ratio of expected welfare to \(qF^*(\mu,b)\), where \(F^*\) is the type-level fluid matching optimum, and can a policy attain that ratio?
A high-multiplicity general matching market with type-pair utilities \(b_{tu}\), masses \(\mu_t\), and pair-mass variables \(x_{tu}\); the objective is to maximize \(\sum_{t\le u}b_{tu}x_{tu}\) subject to \(2x_{tt}+\sum_{u<t}x_{ut}+\sum_{u>t}x_{tu}=\mu_t\). The online policy acts on random-order finite refinements of this population and must pair each arrival with a waiting person or leave them waiting.
With fixed support, type proportions follow a deterministic path at fluid scale and all types can be discovered in a vanishing fraction of arrivals, so the limit may erase the secretary uncertainty behind Theorem 3; the proponent identifies this issue but does not resolve the fluid-policy bridge.
fatal: False
The mirror covers Theorem 3 for no-rejection general matching. It leaves the capacitated bipartite matching and roommate matching results unaddressed.
The lead is Type-Secretary Matching\(_\infty\), an asymptotic high-multiplicity version of the paper’s no-rejection general matching problem.
The anchor is Theorem 3, proved in this paper. It says that for GENERALMATCHING, ALG3 is \(3.34\)-competitive with high probability as \(n\to\infty\). The underlying problem has an even number \(n\) of vertices in a complete graph with arbitrary nonnegative edge weights. Vertices arrive in uniformly random order; when a vertex arrives, the algorithm may match it to a waiting vertex or leave it waiting, but it may not reject anyone, and it must produce a perfect matching. ALG3 runs in polynomial time. The paper has no numbered hardness result for this problem; the NP-hardness it mentions for offline roommate matching is cited in prose, so it is not an anchor here.
For the mirror, let \(T\) be a finite set of types, with rational masses \(\mu_t\geq 0\) summing to \(1\). A type \(t\) specifies a person’s complete utility profile: pairing someone of type \(t\) with someone of type \(u\) yields the same nonnegative utility \(b_{tu}=b_{ut}\) for every such pair. The support size \(\tau=|T|\) is much smaller than the population. A plausible regime is a large placement or peer-matching programme using a modest number of standardized compatibility profiles. Individual utilities may vary arbitrarily across type pairs; the high-multiplicity assumption is that people within a type are indistinguishable for the matching problem.
The continuous input is \((T,\mu,b)\). Its offline benchmark is the fluid matching LP
\[
F^*(\mu,b)=
\max \sum_{t\leq u} b_{tu}x_{tu}
\]
subject to
\[
2x_{tt}+\sum_{u<t}x_{ut}+\sum_{u>t}x_{tu}=\mu_t
\quad\text{for every }t,\qquad x_{tu}\geq 0.
\]
Here \(x_{tu}\) is the mass of pairs made from types \(t\) and \(u\). Each unit of mass still receives one integral partner; the variables record type-level averages.
The online question is: what is the best asymptotic competitive ratio for matching this population without rejections? More precisely, take scales \(q\) for which every \(q\mu_t\) is an integer and \(q\) is even. The scale-\(q\) refinement has \(q\mu_t\) people of type \(t\), arriving in uniformly random order. A causal policy sees arrivals and their utilities to people already seen, may pair the current person with someone waiting or leave them waiting, and must eventually pair everyone. It does not see the unseen arrival sequence. A solution is a uniform family of such policies whose decisions can be expressed using type-level waiting masses, and whose normalized welfare approaches a guarantee against \(F^*(\mu,b)\). The target is to determine
\[
\rho^*_\infty=
\sup_{\Pi}\inf_{(T,\mu,b):\,F^*>0}
\liminf_{q\to\infty}
\frac{\mathbb{E}[W_q(\Pi)]}{qF^*(\mu,b)},
\]
and to give a policy attaining that guarantee. For fixed finite support, the integer matching optimum on the scale-\(q\) refinements converges after normalization to the LP benchmark.
I expect a constant-factor policy to be tractable in this regime. Theorem 3 gives a concrete lead: applying ALG3 to each refinement supplies the paper’s \(3.34\) guarantee, and its choices can be described by counts of waiting types rather than named individuals. A stronger continuous result would derive a policy directly over type-level mass flows and compute its decisions in time polynomial in \(\tau\) and the binary input length \(L\), rather than listing the \(q\) people. The paper’s polynomial-in-\(n\) running time alone does not establish that bound. As \(\tau\) grows, the type-pair structure can still carry substantial combinatorics, so this is a tractable high-multiplicity regime, not a claim that all matching hardness disappears.
The authors should recognize this as their problem: it preserves general matching, random-order arrivals, the no-rejection constraint, pair utilities, and the same offline-welfare comparison. The scenario also makes a sensible case for many agents sharing complete utility profiles. The mirror covers Theorem 3 only.
My weakest point is the random-order limit. A bare continuum distribution does not itself have a uniformly random permutation: in the fluid limit, type arrival proportions become deterministic. The scale-\(q\) refinement semantics preserves the paper’s secretary uncertainty, but makes this an asymptotic high-multiplicity policy problem rather than a one-shot deterministic flow model. The useful follow-up is to establish the formal bridge between those refinements and a causal mass-flow policy, then ask whether the optimal asymptotic ratio exceeds \(1/3.34\).
The strongest objection is a degeneration in the proposed mirror’s online information structure. With fixed finite \(T\) and fixed positive masses \(\mu_t\), a uniformly random arrival order has, at every macroscopic point, type counts close to their deterministic proportions. The deviations are only \(O(\sqrt q)\), while the population is size \(q\). And the algorithm can learn every type-pair utility after each type has appeared once, which takes \(o(q)\) arrivals. So the random-order uncertainty that drives Theorem 3 survives only at a vanishing fraction of the population.
That remains true for a stronger version of the proposed mirror. In GENERALMATCHING, the algorithm may leave people waiting. It can hold the initial arrivals while it discovers the finite set of types and their pair utilities, then plan a type-level matching using the known remaining counts \(q\mu_t\). A plan specifies which type pairs to form; as arrivals occur, the policy can match each person to their planned partner when both are present. This is a legitimate causal policy, but it shows how little of the secretary problem remains at fluid scale: the continuum supplies a deterministic arrival profile, while the consequential uncertainty is confined to finite-population fluctuations.
The same issue reaches the paper’s other matching results. Finite classes of person profiles, room valuations, or compatibility patterns have deterministic aggregate arrival paths in the limit. Capacities and room assignments make the fluid constraints richer, but do not restore uncertainty about the macroscopic mix of future types. Letting types become rare as \(q\) grows could preserve late discoveries, but then the proposed fixed-support continuum and its type-level mass description no longer capture the regime. Keeping \(O(\sqrt q)\) fluctuations as the object of study would be a finite-size stochastic analysis, rather than a computational question about the continuous society.
I would not argue that high-multiplicity matching is an incoherent model; the existing high-multiplicity work supports it. Nor is the problem that only Theorem 3 has a mirror. The negative case is that, for this paper’s secretary-style anchors, the population limit removes the very information constraint their competitive analyses study. A formal asymptotic theorem could still be written, but I find the case that it merits ChoCo’s computational complexity programme weak: the proposed limit looks more like planning over type-level flows than a continuous version of secretary matching.
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.