d4-conf-atal-2014-0060 (d4-conf-atal-2014-0060)

Given a finite role set \(T\), a role graph \(H\), rational proportions \(\mu\), and an explicit rational polynomial \(g\) with \(g(0)=0\), form populations of \(N\) agents with \(N_t/N\to\mu_t\). Agents in the same role form a clique, and roles adjacent in \(H\) have all-to-all links. A connected coalition \(S\) has worth \(N g(x(S))\), where \(x_t(S)=|S\cap V_t|/N\); a disconnected coalition has the sum of its connected components’ worths. Compute the limit, as \(N\to\infty\), of each role’s per-agent Myerson value.

A society is given by its support: a nonempty list of \(\tau\) roles \(T\) with positive binary-rational masses \(\mu_t\), satisfying \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; set \(m=|T|=\tau\).
The input also contains a simple undirected graph \(H\) on \(T\) and an explicit polynomial \(g\in\mathbb Q[x_t:t\in T]\) with \(g(0)=0\). Encode it as a list of monomials with binary-rational coefficients and unary nonnegative integer exponents; let \(d\) be its total degree and \(L\) the total input bit length. Coefficients and coalition worths may have either sign.
For every sequence of integer populations with \(\sum_t N_t=N\) and \(N_t/N\to\mu_t\), form a graph \(G_N\) whose role classes \(V_t\) are cliques, with all edges between classes precisely when their roles are adjacent in \(H\).
For nonempty connected \(S\), assign worth \(N g(x(S))\), where \(x_t(S)=|S\cap V_t|/N\). For arbitrary \(S\), let \(v_N(S)\) be the sum of these worths over its connected components, and set \(v_N(\varnothing)=0\). Let \(a_t(N)\) be the Shapley value in \(v_N\) of any one role-\(t\) agent; this is its Myerson value, without further normalization.

Do the limits \(a_t=\lim_{N\to\infty}a_t(N)\) exist as rational numbers independently of the population sequence, and is computing all of them exactly in polynomial time or NP-hard? State running times in \(m,\tau,L,d\).

