| paper | d4-conf-wine-2021-0023 |
| 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: Yes. A randomized causal policy can be constructed and executed in polynomial time with \(F(\pi)\ge 0.726\,\mathrm{OPT}_{\mathrm{cl}}\), implying the requested \(0.725\) guarantee. · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 2.2
Given rational offline type masses \(\mu_i\) summing to \(1\), a compatibility relation with online types, and \(N\) KIID arrival rounds with known probabilities \(p_j=r_j/N\) summing to \(1\), each arrival carrying mass \(1/N\), can one compute a causal type-level policy whose minimum expected matched fraction \(\min_i \mathbb{E}[z_i]/\mu_i\) is at least \(0.725\) times the clairvoyant optimum for that same objective?
Represent identical offline agents by types with masses \(\mu_i\), and represent matched supply by type-level masses \(z_i\). Preserve the paper’s sequential KIID arrivals and unit-capacity matching semantics, while evaluating fairness as expected matched mass divided by type mass.
With \(N\) rounds and arrival mass \(1/N\), the proposal retains an \(N\)-granularity stochastic process; it remains to establish that a type-only policy and guarantee apply to arbitrary rational masses without relying on that finite expansion.
fatal: False
The mirror covers the IFM competitive guarantee only; it leaves the GFM and VOM guarantees, the Greedy and Ranking lower bounds, the relation theorem, and the experiments outside.
The strongest honest lead is HM-IFM-CR: high-multiplicity individual-fair online matching.
Take \(N\) offline agents, grouped into a finite set \(I\) of types. Type \(i\) has mass \(\mu_i=n_i/N\), with \(\sum_i\mu_i=1\); its members have identical compatibility with online types. There are \(N\) arrival rounds. In each round, an online agent of type \(j\in J\) arrives independently with probability \(p_j=r_j/N\), where the \(r_j\) are nonnegative integers summing to \(N\). Each arriving agent has mass \(1/N\), and must be matched immediately to one compatible, still-available offline agent or rejected. Here \(\tau=|I|+|J|\), and the intended regime has \(N\gg\tau\) and many offline agents per type. A plausible setting is a large rideshare platform: many drivers share the same full eligibility profile, while trips are grouped by origin, destination, and time window.
A type must capture everything the matching problem uses: compatibility, and any group membership or weight if those matter. An offline type’s mass is its share of the offline population. If \(z_i^\pi\) is the mass of type \(i\) matched by a causal policy \(\pi\), its individual-fairness value is \(F(\pi)=\min_i \mathbb{E}[z_i^\pi]/\mu_i\). Define the clairvoyant benchmark as the maximum of this same value over feasible matchings chosen with knowledge of the entire arrival sequence. HM-IFM-CR asks for the best universal competitive ratio \(\rho^*=\sup_{\mathcal A}\inf_{\mathcal I} F(\mathcal A(\mathcal I))/\mathrm{OPT}_{\mathrm{IFM}}(\mathcal I)\), and a type-compressed policy with a certified guarantee. A solution is a rule that, on each arrival, maps its type and the remaining type masses to a distribution over compatible offline types or rejection, plus a proof of its ratio.
The anchor is Theorem 2.2, proved in this paper: under the paper’s known KIID arrival model and unit offline capacities, the LP-based sampling algorithm with boosting, SAMP-B, has competitive ratio at least \(0.725\) for IFM against a clairvoyant optimum. This is an algorithmic competitive guarantee, not an NP-hardness or standard complexity-class result; the paper’s theorem and numbering appear in the [arXiv version](https://arxiv.org/abs/2109.08934). The type-mass analogue uses aggregate variables \(x_{ij}\) for matched mass and per-capita fairness constraints \(\sum_jx_{ij}\ge\lambda\mu_i\). A causal policy can implement boosted sampling by renormalizing the LP weights over currently available mass. The target for a prover is a preprocessing algorithm polynomial in \((\tau,L)\), with polynomial work per arrival, that returns such a policy and certifies the \(0.725\) guarantee. I expect this policy-construction question to be Class A: the benchmark has a compact type-level LP, and the paper’s subset constraints have a separation-oracle route. Establishing the bit complexity directly on binary-encoded masses, without expanding \(N\) agents, is part of the mirror.
This covers only Theorem 2.2 and IFM. I would leave the paper’s group-fairness and weighted-objective results, its Greedy and Ranking lower bounds, and its experiments outside this mirror. Further questions are whether \(\rho^*\) is sharp, how it varies with \(\tau\), and whether the group-fairness version admits an equally compact policy.
The weak point is the scaling limit: with many repeated types and independent arrivals, a deterministic fluid limit may erase most arrival uncertainty, letting a policy approach the clairvoyant benchmark. Then \(0.725\) remains a valid inherited bound but may say little about the limit’s true ratio. The proposed mirror therefore retains the KIID sequence of individual arrivals while representing the high-multiplicity population by masses; a purely deterministic fluid limit is a separate question.
The proponent has found the strongest mirror. A large rideshare platform can have many drivers with the same full compatibility profile and group membership, so type masses and per-capita fairness are sensible. I would not argue that online matching lacks a high-multiplicity regime.
The difficulty is what Theorem 2.2 contributes. Its claim is a competitive guarantee for SAMP-B, not a complexity result for computing an optimum. The benchmark is already a polynomially solvable LP with variables on the graph’s edges, and SAMP-B is an explicit sampling rule. After grouping identical drivers, its LP and choices can be expressed using type counts. A continuous version asking for a policy with the same \(0.725\) guarantee would therefore mainly re-establish a stochastic performance bound. Asking for the *best* possible guarantee or an optimal policy would be a new online-algorithm-design problem, rather than a computational mirror of this theorem.
The better mirror also runs into a scaling choice. Keep unit arrivals and unit driver capacities, and aggregate drivers’ availability still moves in increments of \(1/N\); the model retains the finite KIID process that produces the theorem’s guarantee. Remove those increments to make supply and demand genuine flows, and in a balanced regime with fixed support, independent arrivals concentrate around their known type rates. The resulting fluid planner can schedule against those rates in advance, so the clairvoyant advantage behind the competitive-ratio question disappears in the regular limit. Keeping only \(O(1)\) arrivals as supply grows avoids that concentration, but per-capita service tends to zero; a nondegenerate question then needs an additional scaling of the objective or a rare-event model.
That is the strongest case against spending ChoCo time on this anchor: the finite-granularity version keeps the paper’s theorem but offers little new continuous optimization, while the genuine fluid version removes the uncertainty the theorem measures. It is not a proof that no valuable follow-up exists. A compact, binary-encoded synthesis problem for high-multiplicity online policies could be worthwhile, but it would need its own computational formulation and result; this paper’s \(0.725\) guarantee does not supply that case.
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.