| paper | d4-journals-jet-2015-0131 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(m,\tau,L\), independently of \(1/\epsilon\). A stable exact unequal-division allocation always exists. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 7
Given worker types \(A\), employer-seat types \(B\), rational masses \(\mu_t>0\) summing to one, and a compatibility graph \(H\), where every member of a type has the same compatible types, values \(w_{ab}\in(0,1]\), and bargaining shares \(r_{ab},r_{ba}>0\) with \(r_{ab}+r_{ba}=1\), find a stable \(\epsilon\)-UD allocation or certify that none exists. Represent matched mass on each compatible pair \((a,b)\) by a finite rational measure \(\pi_{ab}\) over earnings pairs \((x,y)\), with \(x+y=w_{ab}\), and require total incident matched mass at each type \(t\) to be at most \(\mu_t\); unmatched mass earns zero. Let \(\ell_t\) be the lowest earnings in the resulting earnings support and set \(\beta_t=\max_{u\in N(t)}(w_{tu}-\ell_u)^+\), or zero if \(t\) has no compatible types. Require \(\ell_a+\ell_b\ge w_{ab}\) for every compatible pair and, for \(\pi_{ab}\)-almost every matched earnings pair, \(\left|x-\beta_a-r_{ab}(w_{ab}-\beta_a-\beta_b)\right|\le\epsilon\).
A two-sided, unit-capacity clone market with rational type masses, shared compatibility and bargaining parameters within each type, mass matchings, and type-level earnings distributions. The type minima define outside options; the task is to compute a stable allocation satisfying the prescribed surplus split within \(\epsilon\).
The mirror covers Theorem 7's approximation result for unequal bargaining powers in unit-capacity networks. It leaves the paper's natural-dynamics results, existence results, and general-capacity results aside.
My lead is Fluid Unequal-Power Bargaining (F-UD): find a stable bargaining allocation for a large labor market described by masses of agent types. This paper offers a good computational anchor for that question, though it does not already solve its type-compressed version.
The anchor is Theorem 7, proved here in Section 4.2 and Appendix G.2. For a finite exchange network with unit-capacity agents, edge weights in \((0,1]\), and edge-specific bargaining shares \(r_{ij}\) and \(r_{ji}\) summing to one, it gives an algorithm polynomial in the input size and \(1/\epsilon\). If a UD solution exists—a stable outcome with the prescribed surplus division—the algorithm returns a stable \(\epsilon\)-UD solution, whose division error on every matched edge is at most \(\epsilon\). If no UD solution exists, it returns “unstable.” The paper calls this an FPTAS. I find no named hardness theorem in the paper; its closing conjecture about exact UD computation is not a proved hardness result.
Here is the continuous problem I would hand to a prover. Let \(A\) be worker types and \(B\) employer-seat types, with rational masses \(\mu_t>0\) summing to one. Each type is a complete description for the market: for example, region, occupation or skill, compatible roles, match values, and bargaining shares. A compatibility graph \(H\) specifies which type pairs can trade. Every worker and employer seat has capacity one; between compatible types \(a,b\), every individual pair can match, with value \(w_{ab}\in(0,1]\) and shares \(r_{ab},r_{ba}>0\), where \(r_{ab}+r_{ba}=1\).
A candidate solution gives, for each compatible pair \(a,b\), a finite rational measure \(\pi_{ab}\) over earnings pairs \((x,y)\). Its total mass is the mass matched between those types; its marginals count the mass of each type receiving each earnings level. Total matched mass incident to any type \(t\) must be at most \(\mu_t\). The leftover mass of that type is unmatched and earns zero. Let \(\nu_t\) be the resulting earnings distribution for type \(t\), and let \(\ell_t\) be its lowest earnings in the support. Define the type’s best alternative as \(\beta_t=\max_{u\in N(t)}(w_{tu}-\ell_u)^+\), or zero if it has no compatible types.
Require stability, \(\ell_a+\ell_b\ge w_{ab}\) for every compatible pair, and valid deal splits, \(x+y=w_{ab}\) on every matched pair. Finally, for \(\pi_{ab}\)-almost every matched earnings pair, require \(\left|x-\beta_a-r_{ab}(w_{ab}-\beta_a-\beta_b)\right|\le\epsilon\). The last condition is the paper’s correct-division condition in type-mass form: each matched unit gets its prescribed share of surplus over its best alternatives. In the atomless limit, excluding one particular counterpart does not change the available pool of a positive-mass type. The task is to output such an allocation, or report that no stable fluid allocation exists. There is no separate welfare objective: the computational task is to find the equilibrium allocation and division.
The regime is a large hiring market with many graduates and vacancy seats, but relatively few combinations of location, specialization, requirements, and bargaining share. For instance, thousands of workers may share one type, and thousands of seats another, with compatibility and surplus determined by type. The population is continuous because the input gives fractions of those cohorts and the output may assign fractional mass to a type pair; each unit of matched mass still receives one job and one seat. This is a high-multiplicity version of the paper’s exchange network, not a claim that its real-valued messages make its population continuous. The paper itself names labor markets and hospital assignments, which makes this regime credible to its authors.
I expect F-UD to be tractable, but Theorem 7 does not establish that. Its algorithm runs on an explicitly listed graph; a market with many agents may have far more nodes and edges than types. The proposed result would need a type-level algorithm with runtime polynomial in \(\tau\), the input bit length \(L\), and \(1/\epsilon\), independent of the total agent count. The theorem’s stable-matching step and local rebalancing offer a concrete starting point for that compression. Further questions include whether finite markets with repeated types converge to these fluid solutions, and whether an efficient type-level rebalancing algorithm always exists.
The weakest point is the block-market assumption: agents of compatible types can all meet, while in an arbitrary exchange network neighborhoods are individual-specific. The continuum best alternative also ignores the removal of one particular partner, which is justified only in the positive-mass, atomless limit. That is a real model restriction, but it describes a plausible hiring regime rather than a tractability-driven simplification of bargaining itself. My case covers the unequal-bargaining approximation result, Theorem 7; it does not stretch to mirror the paper’s other dynamics or capacity results.
Theorem 7 is a genuine computational anchor: it gives a polynomial-time approximation algorithm for a named bargaining problem. The paper’s arbitrary exchange networks make a strong objection possible, though. The algorithm takes the individual network as input, and each agent’s alternatives depend on that agent’s actual neighbors. Type masses alone cannot preserve those alternatives when neighborhoods differ. Compressing such a market to \(\tau\) types would require types to encode neighborhood structure; for general networks, that could make \(\tau\) as large as the population. Theorem 7 therefore gives no type-level runtime bound.
That objection reaches the proposed model only if its “block market” is too coarse. It is not decisive for the stronger version: define types to include the full role, compatibility pattern, values, and bargaining shares; give every agent of one type access to the same counterpart types; and represent outcomes with type-by-earnings measures and compatible couplings. Then \(\ell_t\) correctly captures the best available counterpart in an atomless pool, and mass matching is a natural population version of the paper’s unit-capacity market. Large hiring and hospital markets make that regime credible, and the paper itself names those settings.
The formulation needs those block and coupling conditions stated precisely. Without them, its type-level outside options could erase network information that affects bargaining. Adding the conditions appears to repair the model, however, and the task remains distinct from continuizing outcomes alone: the input society is a distribution over agent types.
So the strongest negative case is narrow: Theorem 7 does not establish efficient compression for general exchange networks, and the proposed mirror covers a structured market regime. I cannot honestly turn that limitation into a case against every worthwhile mirror. No decisive objection applies to the exact clone-type labor-market version; the negative case is weak there.
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.