Known discrete results: DFS enumeration of connected induced subgraphs of an \(n\)-clique examines exactly \(2^{n-2}(n^2-n+4)-(n+1)\) edges; a finite Myerson-value algorithm enumerates connected coalitions with oracle access to their worths. [Source](https://aamas.csc.liv.ac.uk/Proceedings/aamas2014/aamas/p197.pdf)
No result settling this exact population-limit computation was identified in the literature search.

1. Result

All the limits exist, are rational, and are independent of the population sequence. Computing all of them exactly is polynomial-time solvable.

Write the polynomial, omitting constant terms whose sum is zero, as
\[ g(x)=\sum_{\alpha}c_{\alpha}x^{\alpha}, \qquad |\alpha|=\sum_{s\in T}\alpha_s\geq 1. \]
For each role \(t\), let \(C(t)\) be its connected component in \(H\), and let \(\mu^{C(t)}\) equal \(\mu\) on \(C(t)\) and zero outside it. Then
\[ \boxed{ a_t=\int_0^1 \partial_t g\bigl(u\mu^{C(t)}\bigr)\,du = \sum_{\substack{\alpha_t>0\\ \operatorname{supp}(\alpha)\subseteq C(t)}} \frac{c_{\alpha}\alpha_t}{|\alpha|} \prod_{s\in T}\mu_s^{\alpha_s-\mathbf 1_{\{s=t\}}}. } \]
In the product, all exponents are nonnegative because the sum only includes terms with \(\alpha_t>0\).

The main issue in proving this formula is controlling early predecessor coalitions that omit some roles. Their marginal contributions need not be uniformly bounded in population size. The following argument controls their total contribution explicitly.

2. Predecessor coalitions and connectivity

Fix a role \(t\). Since \(\mu_t>0\), a role-\(t\) agent exists for every sufficiently large population. Fix such an agent \(i\).

In a uniformly random permutation of all \(N\) agents, let \(S\) be the set preceding \(i\), and let \(k=|S|\). The position of \(i\) is uniform, so \(k\) is uniform on \(\{0,\ldots,N-1\}\). Conditional on \(k\), the set \(S\) is a uniformly chosen \(k\)-element subset of the other \(N-1\) agents. Consequently,
\[ a_t(N)=\frac1N\sum_{k=0}^{N-1} \mathbb E\bigl[v_N(S\cup\{i\})-v_N(S)\mid |S|=k\bigr]. \]

Call \(S\) good if it contains an agent from every role. For a good coalition, its graph components correspond exactly to the connected components of \(H\): a path in \(H\) lifts to a path between represented role classes, and any path between classes projects to a walk in \(H\).

Let \(C=C(t)\), and define the vector \(X^C\) by
\[ X^C_s= \begin{cases} |S\cap V_s|/N,&s\in C,\\ 0,&s\notin C. \end{cases} \]
Adding \(i\) changes only the component corresponding to \(C\). Thus, on the good event, its marginal contribution is
\[ \Delta_{N,t}(S) :=v_N(S\cup\{i\})-v_N(S) = N\left[g\left(X^C+\frac{e_t}{N}\right)-g(X^C)\right]. \]
By the fundamental theorem of calculus,
\[ \Delta_{N,t}(S) = \int_0^1 \partial_t g\left(X^C+\frac{z e_t}{N}\right)\,dz. \]

This identity applies regardless of the signs of the coefficients or worths.

3. Coalitions omitting roles have vanishing total contribution

Let
\[ A=\sum_{\alpha}|c_\alpha|. \]
For \(x\in[0,1]^m\), every positive-degree monomial satisfies \(x^\alpha\leq\sum_s x_s\). Indeed, choosing a coordinate with positive exponent gives \(x^\alpha\leq x_s\). Therefore
\[ |g(x)|\leq A\sum_s x_s. \]

Apply this bound to each connected component of a coalition \(R\). Their sizes sum to \(|R|\), giving
\[ |v_N(R)|\leq A|R|. \]
Hence every predecessor coalition of size \(k\), good or otherwise, satisfies
\[ |\Delta_{N,t}(S)|\leq A(2k+1). \]

We next bound the probability of omitting a role. Among the agents other than \(i\), put
\[ M=N-1, \qquad n_s=N_s-\mathbf 1_{\{s=t\}}, \qquad p_s=\frac{n_s}{M}. \]
Because \(p_s\to\mu_s>0\), there is a constant \(c>0\), independent of sufficiently large \(N\), such that \(p_s\geq c\) for every role.

If \(k\leq M-n_s\), the probability that a uniform \(k\)-element predecessor set contains no role-\(s\) agent is
\[ \frac{\binom{M-n_s}{k}}{\binom{M}{k}} = \prod_{j=0}^{k-1}\frac{M-n_s-j}{M-j} \leq (1-p_s)^k \leq e^{-ck}. \]
If \(k>M-n_s\), that probability is zero. A union bound therefore gives
\[ \Pr(S\text{ is not good}\mid |S|=k)\leq m e^{-ck}. \]

Let \(F_t=\max_{x\in[0,1]^m}|\partial_t g(x)|\), which is finite. The contribution of bad coalitions to the averaged difference between \(\Delta_{N,t}(S)\) and any quantity bounded by \(F_t\) is at most
\[ \frac{m}{N}\sum_{k=0}^{N-1} \bigl(A(2k+1)+F_t\bigr)e^{-ck} \leq \frac{m}{N}\sum_{k=0}^{\infty} \bigl(A(2k+1)+F_t\bigr)e^{-ck}. \]
The infinite series converges, so this bound tends to zero.

This is the step that prevents exceptional connectivity near the beginning of the permutation from surviving in the population limit.

4. Convergence on good coalitions

Set \(u=k/N\). Conditional on \(k\), the count \(K_s=|S\cap V_s|\) has mean \(kp_s\). Its variance is at most \(N\). To see the latter directly, express \(K_s\) as a sum of indicators over the \(n_s\) role-\(s\) agents. Each indicator has mean \(k/M\), while two distinct indicators have covariance
\[ \frac{k(k-1)}{M(M-1)}-\left(\frac{k}{M}\right)^2 = -\frac{k(M-k)}{M^2(M-1)} \leq 0. \]
Thus the variance is at most the sum of the individual variances, and hence at most \(n_s\leq N\).

By the variance bound and Cauchy–Schwarz,
\[ \mathbb E\left[\left|\frac{K_s}{N}-up_s\right|\mid k\right] \leq N^{-1/2}. \]
It follows, uniformly in \(k\), that
\[ \mathbb E\bigl[\|X^C-u\mu^C\|_1\mid k\bigr] \leq \frac{m}{\sqrt N}+\|p-\mu\|_1. \]

Choose \(K_t\) bounding the absolute values of all second partial derivatives \(\partial_s\partial_t g\) on \([0,1]^m\). Such a bound exists because these derivatives are polynomials. Integrating along a line segment in this cube shows
\[ |\partial_t g(x)-\partial_t g(y)|\leq K_t\|x-y\|_1. \]
Therefore, on the good event,
\[ \left|\Delta_{N,t}(S)-\partial_t g(u\mu^C)\right| \leq K_t\left(\|X^C-u\mu^C\|_1+\frac1N\right). \]

Combining this estimate with the bad-coalition bound proves
\[ \left| a_t(N)-\frac1N\sum_{k=0}^{N-1} \partial_t g\left(\frac{k}{N}\mu^C\right) \right| \leq K_t\left(\frac{m}{\sqrt N}+\|p-\mu\|_1+\frac1N\right) +\frac{B_t}{N}, \]
where \(B_t\) is finite and independent of sufficiently large \(N\).

Every term on the right tends to zero. The remaining sum is a Riemann sum for a continuous polynomial function, so
\[ \lim_{N\to\infty}a_t(N) = \int_0^1\partial_t g(u\mu^C)\,du. \]
This proves existence and independence from the population sequence.

For a monomial with \(\alpha_t>0\), its derivative vanishes on \(u\mu^C\) unless \(\operatorname{supp}(\alpha)\subseteq C\). Otherwise,
\[ \partial_t(c_\alpha x^\alpha)\big|_{x=u\mu^C} = c_\alpha\alpha_t\,u^{|\alpha|-1} \prod_s\mu_s^{\alpha_s-\mathbf 1_{\{s=t\}}}. \]
Integrating \(u^{|\alpha|-1}\) gives the stated rational formula.

5. Exact algorithm and bit complexity

Let \(q\) be the number of listed monomials. Here \(q\leq L\), and unary exponent encoding implies \(d\leq L\). The case with no positive-degree terms gives \(a_t=0\) for every role.

The algorithm is:

• Compute the connected-component labels of \(H\).
• Initialize every answer to zero.
• For each positive-degree monomial, inspect its support. If it spans several components, discard it.
• Otherwise compute \(P_\alpha=c_\alpha\prod_s\mu_s^{\alpha_s}\), and, for every \(t\) with \(\alpha_t>0\), add

\[ \frac{\alpha_tP_\alpha}{|\alpha|\mu_t} \]
to \(a_t\).

Division by \(\mu_t\) is valid because all masses are positive. Computing the powers by repeated multiplication gives
\[ O\bigl(m^2+q(m+d)\bigr) \]
graph operations and exact rational arithmetic operations.

To verify polynomial bit complexity, let \(D_c\) be the product of the denominators of the listed coefficients and \(Q\) the product of the denominators of all masses. Each output summand has denominator dividing
\[ D=D_cQ^d d!. \]
Indeed, its coefficient denominator divides \(D_c\), its mass denominators divide \(Q^d\), and its degree divisor divides \(d!\).

The binary length of \(D\) is
\[ O\bigl(L(d+1)+d\log(d+1)\bigr). \]
Moreover, each summand has absolute value at most \(|c_\alpha|\), since \(\alpha_t/|\alpha|\leq1\) and all mass powers lie in \([0,1]\). Consequently, output numerators have polynomial bit length as well.

Define
\[ B=1+L(d+1)+d\log(d+1). \]
Reducing fractions after each operation keeps intermediate integers at \(O(B)\) bits. Using elementary integer arithmetic, including a conservative \(O(B^3)\) bound for rational operations and reduction, gives the explicit bit-running-time bound
\[ \boxed{ O\bigl((m^2+L(m+d))B^3\bigr). } \]
Since \(m=\tau\), this is equivalently
\[ O\bigl((\tau^2+L(\tau+d))B^3\bigr). \]
The total output length is \(O(mB)=O(\tau B)\). These bounds establish polynomial-time exact computation without enumerating connected coalitions.

6. Consequence for the role graph

The limiting values depend on \(H\) only through its connected-component partition.

For example, suppose the three roles form the path \(r-b-s\), and \(g(x)=x_rx_s\). With all three masses positive, the formula gives
\[ a_r=\frac{\mu_s}{2}, \qquad a_s=\frac{\mu_r}{2}, \qquad a_b=0. \]
Thus a role necessary for communication can receive zero per-agent value in the limit. The proof above establishes why its early connectivity contributions vanish.

⟨structured verdict parsed — rendered above⟩

Verdict: proved. The output establishes sequence-independent rational limits and an exact polynomial-time algorithm under the specified encoding. I found no major or minor mathematical issues.

1. Scope and claimed formula

The proof addresses the stipulated support model: \(m=\tau\), every \(\mu_t>0\), and \(g(0)=0\). It permits arbitrary signs for coefficients and worths throughout.

Removing the listed constant terms is valid because their sum equals \(g(0)=0\). Every remaining monomial has positive total degree.

The claimed formula is well-defined. In every retained summand, \(\alpha_t>0\), so all exponents \(\alpha_s-\mathbf 1_{\{s=t\}}\) are nonnegative. The degree divisor \(|\alpha|\) is positive.

Agents within a role are interchangeable in both the graph and the worth function, so the Shapley value of “any one” role-\(t\) agent is unambiguous.

2. Shapley representation and connectivity

The predecessor-set representation is correct: the number \(k\) of predecessors is uniform on \(\{0,\ldots,N-1\}\), and conditional on \(k\), their set is uniform among the \(k\)-element subsets of the other agents. Thus the displayed expression for \(a_t(N)\) is exactly the Shapley value, with the required normalization.

When every role is represented, the coalition components correspond exactly to the components of \(H\). The clique structure connects agents within each role, and the complete adjacency between neighboring role classes lifts every role-graph path. Conversely, graph paths cannot cross between different components of \(H\).

Adding \(i\) to a good predecessor coalition changes only the component containing role \(t\). Consequently,
\[ \Delta_{N,t}(S) = N\left[g\left(X^C+\frac{e_t}{N}\right)-g(X^C)\right] \]
is correct.

The fundamental-theorem-of-calculus application is valid because \(g\) is a polynomial. Its integration segment lies in \([0,1]^m\): in particular, the role-\(t\) predecessor count is at most \(N_t-1\), so adding \(1/N\) cannot make that coordinate exceed \(1\).

3. Exceptional coalitions

The bound controlling bad coalitions is valid and addresses the potentially large connectivity marginal.

For any positive-degree monomial and any \(x\in[0,1]^m\), selecting a coordinate with positive exponent gives
\[ 0\leq x^\alpha\leq x_s\leq\sum_r x_r. \]
Taking absolute values termwise therefore yields the stated bound on \(g\). Applying it separately to connected components gives
\[ |v_N(R)|\leq A|R|. \]
The triangle inequality then gives
\[ |\Delta_{N,t}(S)|\leq A(2k+1). \]
Neither argument assumes nonnegative worths.

The role-omission probability is also correct. For \(k\leq M-n_s\), every factor satisfies
\[ \frac{M-n_s-j}{M-j} = 1-\frac{n_s}{M-j} \leq 1-\frac{n_s}{M}. \]
For larger \(k\), omission is impossible.

Because there are finitely many roles and every limiting mass is positive, the common constant \(c>0\) exists for all sufficiently large populations along each admissible sequence. The union bound consequently holds uniformly in \(k\).

The exceptional contribution is bounded by a constant multiple of
\[ \frac1N\sum_{k=0}^{\infty}(k+1)e^{-ck}, \]
which tends to zero. It is acceptable that the eventual population threshold depends on the sequence: the proof requires convergence along each sequence, not a uniform convergence rate over all sequences.

4. Concentration and passage to the limit

The conditional mean \(\mathbb E[K_s\mid k]=kp_s\) is correct.

The covariance computation checks:
\[ \frac{k(k-1)}{M(M-1)}-\frac{k^2}{M^2} = -\frac{k(M-k)}{M^2(M-1)}. \]
For sufficiently large \(N\), its denominators are nonzero. Nonpositive pairwise covariances imply the stated variance bound, and Cauchy–Schwarz gives the expected absolute-deviation bound.

Summing coordinatewise deviations over \(C\), and using \(u\leq1\), gives
\[ \mathbb E[\|X^C-u\mu^C\|_1\mid k] \leq \frac{m}{\sqrt N}+\|p-\mu\|_1. \]
This estimate is uniform in \(k\).

All second partial derivatives are bounded on the compact cube. Integrating the gradient of \(\partial_tg\) along a segment establishes the stated Lipschitz estimate. Combining it with the good-coalition marginal identity gives the displayed error bound.

The good and bad estimates combine correctly: the expectation of the nonnegative deviation restricted to good coalitions is at most its unrestricted expectation, while the bad-coalition comparison uses the bounded quantity \(\partial_tg(u\mu^C)\).

Every resulting error term vanishes. The remaining average is a left Riemann sum for the continuous function \(u\mapsto\partial_tg(u\mu^C)\). Hence the integral formula follows, independently of the population sequence.

5. Monomial evaluation and rationality

For \(\alpha_t>0\), a monomial involving a role outside \(C(t)\) retains a positive exponent in that outside coordinate after differentiation. Its evaluation at \(u\mu^{C(t)}\) therefore vanishes.

For a monomial supported within \(C(t)\), the displayed derivative has power \(u^{|\alpha|-1}\). Its integral is \(1/|\alpha|\), including the degree-one case. Thus the finite-sum formula follows exactly.

All coefficients, masses, and degree factors are rational, so every limit is rational.

6. Exact algorithm and bit complexity

The algorithm implements the formula correctly. A monomial spanning multiple components contributes to no role; a monomial supported in one component contributes precisely to its roles with positive exponents. Division by \(\mu_t\) is legitimate.

The operation count
\[ O\bigl(m^2+q(m+d)\bigr) \]
covers component computation, support inspection, repeated multiplication for powers, and accumulation of contributions. Unary exponent encoding gives \(d\leq L\), and the explicit list gives \(q\leq L\).

The common-denominator claim is correct. In the final summand, the total mass exponent is \(|\alpha|-1\leq d-1\), so its mass denominator divides \(Q^d\). Its coefficient denominator divides \(D_c\), and \(|\alpha|\) divides \(d!\). Thus every summand denominator divides
\[ D=D_cQ^dd!. \]

The stated bit-length bound follows from the total input lengths of the denominators and the bound on \(d!\). The numerator bound also holds: each summand has absolute value at most \(|c_\alpha|\), and accumulation introduces only polynomially many such terms.

Reduced intermediate fractions have \(O(B)\)-bit integers. Products used for individual monomials, final summands, and partial sums all satisfy polynomial denominator and magnitude bounds. Temporary integers in a single rational operation remain of this order as well. The conservative \(O(B^3)\) arithmetic bound therefore supports
\[ O\bigl((m^2+L(m+d))B^3\bigr), \qquad B=1+L(d+1)+d\log(d+1). \]
Substitution of \(m=\tau\) and the total output-length bound are valid.

The zero-polynomial case is explicitly handled. The proof supplies an exact polynomial-time classification without relying on the cited discrete enumeration results.

7. Consequence and example

Dependence on \(H\) only through its component partition follows directly from the proved formula.

For the path \(r-b-s\) and \(g(x)=x_rx_s\), the reported values
\[ a_r=\frac{\mu_s}{2}, \qquad a_s=\frac{\mu_r}{2}, \qquad a_b=0 \]
are correct.

Required clarification or repair: none.

⟨structured verdict parsed — rendered above⟩