d4-conf-atal-2008-0078

The strongest mirror I believe in is a single-type, atomless version of CORE MEMBERSHIP. It uses the paper’s own single-agent case, where the hardness already lives in checking one agent’s Boolean goal.

The anchor is Theorem 1, proved in this paper: CORE MEMBERSHIP is co-NP-complete even when the game has one agent and the valuation being checked is empty. In other words, deciding whether a given valuation belongs to the core is co-NP-complete under both restrictions. The paper proves this by reducing SAT to the complement of membership.

Take a population of many identical autonomous units, each with the same local Boolean settings, goal formula, and action costs. A type specifies that local template; each unit controls its own private copy of the template’s variables. For example, the units could be mass-produced devices, each choosing a Boolean configuration to meet the same local operating requirement. The regime has arbitrarily many units and just one type, so \(\tau=1\). The units’ individual settings remain integral Boolean valuations.

Here is the continuous problem. An instance gives a finite local variable set \(\Phi\), costs \(c\), a goal formula \(\gamma\), and a finite-support rational allocation \(x=(x_\xi)_{\xi\subseteq\Phi}\), where \(x_\xi\) is the fraction of the population using local valuation \(\xi\), and \(\sum_\xi x_\xi=1\). Each unit gets the paper’s goal-first, cost-second preferences on its own copy. The question is whether this allocation is in the atomless core: there must be no measurable coalition of positive mass whose members can change their own settings so that every member strictly prefers the result. A positive mass at \(\xi\) can block whenever some valuation \(\xi'\) is strictly better for those units. The solution is a yes/no membership answer; there is no planner objective in the anchor.

This continuous problem is co-NP-complete for the stated finite-support representation. Non-membership has a short certificate: a valuation with positive allocated mass and a strictly better local valuation. For hardness, use the reduction in Theorem 1: given SAT formula \(\Psi\), set \(\Phi=\{x_1,\ldots,x_k,d\}\), \(\gamma=\Psi\land d\), and give every variable cost \(1\). Put the whole population at the empty valuation. If \(\Psi\) is satisfiable, a positive-mass coalition can move to a satisfying valuation and strictly improve. If \(\Psi\) is unsatisfiable, the empty valuation has minimum cost and no valuation satisfies the goal, so no coalition can block. Thus the continuous allocation is in the core exactly when \(\Psi\) is unsatisfiable.

I expect hardness transfers (Class B) for this mirror. Each individual still chooses a Boolean valuation; only the fraction of the population taking each valuation is continuous. The reduction also matches the paper’s preferences: with one type, the total local action cost is the paper’s \(\mu\), and the usual finite replication changes the utility scale but not the strict preference or blocking relation.

The scope is deliberately narrow: it mirrors Theorem 1’s single-agent restriction, not the paper’s general interacting-agent core results, stable sets, or bargaining protocol. The main weakness is that the population consists of independent replicas, so it does not capture the cooperation that motivates much of CBG. That is a real limit on the mirror’s reach. It is also faithful to the chosen anchor: the paper explicitly proves hardness even in the one-agent case, and its SAT reduction survives when a unit mass of identical agents each has the same local problem.

Further questions include whether a continuous core can be defined for CBG goals that depend on other agents’ settings while retaining the paper’s Boolean semantics, and whether core non-emptiness in that interacting population model is tractable or hard.