| paper | d4-conf-sagt-2014-0020 |
| 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 instance admits a finite rational better-response sequence from its initial allocation to stability, constructible in polynomial binary time. · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 6.
statement extracted from the paper’s text layer
Given a bipartite market with finite job and machine type sets \(J\) and \(M\), positive rational masses \(\mu_t\), common strict rankings within each type, per-capita quotas \(q_t\), pool quotas \(Q_t=\mu_tq_t\), pool-pair capacities \(K_{jm}\), and a feasible initial flow \(x^0\), compute a finite sequence of type-pool better-response reallocations ending at a stable allocation. Does every such instance admit such a sequence, and what running time suffices in the support size \(\tau=|J|+|M|\), the compatible-pair set \(E_T\), and the input bit length?
A market whose state-bearing actors are type pools: each type \(t\) has mass \(\mu_t\), quota \(Q_t=\mu_tq_t\), and common preferences; a feasible flow \(x\) assigns allocation across compatible type pairs subject to pool quotas and capacities \(K_{jm}\). A better response increases flow on a blocking pair and may reduce only worse-ranked flow, while preserving feasibility. Theorem 6 supplies a path algorithm with \(O(\tau^2|E_T|)\) arithmetic operations.
The result does not extend to a generic population whose same-preference members have different allocation states; it covers only markets where pools act at the type level.
fatal: False
Covers the deterministic better-response path-to-stability result for real-valued type-pool instances. It leaves aside the paper's random convergence results, its correlated-market bound, and its best-response results.
The strongest case is the paper’s deterministic better-response result in a large, type-structured labor market. Imagine a citywide or platform-wide market with many standardized job slots and worker cohorts. Workers of the same type share a strict ranking of job types, quota, and relevant capacity limits; job slots of the same type share the corresponding preferences and constraints. There may be hundreds of thousands of people but only \(\tau\) distinct types. That is a credible high-multiplicity regime: each type is a complete profile for the allocation problem, and a mass, rather than one named person, is the natural unit of change.
Here is a concrete mirror. Let \(T=J\sqcup M\) be finite job and machine type sets, with positive type masses \(\mu_t\) summing to \(1\). Each type has a common strict ranking of compatible types on the other side and a per-capita quota \(q_t\), so its total quota is \(Q_t=\mu_t q_t\). Each compatible pair \(jm\) has a total pool-to-pool capacity \(K_{jm}\); for instance, it can be derived from the two sides’ per-capita limits as \(K_{jm}=\min\{\mu_j\bar c^J_{jm},\mu_m\bar c^M_{jm}\}\). The instance also gives a feasible initial flow \(x^0\), where \(x_{jm}\) is the allocation volume between the two types, \(x_{jm}\le K_{jm}\), and the total flow incident to each type is at most \(Q_t\).
Define blocking and better-response steps by the paper’s rules on this type graph. A compatible pair blocks when it has unused capacity and, at each endpoint, either the type has unused quota or prefers that pair to its worst currently allocated pair. A better-response step increases flow on a blocking pair; any reductions are only on worse-ranked pairs, and feasibility is maintained. Thus the action is a mass-weighted reallocation among type pools, not a one-person change.
Call the problem Type-Continuous Better-Response Path to Stability: given the rational masses, type profiles, capacities, quotas, and feasible \(x^0\), output a finite sequence of such better-response allocations ending at a stable allocation. The expected answer is tractable. With \(\tau=|J|+|M|\) and \(E_T\) the compatible type pairs, the target is \(O(\tau^2|E_T|)\) exact arithmetic operations, with polynomial bit complexity for binary-rational input.
The anchor is Theorem 6 (proved here): for every real-valued stable-allocation instance and given feasible allocation, there is a sequence of better responses leading to a stable allocation in \(O(|V|^2|E|)\) time. On the mirror, the support types are the vertices, so the theorem’s bound becomes \(O(\tau^2|E_T|)\). This is the lead anchor because it retains the paper’s central question—whether myopic improvements can reach stability—and applies to real-valued quantities. The mirror covers this deterministic better-response result; it does not claim the same conclusion for random dynamics or best-response paths.
The soft spot is the aggregation itself. The theorem treats each vertex as an actor, while the mirror lets a whole type pool move together. Individual allocations within a cohort could differ, so a type-level stable allocation need not describe every possible unsynchronized individual state. The case is strongest when the market actually allocates by pools, or when the question is explicitly restricted to symmetric, type-level allocations and responses. That is a meaningful regime, though the formal bridge from a population of individuals to the pool graph should be proved rather than assumed.
Once that regime is fixed, the paper’s model is a close fit: it already allows real quotas, capacities, and allocation amounts, while the continuous mirror makes the population a distribution over types and scales pool resources with mass. The theorem may therefore provide the algorithm almost directly; that makes the mirror less of a new algorithmic challenge, but still a valid continuous-population formulation. Further questions are whether the type-pool path lifts to individual-level paths, whether arbitrary submasses of a type may respond without losing the bound, and how finite populations approximate the continuous path.
The only serious anchor is Theorem 6: it is a computational result, and the stated type-pool model appears to inherit it directly. Taking types as vertices and scaling their quotas and edge capacities gives a finite allocation instance, so the theorem yields the proposed \(O(\tau^2|E_T|)\) bound. That makes the case turn on whether this is a population mirror of the paper’s process.
The problem is that a type node in this construction acts as one player. It can move mass on behalf of the whole cohort in a single better-response step. In the paper, a vertex has its own current allocation and worst allocated edge; those determine whether it blocks and what it can refuse. Two agents with the same preferences and quota may have different current allocations, so they may have different response opportunities. A distribution over preference types does not record that difference. For example, if half a cohort is allocated to its first choice and half to its second, the pool’s aggregate flow does not say which agents can make which myopic changes.
One can add each agent’s allocation state to its type. But then the support may grow with the number of agents, and response steps can split mass among new states. The claimed dependence on the preference-type support \(\tau\) no longer follows. This is not a technical failure of Theorem 6; it is a mismatch between its state-bearing graph vertices and a population described only by preference types.
The best repair is to define an explicitly pooled market: a type is a collective actor, allocations are made between type pools, and each response moves pool mass. That is mathematically coherent, but it changes the paper’s uncoordinated process. A cohort of workers or jobs must act together, and the pool’s aggregate “worst” allocation stands in for every member’s individual state. Such a regime could be plausible where contracts are genuinely made through pools, but it is a special institution, not a general high-multiplicity version of the paper’s market.
So the negative case is about the semantics of the anchor, not the existence of a continuous question or the answer to it. I would not claim that no worthwhile mirror exists in any scenario: a genuinely pooled market could make one worthwhile. But the proponent’s theorem-level mirror does not establish that case without assuming the coordination that the paper’s dynamics set out to avoid.
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.