Answer: \(D\) exists for every admissible input; exact computation and deciding \(D\ge q\) are polynomial-time solvable for every fixed \(K\).
Theorem 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateLet G be a configuration, G = {g1, . . . , gi, ..., g|G|}. Let AV GG be the average of all coalition structures in F −1[{G}] and avggi be the average of all coalitions in CLgi, for every 1 ≤i ≤|G|. Then the following holds: AV GG = gi∈G avggi The Anytime Optimal Algorithm Having described our representation, we now focus on how to search it. Here, we describe the two main steps of the algorithm.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational type masses \(\mu_t\), a fixed maximum team size \(K\), team-size densities \(\rho_g\), and values \(w_g(a)\) for teams with type-count vector \(a\), compute the limiting average total coalition value per agent over uniformly chosen partitions with those team-size densities.
A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_t\), normalized by \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Fix a maximum team size \(K\ge1\). Input team densities \(\rho_g\in\mathbb{Q}_{\ge0}\), for \(1\le g\le K\), count teams per agent and satisfy \(\sum_{g=1}^K g\rho_g=1\).
For every \(a\in\mathbb{Z}_{\ge0}^{T}\) with \(\sum_t a_t=g\le K\) and \(g\ge1\), an explicit table gives a binary rational value \(w_g(a)\ge0\). Let \(m\) be the number of table entries and \(L\) the total input bit length.
For each positive integer \(n\) making all \(n\mu_t\) and \(n\rho_g\) integers, take \(n\) distinct labeled agents, with \(n\mu_t\) agents of type \(t\). Choose \(\Pi_n\) uniformly among unordered set partitions having exactly \(n\rho_g\) nonempty teams of size \(g\); every agent belongs to exactly one team.
Write \(a(C)\) for the type-count vector of team \(C\), and define the limiting average value per agent by \(D=\lim_{n\to\infty}\frac{1}{n}\mathbb{E}[\sum_{C\in\Pi_n}w_{|C|}(a(C))]\), along those admissible integers.
Does \(D\) exist for every admissible input, and is its exact computation polynomial-time solvable in \(m,\tau,L\) for every fixed \(K\), or is deciding \(D\ge q\), for an input binary rational threshold \(q\), NP-hard for some fixed \(K\)?
Discrete: for any prescribed multiset of team sizes, the uniform average total partition value equals the sum, with multiplicities, of the average coalition values at those sizes. [Verified source](https://cdn.aaai.org/AAAI/2007/AAAI07-188.pdf).
Continuous: no result settling this exact limiting computation was located in the search.
The limit exists for every admissible input, and its exact computation is polynomial-time solvable for every fixed \(K\). Explicitly,
\[ D=\sum_{g=1}^{K}\rho_g \sum_{\substack{a\in\mathbb Z_{\ge0}^{T}\\ \sum_t a_t=g}} w_g(a)\frac{g!}{\prod_{t\in T}a_t!} \prod_{t\in T}\mu_t^{a_t}. \]
Thus deciding \(D\ge q\) is also polynomial-time solvable for every fixed \(K\).
All masses and densities are rational. Let \(d\) be the least common multiple of their denominators. Every positive multiple \(n\) of \(d\) is admissible, so admissible integers are unbounded.
Fix an admissible \(n\), and write \(N_t=n\mu_t\) and \(b_g=n\rho_g\). These are nonnegative integers, and
\[ \sum_{t\in T}N_t=n, \qquad \sum_{g=1}^{K}g b_g=n. \]
Consequently, the labeled agents can be partitioned into \(b_g\) teams of size \(g\): arrange the agents in any order and divide them into blocks of the prescribed sizes. The set on which the uniform distribution is defined is therefore nonempty.
Types impose no restriction on which partitions are allowed; they determine only the values assigned to their teams.
Take an admissible \(n\ge K\). For any subset \(S\) of the labeled agents, let \(I_S\) be the indicator that \(S\) is a team in \(\Pi_n\).
For a fixed size \(g\), every subset \(S\) of size \(g\) has the same inclusion probability. Indeed, any permutation of agent labels bijects the allowed partitions with themselves, preserves their uniform distribution, and can map any such subset to any other.
Every allowed partition has exactly \(b_g\) teams of size \(g\). Hence
\[ \sum_{|S|=g}I_S=b_g, \qquad \mathbb P(I_S=1)=\frac{b_g}{\binom ng}. \]
By linearity of expectation,
\[ \frac1n\mathbb E\!\left[ \sum_{C\in\Pi_n}w_{|C|}(a(C)) \right] = \sum_{g=1}^{K}\rho_g \frac1{\binom ng} \sum_{|S|=g}w_g(a(S)). \]
This argument applies directly to unordered partitions. It also proves, in this setting, the discrete averaging identity stated in Theorem 1 of the supplied [Rahwan et al. paper](https://cdn.aaai.org/AAAI/2007/AAAI07-188.pdf).
Define
\[ A_g=\left\{a\in\mathbb Z_{\ge0}^{T}:\sum_{t\in T}a_t=g\right\}. \]
For \(a\in A_g\), the number of subsets with type-count vector \(a\) is \(\prod_{t\in T}\binom{N_t}{a_t}\). Here \(\binom{N_t}{a_t}=0\) when \(a_t>N_t\). Grouping the subsets by their type counts gives the exact identity
\[ \frac1n\mathbb E\!\left[ \sum_{C\in\Pi_n}w_{|C|}(a(C)) \right] = \sum_{g=1}^{K}\rho_g \sum_{a\in A_g} w_g(a) \frac{\prod_{t\in T}\binom{n\mu_t}{a_t}}{\binom ng}. \tag{1} \]
No independence between teams is needed.
For a nonnegative integer \(r\), define the falling factorial by \((x)_0=1\) and \((x)_r=\prod_{j=0}^{r-1}(x-j)\).
For each fixed \(g\) and \(a\in A_g\),
\[ \frac{\prod_t\binom{n\mu_t}{a_t}}{\binom ng} = \frac{g!}{\prod_t a_t!} \frac{\prod_t(n\mu_t)_{a_t}}{(n)_g}. \]
Because \(\sum_t a_t=g\), dividing the numerator and denominator of the last fraction by \(n^g\) yields
\[ \frac{\prod_t(n\mu_t)_{a_t}}{(n)_g} = \frac{ \prod_{t\in T}\prod_{j=0}^{a_t-1}(\mu_t-j/n) }{ \prod_{j=0}^{g-1}(1-j/n) } \longrightarrow \prod_{t\in T}\mu_t^{a_t}. \]
The denominator converges to \(1\), and every product has finitely many factors. For the fixed input, the sums in (1) also have finitely many terms. Taking their limits term by term proves the asserted formula for \(D\), along all admissible integers.
The coefficient
\[ \frac{g!}{\prod_t a_t!}\prod_t\mu_t^{a_t} \]
is the multinomial probability of type-count vector \(a\) in \(g\) independent draws from the type distribution. Thus the limiting contribution of size \(g\) is its team density multiplied by its multinomial average value.
It remains to verify that evaluating the formula takes polynomial bit time.
Write the input rationals with integer numerators and positive integer denominators:
\[ \mu_t=\frac{u_t}{v_t}, \qquad \rho_g=\frac{r_g}{s_g}, \qquad w_g(a)=\frac{x_{g,a}}{y_{g,a}}. \]
Set
\[ B_\mu=\prod_{t\in T}v_t, \qquad B_\rho=\prod_{g=1}^{K}s_g, \qquad B_w=\prod_{g=1}^{K}\prod_{a\in A_g}y_{g,a}, \qquad Q=B_\mu^K B_\rho B_w. \]
Each summand in the formula for \(D\) has an integer numerator over the denominator
\[ s_g y_{g,a}\prod_t v_t^{a_t}, \]
since \(g!/\prod_t a_t!\) is an integer. This denominator divides \(Q\): each exponent \(a_t\) is at most \(K\). Therefore \(D=P/Q\) for a nonnegative integer \(P\).
The sum of the binary lengths of the input denominators is at most \(L\). Consequently, \(Q\) has bit length \(O(KL)\), which is \(O(L)\) for fixed \(K\).
The numerator also has polynomial length. Let \(W=\max_{g,a}w_g(a)\). The multinomial theorem and \(\sum_t\mu_t=1\) give
\[ \sum_{a\in A_g} \frac{g!}{\prod_t a_t!}\prod_t\mu_t^{a_t}=1. \]
Moreover, \(\sum_g\rho_g\le\sum_g g\rho_g=1\). Hence
\[ 0\le D\le W, \qquad 0\le P=QD\le QW. \]
Because \(W\) is an input rational, its magnitude is at most \(2^L\). Thus \(P\) also has bit length \(O(KL+L)\). All partial sums after scaling by \(Q\) satisfy the same bound, because the summands are nonnegative.
An exact algorithm now proceeds as follows:
Scanning dense type-count vectors takes \(O(m\tau)\) elementary steps. All arithmetic operands have polynomial bit length, and integer arithmetic and greatest common divisor computation take polynomial time. This proves exact polynomial-time computability in \(m,\tau,L\) for every fixed \(K\).
Finally, write the threshold as \(q=h/j\), with \(j>0\). Comparing \(D\ge q\) is exactly the integer comparison \(Pj\ge hQ\), which also takes polynomial time.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The finite-population expectation, passage to the limit, and exact polynomial-time algorithm are all justified. I found no major or minor issues requiring repair.
The least common multiple of the input denominators is a positive integer, and every positive multiple makes all population counts and team counts integral. Thus the admissible integers are unbounded.
For an admissible \(n\), the identities \(\sum_t N_t=n\) and \(\sum_g g b_g=n\) follow directly from the input normalizations. Dividing an ordering of the labeled agents into the prescribed blocks constructs a valid partition. Types impose no feasibility restrictions, so the uniform distribution is well-defined.
The symmetry argument is valid even though agents have different types: allowed partitions are constrained only by team sizes. A permutation of labels therefore bijects the allowed partition set with itself and preserves its uniform distribution.
For each \(g\), this action is transitive on subsets of size \(g\), so their inclusion probabilities agree. Taking expectations in \(\sum_{|S|=g}I_S=b_g\) gives exactly
\(\mathbb P(I_S=1)=b_g/\binom ng\).
The restriction \(n\ge K\) ensures that all denominators are positive. Discarding the finitely many smaller admissible populations does not affect the limit.
Every team's value depends only on its subset of agents. Consequently, expressing the total as a sum of subset indicators and applying linearity of expectation yields the displayed coalition-average identity. No independence assumption is introduced.
For a specified vector \(a\), independently choosing \(a_t\) agents from each disjoint type class counts every corresponding subset exactly once. Thus the count \(\prod_t\binom{N_t}{a_t}\) is correct, including zero when a required count exceeds the available population. Equation (1) follows.
The citation is accurate: Theorem 1 of the [supplied Rahwan et al. paper](https://cdn.aaai.org/AAAI/2007/AAAI07-188.pdf) states that the average partition value for a fixed multiset of coalition sizes equals the sum of the coalition averages at those sizes, with multiplicities. Its hypotheses match the partition model here. The prover also establishes the needed identity independently.
The falling-factorial conversion of the binomial ratio is exact for the admissible integer counts. The convention \((x)_0=1\) correctly handles zero coordinates.
Since \(\sum_t a_t=g\), dividing by \(n^g\) gives precisely the displayed product ratio. Its numerator converges to \(\prod_t\mu_t^{a_t}\), while its denominator converges to \(1\). There are finitely many factors for each term.
For a fixed input, the outer and inner sums are finite. Termwise convergence therefore proves existence of the limit along all admissible integers and establishes the stated formula for \(D\). The argument does not require uniform convergence over different inputs.
The multinomial coefficient \(g!/\prod_t a_t!\) is an integer. Hence the stated denominator of each summand is valid without requiring cancellation.
For every coordinate, \(a_t\le K\), so \(\prod_t v_t^{a_t}\) divides \(B_\mu^K\). Also, \(s_g\) divides \(B_\rho\), and \(y_{g,a}\) divides \(B_w\). These facts establish divisibility by \(Q\), including when denominators share prime factors.
Thus scaling every summand by \(Q\) yields a nonnegative integer, and their sum gives the asserted representation \(D=P/Q\).
The bound on \(Q\) follows from summing the binary lengths of the input denominators and multiplying the mass contribution by \(K\). Its bit length is \(O(KL)\).
The multinomial identity is applied with the required hypothesis \(\sum_t\mu_t=1\). Each size-specific probability sum equals \(1\). Since the densities are nonnegative and \(\sum_g\rho_g\le1\), the bound \(0\le D\le W\) follows.
An input rational with positive integer denominator has magnitude at most \(2^L\). Therefore \(P\le QW\) has the claimed polynomial bit length. Nonnegativity also bounds every partial sum by the final numerator.
The algorithm processes the explicit table rather than an implicitly represented larger domain. For fixed \(K\), the listed powers, factorials, term products, and exact divisions involve polynomially many operations on integers of polynomial bit length. Dense vector scanning costs \(O(m\tau)\) coordinate operations. Standard integer arithmetic and greatest common divisor algorithms consequently give polynomial bit time.
Since \(Q>0\) and \(j>0\), comparing \(Pj\) with \(hQ\) is exactly equivalent to \(D\ge q\), including negative thresholds. Its running time is polynomial in the input and threshold encoding lengths.
Zero densities, zero values, a single supported type, and \(K=1\) are all covered by the written argument. No additional case or clarification is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.