| paper | d4-journals-geb-2026-0062 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable; every input satisfying the stated assumptions yields a maximum-total-mass matching. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given finite rational worker masses \(\mu_{r,\pi}\) and job masses \(\nu_s\) on a common scale, where worker types have region \(r\) and a fixed ranking \(\pi\) of job regions, and jobs have region \(s\), compatibility holds exactly when \(r\neq s\). Let \(r_1\) be a region with the largest worker mass and assume \(\sum_{r\neq r_1}\mu_r\geq\sum_{s\neq r_1}\nu_s\), where \(\mu_r=\sum_\pi\mu_{r,\pi}\). Fix an order of worker types within the two worker tubes \(W_1,W_{-1}\); process each type’s mass in that order, assigning it to the earliest job tube \(J_{-1},J_1\) with compatible available mass and following \(\pi\) within that tube. Does this execution always produce a flow of maximum total mass among feasible matchings?
A finite-support bipartite type-mass market: worker types carry rational mass and region-specific job rankings, job types carry rational mass and region, and compatible flow \(x_{r,\pi,s}\) is allowed only when \(r\neq s\). The two-tube sequential rule allocates worker mass through \(W_1,W_{-1}\) against job mass in \(J_{-1},J_1\); only aggregate assignments are fractional.
The paper allows arbitrary individual worker orders and job rankings, while the proposed infinitesimal execution does not specify how those individual orders become a type-level process.
fatal: False
The mirror covers Theorem 3’s maximum-cardinality guarantee for regular markets with avoidance-only compatibility. It leaves aside the historical procedure comparisons, eligibility and high-level prioritization results, and the other mechanism-design results, including Proposition 5’s tube-count obstruction.
The strongest positive case is a type-mass version of the paper’s sequential matching rules. It has a plausible regime: a large hiring or placement cycle in which many candidates and posts share a small set of relevant attributes—such as home region, qualification, job category, and any preference that affects assignment. A type is the full bundle of those attributes; its mass is its fraction of the candidate or job population. A solution assigns mass \(x_{uv}\) between compatible worker and job types, with each type’s assigned mass bounded by its supply. Each unit still gets one job; only the aggregate assignment can be fractional.
My lead anchor is Theorem 3, proved here. It says that when compatibility is determined only by avoidance of one’s own region, and the market is regular—if \(r_1\) has the largest worker population, then \(|W_{-1}|\geq |J_{-1}|\)—the tube sequence that processes workers \(W_1\) before \(W_{-1}\), and jobs \(J_{-1}\) before \(J_1\), produces a matching minimizing unfilled jobs for every assignment plan.
Its continuous mirror is Avoidance-Only Two-Tube Mass Matching. An instance gives rational worker and job masses by region, with a match allowed exactly when the regions differ, and a regularity condition \(\mu_{-1}\geq\nu_{-1}\) for the largest worker region \(r_1\). A fixed assignment plan supplies the within-tube processing and job-choice orders. Process worker mass infinitesimally through the two worker tubes; each portion takes an available compatible job mass from the earliest job tube, following its order. The output is a flow \(x_{rs}\), with \(x_{rr}=0\), row sums at most \(\mu_r\), and column sums at most \(\nu_s\). The question is whether this execution always maximizes \(\sum_{r,s}x_{rs}\) over feasible mass flows. Theorem 3 makes tractability the expected answer: the maximum is a bipartite flow problem, and the proposed mirror asks whether this simple, transparent sequential rule attains it for every plan. This is the most convincing mirror because regions and avoidance already define the paper’s model, while mass is a natural description of large regional cohorts.
A second, distinct anchor is Proposition 5, proved here. It states that for every \(k\geq2\), there is a market such that every tube sequence with fewer than \(k\) job tubes admits an assignment plan whose matching does not minimize unfilled jobs. Thus no fixed number of job tubes suffices for all compatibility structures.
Its continuous question is Robust Tube Design for Mass Matching. Given finite supports of worker and job types with rational masses, a compatibility relation, and a bound \(q\), determine whether there is a type-anonymous ordered tube architecture with at most \(q\) job tubes that yields a maximum-mass matching for every allowed assignment plan. A solution is such an architecture, or a plan showing why none exists. The proposition’s witness transfers: give each of its \(2k-1\) worker types and \(2k-1\) job types mass \(1/(2k-1)\). The greedy execution still strands positive job mass, while the maximum feasible flow matches total mass \(1\). Replicating each type many times gives a high-multiplicity regime with the same type-level instance. For the universal fixed-\(q\) version, the expected answer is a transferred impossibility: the required number of tubes is unbounded as support grows. That is a structural lower bound, not a claim of NP-hardness or a runtime lower bound; the complexity of finding the minimum tube count for a given instance remains open.
The two anchors support complementary questions: a tractable guarantee under regional avoidance, and an unbounded architecture requirement under arbitrary compatibility. The second is the closer analogue to a hardness boundary, but neither result establishes a standard complexity classification. That is the case’s weak point: the paper’s theorems concern mechanism guarantees, not running time, and maximum bipartite mass matching is already a familiar flow problem. A ComSoC referee could reasonably view these mirrors as market-design and mechanism questions rather than a contribution to computational complexity. The positive case is therefore for a continuous-population algorithmic-mechanism mirror, not for claiming that the paper has already charted a complexity landscape.
The strongest objection is that the paper has no named computational result to mirror. Theorem 3 is a guarantee about what a particular lots-drawing procedure produces; Proposition 5 is a lower bound on how many tubes a procedure may need. Neither classifies the complexity of deciding or computing a solution. That leaves the continuization programme with a poor fit: the natural questions here are about mechanism guarantees and design, rather than the complexity of computational social choice problems.
There is a plausible population regime, so I would not argue that matching civil-service cohorts is inherently unsuited to mass. But Theorem 3’s quantifier over *every assignment plan* creates a problem for the proposed mass mirror. A faithful plan includes individual worker order and, for each worker, an order over jobs. Include those in the type and the support can grow with the number of individuals, losing the intended high-multiplicity regime. Collapse agents with the same region and degree instead, and one must specify how the original random, without-replacement draws and individual job orders become a continuum process. The proposed infinitesimal first-fit flow is one possible model, but it is not yet a faithful account of those draws.
Even granting that aggregate-flow model, its central comparison is whether the two-tube rule attains maximum mass matching. That benchmark is a standard maximum-flow computation; Theorem 3 supplies a structural guarantee for the special avoidance graph and regularity condition. This could be a clean mass-valued mechanism theorem, but it does not open an algorithmic complexity question of the kind ChoCo is meant to chart.
Proposition 5 is a stronger candidate for a computational reframe, but its result is also structural: for arbitrary compatibility graphs, no fixed number of job tubes suffices. Duplicating each role in its witness produces high multiplicity while preserving the obstruction. That is good evidence that the regime is sensible, but the lower bound itself concerns the support graph and the tube architecture. A problem to compute the minimum tube count for a given market would be a legitimate new mechanism-synthesis project. Its decision variables are ordered partitions of compatibility types; the masses do not appear to drive the difficulty. It would be hard to present that as a computational question created by continuizing the population.
So I would reject these anchors as evidence for a *ChoCo* mirror, while conceding that they could motivate continuous-mechanism work elsewhere. The negative case is weaker on the user’s universal burden: a large, type-concentrated hiring market is plausible, and a carefully defined mass-valued mechanism question may be worthwhile. What the paper does not provide is a strong reason to think that such a question would contribute to the programme’s computational agenda.
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.