| paper | d4-conf-wine-2010-0037 |
| 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 in \(\operatorname{poly}(m,\tau,L)\); every valid instance admits a maximum-weight matching with a stable allocation satisfying exact correct division. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 2.3
Given a finite type set \(T\), rational masses \(\mu_t\), and type-pair eligibility, profits, and split fractions, can one compute a maximum-weight feasible mass matching and a stable cohort allocation satisfying the paper’s \(\varepsilon\)-correct-division condition, or certify that no such outcome exists, in time polynomial in \(\tau\), input bit length \(L\), and \(1/\varepsilon\)?
An atomless population with mass \(\mu_t\) for each complete agent type \(t\). Use mass-flow variables \(x_{tu}\) for eligible type pairs, constrained by each type’s mass, and per-person earnings for each active pair cohort. Maximize \(\sum_{\{t,u\}\in F} w_{tu}x_{tu}\); require stability against type-pair deviations and the paper’s division condition on every active cohort.
The mirror covers computing an \(\varepsilon\)-UD outcome or certifying nonexistence for typed mass markets. It leaves aside the local belief-propagation result and the paper’s guarantees for arbitrary individual-level graph structure.
There is a credible mirror, and the strongest anchor is Theorem 2.3. Proved in this paper, it says that for a bargaining network with edge weights in \((0,1]\), there is an algorithm running in \(\operatorname{poly}(|V|,1/\varepsilon)\) time that finds an \(\varepsilon\)-UD solution if one exists, and reports “unstable” otherwise. Here an \(\varepsilon\)-UD solution is a stable outcome whose correct-division equation holds to additive error at most \(\varepsilon\) on every matched edge. This covers arbitrary split fractions \(r_{ij}\in(0,1)\). The paper has no named hardness result: its Section 4 example of exponentially slow rebalancing is not a complexity lower bound.
I would mirror this as Continuous Unequal-Division Bargaining in Typed Exchange Populations. A plausible regime is a large recurring exchange or collaboration market: many agents seek one-to-one partnerships, but fall into relatively few classes defined by all the attributes the model uses—eligible partner classes, pairwise profit, and bargaining split. For example, the total population might be very large while the number \(\tau\) of distinct classes is small. This is the high-multiplicity regime: agents within a class are interchangeable for the problem, while outcomes may still differ according to the class of their partner.
Formally, let \(T\) be a finite set of types with rational masses \(\mu_t>0\), \(\sum_t\mu_t=1\). Let \(F\) be the set of eligible pairs of distinct types. Each pair \(\{t,u\}\in F\) has profit \(w_{tu}\in(0,1]\) and split fractions \(r_{tu},r_{ut}\in(0,1)\), with \(r_{tu}+r_{ut}=1\). Each type is an atomless population of mass \(\mu_t\); any member of \(t\) may partner with any member of an eligible type \(u\), and each person may have at most one partner.
The action variables are the paired masses \(x_{tu}=x_{ut}\ge 0\) and the per-person earnings \(y_{tu},y_{ut}\) for the two sides of each active type pair. They must satisfy \(\sum_{u:\{t,u\}\in F}x_{tu}\le\mu_t\); the remaining mass \(p_t=\mu_t-\sum_u x_{tu}\) is unmatched and earns zero. A mass \(x_{tu}\) of type \(t\) can be paired with the same mass of type \(u\), and earns \(y_{tu}\) and \(y_{ut}\), respectively, with \(y_{tu}+y_{ut}=w_{tu}\). The underlying matching objective is to maximize \(\sum_{\{t,u\}\in F}w_{tu}x_{tu}\), as in the paper’s maximum-weight-matching step.
To state stability and balance, let \(q_t\) be the lowest payoff received by positive mass of type \(t\), including zero if \(p_t>0\). Define the best alternative for type \(t\) as
\[
a_t=\max_{v:\{t,v\}\in F}(w_{tv}-q_v)_+.
\]
Stability requires \(q_t+q_u\ge w_{tu}\) for every eligible pair. For every active pair, the continuous \(\varepsilon\)-division condition requires
\[
\left|y_{tu}-a_t-r_{tu}(w_{tu}-a_t-a_u)\right|\le\varepsilon.
\]
The condition for the other endpoint follows from the same equation and the exact sum of earnings. In an atomless population, excluding an individual’s current partner does not change the best alternative: removing a single person does not change the essential supremum over that type. Thus the definition tracks the paper’s surplus and split condition. The output is the mass matching and its allocation, or a certificate that no such outcome exists.
This preserves the paper’s one-partner constraint, stability requirement, pairwise profits, and unequal division of surplus. It changes the population to a continuum. Earnings can still vary by partner type, so the model does not erase the bargaining question by forcing every member of a type to receive the same amount.
I expect this mirror to be Class A, though Theorem 2.3 does not establish that. With \(\tau\) types, the matching variables are finite in number, and the maximum-surplus matching step becomes a fractional matching LP. The paper’s damped rebalancing is a promising starting point for balancing those type-pair cohorts. The question to hand a prover is whether an \(\varepsilon\)-UD outcome, or a certificate of nonexistence, can be computed in \(\operatorname{poly}(\tau,L,1/\varepsilon)\) time, where \(L\) is the binary input length. An additional structural question is whether fractional matching makes the “unstable” case disappear in this model. A further deliverable would be a precise finite-population dictionary: when does a solution for masses give a useful approximation for large finite blow-ups of the type graph?
The weakest point is the step from the paper’s arbitrary finite graph to a finite type graph with mass capacities. Theorem 2.3 runs rebalancing on individual matched edges; it does not prove that the process compresses to \(\tau\) types or that its runtime becomes independent of the number of agents. Proving that compression and its algorithmic guarantees is the research question, not a consequence of the theorem. The mirror is still worth pursuing because it retains the unequal-division bargaining problem while making population mass, rather than named individuals, the model’s basic unit.
The sole anchor is Theorem 2.3, and it is a genuine computational result: given a finite graph, it finds an \(\varepsilon\)-UD outcome or reports instability. The strongest objection is that the proposed compression to \(\tau\) types changes the network model substantially. In the paper, feasibility, profit, and bargaining split are attached to individual edges of an otherwise arbitrary graph. In the proposed mirror, they are determined by type pairs, so the graph becomes a block model in which agents of a type have the same eligible partner types and pair parameters. If types are meant to preserve arbitrary individual neighborhoods, the type list alone no longer determines feasible matchings; encoding those neighborhoods can bring the original graph-sized input back.
That leaves two choices. Preserve arbitrary network structure, and the population masses do not suffice to express the problem compactly. Or use the type-complete market, where mass matching and coupled type-level payoffs are meaningful but the mirror covers a structured subclass of bargaining networks. The theorem’s edge-by-edge rebalancing also does not directly carry over: a type’s mass can be split among several partner types, so multiple active pair cohorts share the same outside-option minima. Establishing that aggregate dynamics is part of a new algorithmic result.
This is a real limit on the proponent’s claim that Theorem 2.3 supplies the mirror. It does not establish compression or the proposed runtime in \(\tau\) and the input bit length. But it does not defeat the best version of the mirror: a large typed job or exchange market with type-pair eligibility, profits, and bargaining shares is plausible, and the paper itself motivates bargaining networks with markets. The population and per-capita quantities are then sensible. I cannot honestly turn the network-compression objection into a universal case that no worthwhile mirror exists; its force depends on whether the authors regard that structured market as their problem.
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.