| paper | d4-journals-geb-2020-0123 |
| 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: \(\text{Polynomial-time solvable}\) · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 1
statement extracted from the paper’s text layer
Given finite firm and worker type sets \(B\) and \(S\), rational masses \(\mu_b,\mu_s\), type values and reservation wages \(v_b,c_s\), and an allowed-link relation \(E\subseteq B\times S\), compute a mass matching \(x_{bs}\geq 0\) satisfying \(\sum_{s:(b,s)\in E}x_{bs}\leq\mu_b\) and \(\sum_{b:(b,s)\in E}x_{bs}\leq\mu_s\), together with supporting wages for its matched mass, so that no linked firm and worker tranche can mutually benefit by rematching. For the returned matching, compute the minimum and maximum supporting wage for each active type pair.
A one-period market with finitely many firm and worker types carrying rational masses. Each type has shared relevant attributes, including value or reservation wage and access to linked types; \(x_{bs}\) records matched mass on an allowed pair. Matched mass receives wages supporting pairwise stability, residual mass remains unmatched, and the output includes the lower and upper supporting-wage bounds for the returned matching.
The mass LP need not reproduce the allocation selected by the paper’s queue, bid increments, and tie-breaking, and the proposed mirror does not define a fluid limit of that procedure.
fatal: False
The mirror covers the static stable-allocation computation and supporting-price bounds in Proposition 1. It leaves aside the characterization theorem, auction interpretation, simulations, and dynamic wage-growth results.
The anchor I would defend is Proposition 1, proved in Appendix B. It establishes four properties of the paper’s deferred acceptance algorithm: it terminates after finitely many rounds; it returns a pairwise stable allocation; Price Determination Program (I) returns the pointwise minimum price function supporting that allocation; and Program (II) returns the pointwise maximum. This is an algorithmic result, not a formal complexity classification: the paper gives no named theorem that says the problem is in P or is NP-hard, and Proposition 1 itself does not state a polynomial runtime bound.
My lead mirror is Stable Cohort Matching with Price Envelopes. Its setting is a one-period hiring market. Let \(B\) be a finite set of firm types and \(S\) a finite set of worker types, with rational masses \(\mu_t\) summing to one across both sides. A firm type \(b\) has productivity \(v_b\) and a specified set of worker types it can reach; a worker type \(s\) has reservation wage \(c_s\) and a specified set of firm types it can reach. Write \(E\subseteq B\times S\) for the allowed links. Each type includes the agent’s full relevant description, including their value and network access. Thus every firm of type \(b\) is linked to every worker in an adjacent type \(s\), and all agents within a type are otherwise indistinguishable.
The decision variable is matched mass \(x_{bs}\geq 0\) on allowed type pairs, with
\[ \sum_{s:(b,s)\in E}x_{bs}\leq\mu_b,\qquad \sum_{b:(b,s)\in E}x_{bs}\leq\mu_s. \]
The residual masses are unmatched. For each pair with \(x_{bs}>0\), the solution gives a wage \(p_{bs}\in[c_s,v_b]\). Each matched tranche’s virtual price is its wage; an unmatched firm’s is its productivity \(v_b\), and an unmatched worker’s is their reservation wage \(c_s\). The allocation is stable if, for every allowed firm–worker type pair, no positive-mass firm tranche and worker tranche have the firm’s virtual price above the worker’s. That is exactly the paper’s no-blocking condition expressed over type masses.
The problem asks for a stable mass allocation and supporting wages, plus the lower and upper supporting-wage bounds for each active type pair. Formally, for the returned \(x\), let \(\mathcal P(x)\) be the set of all wage schedules satisfying individual rationality and the no-blocking conditions. Return a feasible \(p\in\mathcal P(x)\) and, for each \(x_{bs}>0\), the bounds \(\min_{\tilde p\in\mathcal P(x)}\tilde p_{bs}\) and \(\max_{\tilde p\in\mathcal P(x)}\tilde p_{bs}\). The objective in the paper’s proposition is to construct these outputs, not to optimize a stated welfare criterion.
I expect this mirror to be tractable. A natural route is the capacitated assignment LP that maximizes total gains from trade, \(\sum_{(b,s)\in E}(v_b-c_s)x_{bs}\). Its dual conditions express the same stability inequalities; dual solutions give supporting wages, and LPs over the optimal dual solutions give the price bounds. This is a proposed route for the mirror, not a result claimed by the paper. The paper’s authors would, I think, recognize the underlying problem: it keeps their single-unit matching, exogenous network restrictions, pairwise stability, and supporting prices, while replacing counts of identical agents with masses. Fractions describe how much of a cohort is matched; every individual still gets either a job or no job.
A plausible regime is a large labor market with many vacancies and workers but relatively few exact profiles: standardized worker credentials, location, reservation wages, and application channels; and vacancy families with shared productivity and recruiting rules. For example, a large market might have millions of participants distributed over dozens or hundreds of such types. The paper itself treats labor matching as a buyer–seller market, so the interpretation is close to its own. This mirror covers its static buyer–seller matching and price computation. It does not claim to continuize the paper’s dynamic wage-growth results.
The weakest point is the gap between that regime and the paper’s simulations. The labor application draws firm productivities from a continuous distribution, while the simulations form individual networks randomly. In those settings, exact values and exact neighborhoods may make almost every agent a distinct type, leaving no useful support compression. The mirror therefore needs markets with genuinely repeated value and access profiles, not bins that quietly treat different agents as identical. I think that is a plausible instance regime for large hiring systems, but it is the hinge of the case.
Proposition 1 is the only strong anchor. It proves that a particular finite-network algorithm terminates, returns a stable matching, and computes supporting-price bounds. It gives no polynomial runtime in the input size, no hardness result, and no parameterized complexity. The paper therefore does not identify a complexity boundary for continuization to move. Its central contributions are the characterization of stability and simulations of market outcomes.
The proposed cohort model is coherent, though. With a finite set of firm and worker types and shared access rules, replacing counts by masses gives a capacitated assignment problem. Its dual can provide supporting wages, and price bounds for a fixed allocation can be computed by optimization. High multiplicity is plausible in large hiring markets with repeated credentials and recruiting rules. I can’t dismiss that as an invalid mirror: the authors could recognize it as their static matching and pricing problem.
The sharper objection is that this mass optimization does not directly mirror Proposition 1’s algorithm. The paper’s procedure selects a particular matching through a queue, bid increments, and tie-breaking, then computes price bounds for that matching. A surplus-maximizing flow may select a different stable allocation. A faithful continuum version would need to say what replaces the individual queue and how its order affects the aggregate outcome. The paper supplies no canonical limit for that procedure. Defining one would add a selection process to the mirror; using the LP instead changes the algorithmic output being studied.
That mismatch supports a case for lower priority, not for ruling out the mirror. The type-level LP remains a sensible computational question, and its tractability would fit the programme’s continuous-optimization motivation. The negative case is therefore weak at its central point: I can question whether it mirrors the proposition’s procedure, but I cannot honestly establish that no worthwhile continuous mirror exists. The cohort-matching anchor survives.
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.