| paper | d4-journals-jet-2016-0104 |
| 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: An explicit finite improvement sequence to a stable competitive equilibrium is constructible in time polynomial in $m,\tau,K,L$, allowing the unilateral dissolutions expressly permitted in the task. · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 1
statement extracted from the paper’s text layer
Given firm and worker type sets \(I,J\), rational type masses, integer pair surpluses and outside options, and a feasible initial matching represented by \(K\) state-cohort classes with integral payoffs, can an algorithm polynomial in \(|I|+|J|+K+L\) output a finite sequence of pair improvements ending in a stable competitive equilibrium? Here \(L\) is the input bit length; each move transfers equal rational mass between cohorts not currently paired with each other, gives the newly matched agents integral payoffs that weakly improve both and strictly improve one, and returns abandoned partners to their outside options.
Firm and worker types carry value and outside-option vectors, and rational masses represent their populations. The state is a mass matching refined by current payoffs; each decision moves mass between cohorts and specifies an integral surplus split. The output is a finite improving-trade path to stability, with each unit of mass retaining a whole match; the task has no optimization objective.
Proposition 1 proves termination without a complexity bound, and replicating rational masses may yield an explicitly represented path that is too large; a polynomial-size mass path is an additional open claim.
fatal: False
The mirror covers Proposition 1's path from an arbitrary initial state to equilibrium; it leaves Theorem 1's stochastic absorption guarantee and the algorithm's efficiency unmirrored.
The strict anchor test exposes a gap: this paper has no named result saying that a problem is in P, NP-hard, FPT, or similar. Its closest algorithmic result is Proposition 1, proved here: from any initial finite labor-market state, there is a finite sequence of pair improvements leading to a competitive equilibrium. Theorem 1, also proved here, says that a random decentralized rematching process reaches equilibrium almost surely in finite time if every pair improvement has probability bounded away from zero. These are constructive and convergence results, but neither is a computational-complexity result. So the paper has no anchor that qualifies under the stated rule.
The strongest nearby positive case is a population mirror of Proposition 1. In a plausible regime, many firms and workers participate in repeated hiring markets, but fall into relatively few profiles: firms share productivity and outside-option vectors, and workers share the corresponding value and outside-option vectors. Let \(I\) and \(J\) be the finite sets of firm and worker types, with rational masses \(a_i\) and \(b_j\). A type’s value vector describes its value for every type on the other side. The number of agents may be very large while \(|I|+|J|\) remains moderate. Each person still holds at most one job, and each job still has at most one worker; it is the amount of mass in each cohort that is continuous.
Call the proposed search problem Finite Mass-Trade Stabilization. Its input is those type masses, integer pair surpluses and outside options, and an initial matching state described by rational masses of matched and unmatched cohorts and their current payoffs. A move selects equal positive rational mass of firm and worker cohorts who are not currently matched to each other. They form a new match with a split of their pair surplus that weakly improves both selected cohorts’ payoffs and strictly improves at least one; their former partners become single and receive their outside options. The question is whether one can produce a finite sequence of such moves ending in a competitive equilibrium, where agents meet their outside options and no available firm–worker cohorts can block with a feasible surplus split. A solution is the sequence itself, encoded with rational masses and payoff splits.
This retains Proposition 1’s central object: a path made entirely of local bilateral trades from an arbitrary starting state to equilibrium. It does not merely ask for a stable matching, and fractional masses do not give any individual a fractional job or change the unit-demand assumption. This is a population continuization; the mass-valued matching is the co-modification needed to represent the aggregate.
I would tentatively expect the search problem to be Class A, if the paper’s alternating-path and augmentation construction can be batched by type. Finite-type assignment structure gives a plausible route to finding an equilibrium, but that alone does not find the required sequence of improving trades. The complexity question is whether such a sequence can be constructed in time polynomial in the number of types, initial cohort classes, and input bit length, rather than in the potentially enormous population represented by the rational masses.
Theorem 1 makes the scenario more compelling, but I would not treat it as a second anchor. Its direct continuum translation is an almost-sure absorption question for a process with continuously many possible mass states and trade sizes—an analytic convergence question, not the computational question this mirror should pose. Whether a suitable finite menu of type-level trades preserves finite-time absorption is a further question.
The weakest point is substantial: Proposition 1 relies on a finite-agent state space and integer payoffs. A mass market can have infinitely many aggregate states, and its trades can be split into arbitrarily small rational amounts. Replicating rational masses as a large finite market supports existence of a finite path, but says nothing about finding a compact path efficiently. Thus this is a plausible mirror of the paper’s constructive result, not evidence that its complexity is already known.
The strongest objection is that this paper has no named computational-complexity result to mirror. Proposition 1 proves that a finite sequence of pair improvements exists; Theorem 1 proves almost-sure convergence under a condition on trade probabilities. Neither gives a running-time bound for a defined computational problem. The paper’s “algorithm” is a constructive route through a finite market, not a complexity analysis. Under ChoCo’s stated test, that is a decisive mismatch.
The proposed employer and worker cohorts are plausible: complete types can include productivity and outside-option vectors, and rational masses can represent many unit-demand agents without giving anyone a fractional job. So I would not reject the mirror on grounds of identity, integrality, or a supposedly implausible high-multiplicity market. The problem is what the mirror asks. If it asks whether a finite mass-trade path exists, it translates an existence and convergence result, not a computational one. If it asks how efficiently to output such a path, it adds a new search problem—with choices about encoding trades and representing the output—that the paper does not study. Those choices may support a worthwhile project, but they do not supply the missing computational anchor.
A better stochastic mirror of Theorem 1 would ask about absorption in a continuum-state process. That is a question about the dynamics and their convergence, rather than the complexity of an algorithm for bribery, control, or another computational problem. Turning it into a finite type-level algorithmic task would again require adding a computational objective absent from the theorem.
So the negative case is strong against calling this paper a clear ChoCo mirror, but weak as a universal claim that no useful mirror could be devised. The cohort model is sensible, and one could formulate new algorithmic questions around it. The case against is that those questions would be new computational work inspired by this paper’s economics—not a continuization of a computational result the paper actually establishes.
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.