| paper | d4-conf-aaai-2007-0270 |
| 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→NP-hard discrete result → its continuous mirror
Answer: NP-hard, even with \(r=\tau=2\), nonnegative integer-valued valuations, and \(K=\tfrac14\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2 (Complexity)
Given a finite-support distribution μ over role-level agent types ρ, bundles \(B\), and payment balances π, a role graph \(H\), per-capita copies of the indivisible goods, encoded valuations, and a rational threshold \(K\), decide whether nonnegative rational masses \(x_d\) of finitely encoded deal templates fit within each source type’s mass and induce a distribution μ' with \(E(μ)-E(μ')\ge K\). Each template involves a clique of roles, conserves its participants’ goods, balances payments, and makes every participant strictly better off; \(E(ν)=∑_{z,z':(ρ(z),ρ(z'))\in E_H}ν_zν_{z'}e(z,z')\), using the paper’s pairwise envy notion.
A continuum of repeated agent types carrying mass, with each type fixing its role, valuation, initial integral bundle, and payment balance. Deal-template masses split those types into participating and unaltered groups; goods remain indivisible for each participant, while the available copies scale with population. The objective measures total pairwise envy over the resulting distribution.
The mass action permits batches of templates and potentially extra interactions, so the paper’s reduction does not automatically establish hardness for this model; the proponent flags that a lift is needed but does not rule out those extra deals.
fatal: False
The mirror covers Theorem 2 (Complexity), the WIER decision problem; it leaves Lemma 1 and Theorem 1’s convergence claims aside, since their termination argument relies on finitely many allocations.
The strongest mirror is a population version of WIER, anchored on Theorem 2 (Complexity). The theorem is proved in this paper: WIER is NP-complete. Its input is a negotiation problem, a state \((A,\pi)\), a rational threshold \(K\), and a polynomial-time computable envy measure that is monotone in each pairwise envy and is zero exactly at envy-free states. It asks whether there is a clique-deal leading to a state \((A',\pi')\) such that every agent is strictly better off, \(v_i(A'(i))-v_i(A(i))>\pi'(i)-\pi(i)\), and envy falls by at least \(K\). The proof reduces from WI, whose hardness—even with two agents—is cited from earlier work. It adds a third agent and guard goods so that no IR deal can involve the added agent or those goods; any IR deal corresponding to a WI solution then eliminates envy. Thus the hardness comes from the allocation and valuation problem, not from a large number of agents.
A plausible high-multiplicity setting is a large resource-sharing marketplace with a finite catalog of indivisible goods and many repeated agent roles. Agents in one role share their valuation, initial bundle, payment balance, and neighborhood class. Their negotiation and visibility relationships are described by a finite role graph \(H\), such as a network of compatibility communities in which everyone in one role can negotiate with everyone in an adjacent role. A role’s type includes all of those attributes, so agents with different prices, bundles, or neighborhoods are different types. The population is a distribution \(\mu\) over these types: \(N\) may be large while the initial support size \(\tau\) stays small. Goods scale with the population as copies of the same catalog; each individual still receives an integral bundle.
Call the resulting decision problem Block-Mass WIER. A state is a finite-support distribution \(\nu\) over atoms \(z=(\rho,B,\pi)\), where \(\rho\) is a role, \(B\) is an individual’s integral bundle, and \(\pi\) is their payment balance. An action chooses a clique \(C\) of roles in \(H\) and a finite list of local deal templates. Each template specifies, for one participant from each role \(\rho\in C\), new bundles \(B'_\rho\) and payment changes \(p_\rho\). It must conserve the packet’s goods, satisfy \(\sum_{\rho\in C}p_\rho=0\), and make every participant strictly better off:
\[
v_\rho(B'_\rho)-v_\rho(B_\rho)>p_\rho.
\]
The decision variables are the rational masses \(x_d\) assigned to templates \(d\), with the total mass using each role no greater than its available mass. Unused agents keep their old bundles and balances; participants split into new state atoms.
Use the continuous analogue of total pairwise envy,
\[
e(z,z')=\max\{v_{\rho(z)}(B_{z'})-\pi_{z'}-v_{\rho(z)}(B_z)+\pi_z,0\},
\qquad
E(\nu)=\sum_{z,z':\,(\rho(z),\rho(z'))\in E_H}\nu_z\nu_{z'}e(z,z').
\]
The question is whether some such mass deal produces \(\nu'\) with \(E(\nu)-E(\nu')\ge K\). For a finite population represented by equal masses, \(E\) is total pairwise envy normalized by the square of the population size. Setting \(K=E(\nu)\) asks whether a mass of local, individually rational deals can eliminate envy entirely.
I expect this mirror to be Class B: the discrete hardness should transfer. The paper’s reduction already starts with a constant number of agents. In the cohort version, a template must satisfy IR for each participant, not merely on average across a type. If no source WI deal exists, there is no IR template to apply to positive mass. If one does exist, it can be applied across the corresponding cohorts, and the guard construction removes the envy as in the paper’s proof. That makes this a credible route to hardness even when \(\tau\) is small; a formal result would still need to spell out the cohort lift and the envy measure.
This case mirrors Theorem 2 only. I would not claim that Lemma 1 or Theorem 1 carries over unchanged: their termination argument relies on the finite set of allocations, and convergence in a continuum needs a separate analysis. The main weakness here is the network model. A mass of parallel local deals is a natural population-level action, but it is not literally one deal among named agents in a finite clique. The mirror is most convincing for large populations with repeated roles and block-structured interaction; with highly idiosyncratic neighborhoods, the number of types may grow with the population and the high-multiplicity motivation fades.
Theorem 2 is the right—and only—anchor. It is a genuine computational result: WIER is NP-complete. So the strongest case against has to challenge the proposed population model, not dismiss the theorem as axiomatic or irrelevant.
The paper asks whether one clique-deal among named agents exists. A distribution over types does not, by itself, say which agents can be grouped into such a deal. The proposed mirror supplies that missing structure with a role graph and allows a mass of agents to execute deal templates. That is a reasonable model, but it changes the action from one deal to a batch of deals. Its envy objective also depends on how participants are paired and on the resulting mass distribution. Those choices define a new computational problem; they do not follow uniquely from Theorem 2.
There is a stronger, faithful version of the mirror: use repeated roles, per-capita copies of the goods, a fixed block interaction graph, and a coupling that specifies how mass from different roles participates in the same deal. This removes the objection that individual bundles must become fractional. But it also makes clear what remains to be shown. The paper’s reduction establishes hardness for a single instance with two source agents. Replicating that instance in cohorts does not automatically prove the proposed mass problem hard: deals between members of different cohorts could combine goods in ways absent from the source instance. A lift would need to rule out those extra deals, or give them a deliberate interpretation. Even if it does, the resulting result may simply be the finite WIER instance repeated across the population.
That is a real weakness in the proponent’s argument, but it is not enough to defeat the anchor. A well-specified block-population model with mass pairings and a pairwise-envy objective is coherent, and studying whether such deals exist or how much envy they can reduce is a computational question. The paper’s network structure makes the modelling less canonical than the bribery example, and the proponent has not yet established that its reduction survives the lift. Still, I cannot honestly argue that no worthwhile mirror exists in any scenario. The negative case is weak at its universal claim; Theorem 2 remains a plausible mirror, pending a careful definition and proof.
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.