| paper | d4-conf-aaai-2015-0578 |
| 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: \(\mathrm{NP}\text{-complete}\), already for \(\tau=1\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a finite distribution of rational masses \(\lambda_r\) over exchange-cell templates, each with \(n\) roles and an independent ATTC run, choose a reported ranking \(\hat\succ_r\) for the designated role in each template to maximize \(G=\sum_r (\lambda_r/n)\mathbf{1}[\phi_i(E_r[\hat\succ_r])\,P_i^r\,\phi_i(E_r)]\); decide whether \(G\ge\theta\) for a supplied rational threshold \(\theta\).
A continuum of copies of finite exchange-cell templates, represented by role types \((r,j)\) of mass \(\lambda_r/n\). Each cell runs the paper's ATTC procedure with integral bundles; the decision variable is a common reported ranking for the designated role across copies of each template, and the objective is the mass of that role receiving a strictly better bundle.
The mirror covers Theorem 2's beneficial-misreport hardness for the designated role across repeated exchange cells. It leaves the core-selection result and the splitting-to-misreport result without continuous analogues.
The strongest mirror I believe is a positive-mass ATTC misreport problem. Its natural regime is a continuum of repeated, autonomous exchange cells: for example, many regional barter exchanges or campus housing markets using the same local procedure. A cell has a finite set of roles, goods, endowments, and lexicographic preferences. Across cells, people in the same role have the same complete type, including their endowment and preference; goods are copied within each cell, and trades stay inside it. The number of people can grow with the number of cells while the number of distinct role types stays fixed. Each person still receives an integral bundle; averages across a type can be fractional.
The anchor is Theorem 2, proved in this paper. It says that BENEFICIAL-MISREPORT is NP-hard: given an exchange problem \((e,\succ)\) and an agent \(i\), finding a reported linear order \(\succ'_i\) such that
\[
\phi_i(e,(\succ'_i,\succ_{-i}))\,P_i\,\phi_i(e,\succ)
\]
is NP-hard. The paper proves this by reduction from ACM 3SAT.
Here is a precise continuous version. Let the instance be a finite distribution over exchange-cell templates \(r\), with rational masses \(\lambda_r\) summing to \(1\). Each template has the same \(n\) roles and specifies a finite local exchange problem \(E_r\); every role \(j\) has mass \(\lambda_r/n\). Let \(i\) be the designated strategic role. The type of a participant is \((r,j)\): their template, role, initial bundle, and true ranking. A solution gives one reported ranking \(\hat\succ_r\) for role \(i\) in each template. Run ATTC in each cell with that report and the other roles’ truthful reports. The objective is to maximize
\[
G(\hat\succ)=
\sum_r \frac{\lambda_r}{n}
\mathbf{1}\!\left[
\phi_i(E_r[\hat\succ_r])\,P_i^r\,\phi_i(E_r)
\right].
\]
The decision form asks whether some reports achieve \(G(\hat\succ)\geq\theta\), for a supplied rational threshold \(\theta\). A solution is the report for each targeted role type; the outcome for each participant remains an integral bundle.
For one template copied throughout the society, take \(\lambda_r=1\) and \(\theta=1/n\). A report succeeds for the target role in every copy or in none, so this continuous instance has a beneficial report exactly when the original Theorem 2 instance does. The mirror is therefore expected to be hardness-transferring (Class B): the reduction’s combinatorics lie in the local goods and rankings, and replication records the mass of agents facing that problem. This is not a claim that multiplicity makes the manipulation harder or easier.
This regime is plausible where many autonomous exchanges repeat stable roles and endowment patterns, including roles with substantial inventories. The same manipulation is still the agents’ underlying problem: each target-role participant must find a report that improves their ATTC allocation. The mass objective asks how prevalent that gain is across the population. I am mirroring Theorem 2 alone; I am not claiming a continuous analogue of the core-selection result or the splitting result.
The main weakness is the cell boundary. This mirror treats the population as many repeated local exchanges, rather than one connected exchange economy whose own population tends to a continuum. If the authors or a referee require that stronger regime, the problem needs a type-level ATTC definition with per-capita replicated goods; Theorem 2 by itself does not show that the same hardness survives that construction. Further questions include whether hardness persists with bounded endowment size, and whether a connected continuum ATTC admits tractable type-level algorithms.
Theorem 2 is the only computational anchor, and its object is a named agent’s profitable deviation. The agent has a particular endowment and asks whether changing her ranking improves the bundle she receives. In an atomless society, that agent has zero mass. A distribution over types can describe the population around her, but it does not record a unilateral report or its effect on her allocation. Giving a positive mass of one type a common false ranking makes the deviation observable; it also changes the question to coordinated type-level manipulation.
The proposed repeated-cell mirror avoids that problem by giving each copied cell a fresh finite exchange market. But then ATTC runs separately inside each cell, and the cells never exchange goods or affect one another. For one repeated template, a report succeeds in every copy or none; asking whether \(G\geq 1/n\) simply restates whether the original named agent can benefit. With several templates, the objective measures how often the same local manipulation works across a distribution of independent instances. That could be a question about repeated markets, but it does not make the society in this paper continuous.
A connected-market version would be a better candidate. It would need repeated endowment and preference types while retaining the paper’s lexicographic preferences over named, indivisible goods. In the stated model, goods are distinct and endowments partition them, so identical complete types do not recur. Grouping copies of goods into interchangeable categories could create repeated types, but that co-modification also requires a mass-level ATTC rule and a way to evaluate a single agent’s deviation in it. A rule for positive-mass coordinated deviations is conceivable; it would study a type bloc’s manipulation. Tracking one agent separately preserves Theorem 2’s question only by adding a distinguished atom to the continuum.
This is a substantial weakness in the negative case: a connected mass-exchange model with a tagged agent, or a deliberately bloc-level strategic question, may be worth formulating. The paper does not rule those out. But neither rescues the proposed mirror as a continuous-population version of Theorem 2: one keeps the individual problem outside the continuum, and the other changes the manipulator from one agent to a positive-mass group.
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.