d4-conf-atal-2010-0199

The strongest mirror is Mass Embedded-MC EGSV Evaluation. Consider a large automated trading market in which many agents share a complete payoff-relevant profile: strategy, capabilities, costs, and other attributes used by the game. The society is \(\mu\), a distribution over the \(\tau\) supported types, with \(n\) potentially enormous and \(\tau\ll n\). Cohorts of a type join an alliance together, and the given a priori coalition structure groups types into blocs. Strategy changes by one bloc can affect the payoffs of others, just as the paper’s externalities do.

An instance consists of rational masses \(\mu_t\) summing to \(1\), a list of embedded rules over types, and a fixed coalition structure \(\pi=\{B_1,\ldots,B_K\}\) partitioning the supported types. A pattern \(P^+\land\neg P^-\) matches a bloc \(B\) when \(P^+\subseteq B\) and \(P^-\cap B=\emptyset\). An embedded rule matches when its target pattern matches \(B\) and each external pattern appears in at least one other bloc. Give each rule a per-unit payoff rate \(q\); when it matches, it contributes \(q\lambda(B)\), where \(\lambda(B)=\sum_{t\in B}\mu_t\). This scaling makes a rule’s payoff reflect the population mass receiving its contribution.

The task is to compute the EGSV allocation to each bloc, and optionally its per-capita rate. Define \(B_S=\bigcup_{j\in S}B_j\) and \(v_{\mu,\pi}(S)=w_\mu(B_S,\{B_S,\Theta\setminus B_S\})\), with the empty coalition assigned value zero. The requested output is
\[ \phi_j=\sum_{S\subseteq [K]\setminus\{j\}} \frac{|S|!(K-|S|-1)!}{K!} \left(v_{\mu,\pi}(S\cup\{j\})-v_{\mu,\pi}(S)\right) \]
for every bloc \(j\), together with \(\phi_j/\lambda(B_j)\) if per-capita rates are wanted. This is a value-computation problem, so it has no decision variable or optimization objective.

My lead anchor is Theorem 5.5, proved in this paper. It says that for a game represented by one embedded rule \(p_0\land\neg p'_0\mid p_1\land\neg p'_1,\ldots,p_k\land\neg p'_k\to V\), the game \(\chi(w)\) of EGSV values has a representation by two exclusive embedded rules. Let \(A=P_0\cup\bigcup_{i\ge1}P'_i\) and \(B=P'_0\cup\bigcup_{i\ge1}P_i\). Both transformed rules require the a priori partition to divide \(A\) and \(B\): some union of its blocs contains \(A\), and the remaining blocs contain \(B\). The first rule matches a target coalition containing a member of \(A\); its value is \(VD\). The second matches one containing a member of \(B\); its value is \(VD'\). Here \(r\) counts blocs meeting \(A\), \(s\) counts blocs meeting \(B\), \(D=1/[r\binom{r+s}{r}]\), and \(D'=-1/[s\binom{r+s}{s}]\), with the corresponding coefficient zero when \(r\) or \(s\) is zero. The paper uses this transformation to compute EGSVs; it is a representation theorem used in the computation, rather than a theorem explicitly phrased as an in-\(\mathrm P\) classification.

The mass-scaled rules in this mirror can be expanded into ordinary embedded rules: for each type \(t\) that is not forbidden by the target pattern, add \(t\) to that pattern’s positive literals and use value \(q\mu_t\). When the original pattern matches a bloc, these rules sum to \(q\lambda(B)\). Applying Theorem 5.5 to the expanded rules gives a polynomial-size computation, with running time polynomial in the rule description size, \(\tau\), \(K\), and the rational bit length \(L\). I therefore expect this mirror to be tractable. The paper has no named hardness result to anchor here; its relevant computational result is algorithmic.

This is a credible mirror because it preserves the paper’s central object: computing EGSV for a game with externalities, with the coalition blocs still receiving Shapley-style allocations. The scope is specifically this computation for type-homogeneous, type-aligned coalitions and mass-scaled embedded rules. It does not cover coalition-structure generation, the paper’s expressivity results, or other solution concepts.

The weakest point is that the finite EGSV calculation is still over \(K\) macroscopic blocs; the continuum enters through population mass and normalized payoffs, rather than through an atomless Shapley value over individuals. The type-aligned regime also excludes a cohort being split across several blocs unless those portions are modeled as distinct types. Those limits matter, but they describe an instance regime, not a rejection of the population mirror. A natural next question is whether the two-rule computation survives when type mass can be split across blocs or when rule effects depend on mass thresholds rather than type presence.