| paper | d4-conf-ecai-2014-0049 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Exact terminal-offer computation is polynomial-time solvable in \(\tau\) and \(L\); every input satisfying the stated hypotheses is feasible. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 7
statement extracted from the paper’s text layer
Given a terminal proposer with voting weight \(w_0\) and a responder society with rational type masses \(\mu_t\), where \(\sum_t\mu_t=1\), each type \(t\) has voting weight \(w_t\), discount factor \(\delta_t\), and per-capita conflict share \(\alpha_t\). For quota \(q\) and proposer outside payoff \(d_0\), choose offered fractions \(y_t\in[0,1]\) minimizing \(\sum_t\mu_t y_t\delta_t\alpha_t\), subject to \(w_0+\sum_t\mu_t y_t w_t\ge q\) and \(1-\sum_t\mu_t y_t\delta_t\alpha_t\ge d_0\). Compute the accepting fractions and the proposer’s residual share.
A distinguished terminal proposer faces an atomless electorate described by type masses \(\mu_t\). The decision variables are the fractions \(y_t\) of each type offered its discounted conflict share; the objective minimizes total payments while meeting the weighted quota, and the proposer receives the remaining resource.
The proposer remains a distinguished atomic player, so this mirrors the terminal offer against a continuous electorate rather than continuizing every bargaining role.
fatal: False
The mirror covers Theorem 7’s terminal-offer computation; it leaves the full finite-horizon equilibrium, agenda analysis, and core results untouched.
The strongest positive case is narrow: the terminal-offer computation behind Theorem 7. The theorem says that, when the players’ conflict shares satisfy \(\alpha_i\ge 0\) and \(\sum_i\alpha_i=1\), computing an equilibrium offer for \(G_1\) is NP-hard even under perfect information. The paper proves this here. Its proof reduces the last proposer’s choice to selecting a winning coalition that minimizes the discounted conflict payments, a 0–1 knapsack problem.
A plausible high-multiplicity regime is a large legislative or union bargaining chamber organized into a small number \(\tau\) of caucus types. The chamber may have \(N\) members with \(N\gg\tau\); members of a type share their voting weight, discount factor, and conflict entitlement. In this regime, caucuses are the bargaining and agenda units: the caucus with the terminal proposal turn acts in its members’ common interest, and offers can cover a fraction of another caucus’s mass. That is a concrete population model, though it requires the caucuses to have delegated authority.
Call the mirror problem Atomless Final-Offer Computation. An instance has rational type masses \(\mu_t>0\), with \(\sum_t\mu_t=1\), and for each type \(t\), a per-member voting weight \(w_t>0\), discount factor \(0<\delta_t\le1\), and per-member conflict share \(\alpha_t\ge0\), normalized so \(\sum_t\mu_t\alpha_t=1\). A quota \(q\) and terminal proposer type \(r\) are also given. Assume the total available voting weight can meet the quota.
Choose \(y_t\in[0,1]\) for each \(t\ne r\), the fraction of that type offered its discounted conflict share \(\delta_t\alpha_t\). The remaining fraction gets zero and rejects; the offered fraction accepts at indifference. The proposer caucus receives a uniform per-member share \(x_r\). The question is to compute the accepted terminal offer maximizing \(x_r\), together with the accepting mass fractions. The resource constraint is
\[ \mu_r x_r+\sum_{t\ne r}\mu_t y_t\delta_t\alpha_t\le1, \]
and approval requires
\[ \mu_r w_r+\sum_{t\ne r}\mu_t y_t w_t\ge q. \]
Thus the problem is to minimize \(\sum_{t\ne r}\mu_t y_t\delta_t\alpha_t\) subject to that approval constraint and \(0\le y_t\le1\), then give the proposer the remaining resource. Since \(\sum_t\mu_t\alpha_t=1\), this remaining per-member share is at least \(\alpha_r\), and hence at least the proposer’s discounted conflict share \(\delta_r\alpha_r\). The proposed agreement is individually acceptable to the proposer as well.
This is a rational linear program with \(\tau-1\) variables, so it is solvable exactly in time polynomial in \(\tau\) and the input bit length \(L\). It is a Class A mirror: the integer coalition choice in the theorem’s knapsack reduction becomes a choice of mass, and fractional participation removes that indivisibility. The question keeps the terminal bargaining objective, weighted approval, discounting, conflict point, and divisible resource; it asks whether the paper’s hardness survives when the voters are a distribution over types.
The scope is Theorem 7’s terminal-offer computation, not the paper’s full \(T\)-round equilibrium analysis. My weakest point is the move from an individual proposer in the paper to a caucus with delegated proposal authority. That is plausible in some large chambers, but it is a model change, and authors might reject it for settings where individuals bargain and take turns separately. The case survives only in the caucus regime: there, the hard choice identified in Theorem 7—how much support to buy at each reservation value—is exactly a choice of mass. Natural follow-ups are whether a full type-level, finite-horizon equilibrium can be computed by backward induction, and how well its fractional terminal offers approximate a large finite chamber with \(N\) members.
Theorem 7 is a genuine computational result, so the negative case cannot dismiss this anchor for lack of something to mirror. The strongest objection is that the proposed mirror changes who bargains.
In the paper’s terminal round, one named player proposes; the other \(p-1\) players decide whether to accept. Each responder contributes their own weight and has their own discounted conflict share. In the proponent’s caucus model, however, the entire proposer type contributes \(\mu_r w_r\) to approval and receives the residual resource across its mass. That treats many members as if they jointly held one proposer’s turn. In the paper, only one player has that turn; other members of the same type are responders and must be persuaded. Making them a caucus with delegated authority is plausible, but it changes the bargaining game rather than simply making its population continuous.
The faithful high-multiplicity version exposes a singular role. With \(N\) players, a terminal proposer remains one person, while their mass among the responders is \(1/N\). In the limit, that mass vanishes, but the proposer’s authority and personal payoff do not. A distribution over types alone cannot represent both facts. Giving the proposer a positive mass makes the proposer a bloc and changes the game; letting their mass vanish loses their individual role. The paper’s fixed agenda creates this problem for the full equilibrium too, since proposal authority belongs to particular positions.
There is a stronger repair: keep a distinguished proposer and make only the responders atomless. The terminal offer can then be posed over a distribution of voter types, with approval determined by aggregate voting weight and offer costs by aggregate discounted conflict shares. That is a coherent continuum-electorate bargaining problem. But it is a hybrid with an exceptional individual at its center, rather than the paper’s society becoming a distribution over types. Whether the authors would count that as their continuous-population question is the decisive uncertainty.
The objection is weaker if a legislature or union genuinely delegates proposal authority to a caucus. Then the proposed model may be sensible in its own right. But that scenario does not establish that Theorem 7 has a faithful continuous mirror: it makes a bloc the proposer, while the theorem’s hard choice belongs to one individual. I would not claim this defeats every possible mirror. The atomless electorate with a marked proposer is a credible candidate, and the negative case is weakest precisely 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.