PaperlayerView exact revision on arXiv

Source-linked AI summary

An Anytime Algorithm for Optimal Coalition Structure Generation

Talal Rahwan, Sarvapali Dyanand Ramchurn, Nicholas Robert Jennings, Andrea Giovannucci

arXiv:1401.3466v1cs.MAcs.AI

TL;DR

Coalition structure generation must maximize social welfare over an exponentially large set of agent partitions, limiting existing algorithms. The paper develops an anytime integer-partition algorithm that bounds and prunes sub-spaces while efficiently enumerating valid structures. IP finds optimal solutions much faster than IDP and provides strong quality guarantees when interrupted.

  • Problem

    Coalition structure generation requires finding a welfare-maximizing partition despite an exponentially growing solution space and limitations in execution time, solution quality, and memory.

  • Method

    IP partitions coalition structures by integer-based coalition-size patterns, computes sub-space bounds for pruning, and uses efficient branch-and-bound enumeration.

  • Results

    IP required 0.175% of IDP’s time to find an optimal solution for 27 agents and usually returned interrupted solutions above 95% of optimum with worst-case guarantees above 90%.

  • Takeaways & Limitations

    The anytime design provides progressively better, quality-guaranteed solutions and can avoid searching most of the coalition-structure space.

  • Takeaways & Limitations

    Integer-programming approaches can require huge memory and may be applicable only to small numbers of agents.

Abstract

from arXiv · show

Coalition formation is a fundamental type of interaction that involves the creation of coherent groupings of distinct, autonomous, agents in order to efficiently achieve their individual or collective goals. Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining which of the many possible coalitions to form in order to achieve some goal. This usually requires calculating a value for every possible coalition, known as the coalition value, which indicates how beneficial that coalition would be if it was formed. Once these values are calculated, the agents usually need to find a combination of coalitions, in which every agent belongs to exactly one coalition, and by which the overall outcome of the system is maximized. However, this coalition structure generation problem is extremely challenging due to the number of possible solutions that need to be examined, which grows exponentially with the number of agents involved. To date, therefore, many algorithms have been proposed to solve this problem using different techniques ranging from dynamic programming, to integer programming, to stochastic search all of which suffer from major limitations relating to execution time, solution quality, and memory requirements. With this in mind, we develop an anytime algorithm to solve the coalition structure generation problem. Specifically, the algorithm uses a novel representation of the search space, which partitions the space of possible solutions into sub-spaces such that it is possible to compute upper and lower bounds on the values of the best coalition structures in them. These bounds are then used to identify the sub-spaces that have no potential of containing the optimal solution so that they can be pruned. The algorithm, then, searches through the remaining sub-spaces very efficiently using a branch-and-bound technique to avoid examining all the solutions within the searched subspace(s). In this setting, we prove that our algorithm enumerates all coalition structures efficiently by avoiding redundant and invalid solutions automatically. Moreover, in order to effectively test our algorithm we develop a new type of input distribution which allows us to generate more reliable benchmarks compared to the input distributions previously used in the field. Given this new distribution, we show that for 27 agents our algorithm is able to find solutions that are optimal in 0.175% of the time required by the fastest available algorithm in the literature. The algorithm is anytime, and if interrupted before it would have normally terminated, it can still provide a solution that is guaranteed to be within a bound from the optimal one. Moreover, the guarantees we provide on the quality of the solution are significantly better than those provided by the previous state of the art algorithms designed for this purpose. For example, for the worst case distribution given 25 agents, our algorithm is able to find a 90% efficient solution in around 10% of time it takes to find the optimal solution.

1. Introduction

Coalition structure generation seeks a welfare-maximizing partition of agents, but its exponentially growing solution space makes existing approaches inefficient or impractical. The paper introduces an anytime integer-partition algorithm with bounded sub-space pruning, efficient enumeration, and stronger empirical performance guarantees.

  • Problem: Coalition structure generation partitions agents into exhaustive, disjoint coalitions to maximize social welfare after coalition values are calculated.Coalition values indicate the expected outcome of forming each coalition, while the optimal structure maximizes the combined welfare.
  • Problem: Existing coalition structure generation algorithms use dynamic programming, integer programming, and stochastic search but face execution-time, solution-quality, or memory limitations.The problem of finding an optimal coalition structure is NP-complete, and the number of possible solutions grows exponentially with the number of agents.
  • Approach: The new representation groups coalition structures into disjoint sub-spaces by coalition sizes, enabling average values and upper and lower bounds to be computed for each sub-space.These bounds support pruning and expose the trade-off between sub-space size and potential improvement to the current solution.
  • Approach: IP is an anytime, integer-partition based algorithm that returns an optimal solution upon completion while providing quickly improving, bounded solutions if interrupted.Its branch-and-bound search reduces the amount of search, and its enumeration avoids redundant and invalid coalition structures.
  • Evaluation: 0.175% of IDP’s time was sufficient for IP to find an optimal solution with 27 agents.The comparison uses Improved Dynamic Programming, the fastest algorithm identified as guaranteed to return an optimal solution.
  • Evaluation: IP usually guaranteed at least 40% of the optimum immediately after scanning the input, and found solutions above 90% of optimum after searching around 0.0000002% of the space.Previous anytime algorithms were reported to guarantee solutions above 50% of optimum only after searching the whole space.

2. Related Work

Prior coalition structure generation methods trade off exactness, anytime guarantees, computational cost, memory, or solution quality. The paper positions its approach as meeting the stated design objectives through a more effective search-space representation.

  • Previous CSG algorithms are classified as exact methods using heuristics, integer programming, or dynamic programming, and non-exact methods using genetic algorithms or restricted search spaces.
  • 2.1.1 DYNAMIC PROGRAMMING: Dynamic programming finds optimal coalition structures in O(3^n) time but does not generate solutions anytime and requires three memory tables with 2^n entries each.
  • 2.1.1 DYNAMIC PROGRAMMING: Improved Dynamic Programming reduces operations and memory relative to DP, but still does not return solutions anytime.
  • 2.1.2 ANYTIME ALGORITHMS WITH WORST CASE GUARANTEES: Anytime graph-search algorithms provide worst-case quality guarantees, but their bounds can remain weak and become optimal only after searching the entire space.For 24 agents, one method guarantees only 25% of the optimum after searching 22,384,498,067,085 additional coalition structures.
  • 2.1.2 ANYTIME ALGORITHMS WITH WORST CASE GUARANTEES: Integer programming uses linear relaxation and branch-and-bound, but its huge memory requirement limits applicability to small numbers of agents.
  • 2.2 Non-Exact Algorithms for Coalition Structure Generation: Restricted-search methods can support overlapping coalitions and bounded solutions, but their guarantees may concern only the best combination of permitted coalitions rather than the unrestricted optimum.
  • The paper claims its algorithm meets the CSG design objectives, using a novel search-space representation intended to avoid exhaustive exploration when certifying optimality.

3. Search Space Representation

The paper represents coalition-structure search as independent sub-spaces grouped by integer partitions, enabling bounds on each sub-space and pruning of those unable to contain the optimum. This representation supports an anytime branch-and-bound search that avoids redundant and invalid solutions.

  • 3.2 Bounding Sub-spaces: Upper and lower bounds on each sub-space’s best coalition structure support quality guarantees and identify sub-spaces that can be pruned.The upper bound is based on maximum coalition values, while minimum and average values provide lower-bound constructions.
  • 3.1 Partitioning the Search Space: The representation partitions coalition structures into smaller independent sub-spaces according to integer partitions of the number of agents.For n = 4, the partitions are [4], [3, 1], [2, 2], [2, 1, 1], and [1, 1, 1, 1].
  • 3.1 Partitioning the Search Space: 1575 integer partitions versus nearly 4.4 × 10^17 coalition structures for 24 agents illustrates the representation’s compactness.The same example has 16,777,215 possible coalitions.
  • 3.1 Partitioning the Search Space: Each sub-space is the pre-image of an integer partition, and levels group sub-spaces by the number of partition parts.Level P_i contains sub-spaces whose corresponding integer partitions have i parts.
  • 3.2 Bounding Sub-spaces: Cartesian products of coalition lists contain invalid overlapping combinations, but the represented coalition-structure sub-space is a subset of these products.Consequently, MAX_G remains an upper bound despite invalid elements in T_G.
  • 3. Search Space Representation: The representation is used by an anytime algorithm that searches remaining sub-spaces with branch-and-bound until an optimal coalition structure is found.The search avoids examining every solution within searched sub-spaces and is intended to enumerate coalition structures without redundant or invalid solutions.

4. Solving the Coalition Structure Generation Problem

The IP algorithm solves coalition structure generation by scanning coalition-value lists, computing bounds, pruning sub-spaces, and searching the remainder without redundant or invalid structures. Its representation also supports anytime quality guarantees and preference-directed search.

  • IP computes coalition-structure bounds while scanning the input, then finds initial solutions, prunes sub-spaces, and establishes a worst-case quality bound.The algorithm’s two main stages are scanning the input and searching the remaining sub-spaces.
  • Scanning the Input: The input stores coalition values in lexicographically ordered lists v(Ls), avoiding the need to keep the coalitions themselves in memory.The list v(Ls) contains values for coalitions of size s.
  • Scanning the Input: The scan begins with the grand coalition and singleton coalitions, then processes two-coalition sub-spaces using complementary positions in the ordered lists.Complementary coalitions are diametrically positioned, allowing their values to be combined during scanning.
  • Scanning the Input: The scanning process is linear in the input size, O(y) where y = 2^n − 1.The scan also computes maximum and average coalition values for relevant coalition sizes.
  • Selecting a Sub-space: The representation lets IP select sub-spaces using bounds, prune those unable to improve the current solution, and direct search toward coalition structures matching resource or task preferences.It can express constraints such as a required number of coalitions or a maximum coalition size.
  • Searching a Sub-space: MCP generates every coalition structure in a sub-space, while FCP generates every structure exactly once without comparisons between coalitions.These properties are stated by Theorems 3 and 4, respectively.

5. Performance Evaluation

The evaluation tests IP across multiple coalition-value distributions, including the proposed NDCS distribution, and compares it with IDP and prior anytime algorithms. IP finds optimal solutions faster than IDP and provides strong anytime quality guarantees, although benchmark distributions can bias search performance.

  • 5.1 Benchmarking: Normal and Uniform benchmarks favor coalition structures with fewer coalitions, potentially favoring some algorithms over others.The paper therefore questions their validity and introduces NDCS as a distribution tailored to coalition structure generation.
  • 5.1 Benchmarking: NDCS makes search more demanding because it removes distributional bias by drawing every coalition-structure value from the same distribution.This more strongly tests the efficiency of search algorithms than biased distributions, according to the paper.
  • 5.2 Experiment 1: Optimality: The evaluation compares IP with IDP across Normal, Uniform, and the proposed NDCS distributions, using agent counts from 15 to 27.Running times are measured in milliseconds and plotted on a logarithmic scale.
  • 5.2 Experiment 1: Optimality: 570 times faster than IDP is IP’s best reported result, achieved on the Uniform distribution with 27 agents.This corresponds to taking 0.175% of IDP’s running time; the worst reported case is 1.7 times faster on NDCS with 16 agents.
  • 5.3 Experiment 2: Anytime Quality: For NDCS, Normal, and Uniform, IP reaches over-90% guarantees in less than half, less than 10%, and 15% of optimal-search time, respectively.Uniform produces near-optimal guarantees above 99% within 15% of the time needed to find the optimum.
  • 5.3 Experiment 2: Anytime Quality: IP’s anytime guarantees exceed prior algorithms: after scanning the input, it guarantees nearly 40% of optimal in the worst case versus below 10% for the others.For the hardest distribution, guarantees reach 100% after searching about 0.0000019% of the space, while over-90% solutions require about 0.0000002%.

6. Conclusions and Future Work

The paper concludes that IP combines integer-partition search-space representation, valid-only cyclation, and branch-and-bound pruning to solve coalition structure generation efficiently while providing strong anytime guarantees.

  • IP partitions the search space into disjoint sub-spaces, computes bounds, and prunes regions that cannot contain an optimal solution.The representation can also yield the optimum almost immediately after scanning the input, depending on the input distribution.
  • IP’s cyclation technique generates only valid coalition structures, avoids duplicate generation, and applies branch-and-bound to skip structures that cannot improve the current solution.This avoids searching the exponentially larger space of possible coalition combinations.
  • 0.175% of IDP’s time was required by IP to find an optimal solution for 27 agents in the best case.The experiments report that IP avoids searching most of the search space.
  • Above 90% of the optimal solution was guaranteed within 10% of the time needed to find the optimum for 25 agents.Interrupted runs usually returned solutions above 95% of optimal with worst-case guarantees usually above 90%.
  • After scanning the input, IP guaranteed solutions above 40% of optimal, compared with less than 10% for Sandholm et al.’s and Dang and Jennings’s algorithms.The comparison concerns worst-case guarantees across the evaluated distributions.

Appendix A. Summary of Notation

The notation defines the agents, coalitions, coalition structures, value bounds, search-space components, distributions, and solution-quality ratios used throughout the paper.

  • A is the set of agents, n its cardinality, C a coalition, v(C) its value, CS a coalition structure, and V(CS) its value.
  • CS∗ denotes an optimal coalition structure, while UB∗ and LB∗ are upper and lower bounds on its value.
  • CS′ is the best coalition structure found so far, β bounds its quality, and β∗ specifies the acceptable solution-quality bound.
  • P is the set of possible coalition structures, Pi is the ith representation level, and Ls lists coalitions of size s lexicographically.
  • G identifies coalition-size partitions, TG their Cartesian-product coalitions, PG the corresponding sub-space, and F maps coalition structures to partitions.
  • N(µ, σ2), U(a, b), ropt, and rbound denote the Normal and Uniform distributions and ratios to the optimum and its upper bound.

Appendix B. Proof of Theorem 1.

The proof counts ordered coalition structures by selecting coalitions position by position, then accounts for repeated coalition sizes to relate ordered and unordered representations.

  • For Ḡ = [g1, g2, …, g|G|], P_Ḡ contains ordered coalition structures whose coalition sizes follow the natural ordering of G.
  • Each coalition C in Lgi appears in the ith position across Nn−gi structures formed from the remaining coalition sizes.
  • The number of ordered structures satisfies Nn(g1, …, g|G|) = |Lgi| × Nn−gi(g1, …, gi−1, gi+1, …, g|G|).
  • The average value over ordered structures is computed by weighting coalition values according to their occurrences in each position.
  • When a coalition size occurs x times, each coalition structure is repeated x! times in the ordered representation.

Appendix C. Proof of Theorem 2.

The proof counts non-overlapping coalition combinations through successive choices and then removes multiplicities caused by ordering coalitions of equal sizes.

  • For a set of remaining agents, the number of size-s combinations is the corresponding binomial coefficient.
  • After choosing a coalition of size g1, the number of disjoint coalitions of size g2 is Cn−g1 g2, with analogous successive counts for later sizes.
  • The subset T̂G contains only Cartesian-product elements whose coalitions do not overlap, allowing its size to be computed from successive disjoint choices.
  • Each coalition structure appears once in PG but x! times in T̂G when a coalition size gi has multiplicity x.
  • The proof uses the multiplicity function G(gi) to connect counts in T̂G with the underlying set of distinct coalition sizes.

Appendix D. Proof of Theorem 3.

The proof shows that MCP generates every coalition structure associated with an integer partition by constructing nonoverlapping ordered coalition sets and establishing nonempty correspondence.

  • MCP generates ordered coalition sets whose coalitions have prescribed sizes and do not overlap.Each coalition belongs to the list associated with its partition part.
  • For any coalition structure CS in PG, the proof defines ordered sets corresponding to CS within MCP’s generated space.
  • At least one valid ordering of the coalitions in CS has nondecreasing coalition sizes.
  • |T̂_CS^G| ≥ 1, implying that every coalition structure in PG is generated by MCP.

Appendix E. Proof of Theorem 4.

The proof establishes that FCP generates every coalition structure in PG exactly once, while avoiding duplicate ordered sets that MCP may generate when coalition sizes repeat.

  • FCP generates ordered coalition sets corresponding to coalition structures under the prescribed nondecreasing size order.
  • When all coalition sizes are unique, FCP and MCP generate the same ordered sets, yielding one representation per coalition structure.
  • When a coalition size has multiplicity greater than one, MCP generates multiple permutations of equal-sized coalitions, whereas FCP avoids redundant permutations.
  • FCP retains exactly one permutation among equal-sized coalitions by ordering their smallest agents increasingly.
  • |T̃_CS^G| = 1 for all CS ∈ PG, proving that FCP generates every coalition structure in PG exactly once.

Appendix F. Proof of Theorem 5

For coalition values drawn from size-scaled normal distributions, the proof shows that merging coalitions increases variance and makes high coalition-structure values more likely; the uniform case follows analogous high-value intuition.

  • The normal-distribution proof compares a structure with multiple coalitions against one formed by merging them into a single coalition.
  • For normal variables with equal means, the variable with larger variance has a greater probability of exceeding any threshold r.
  • |C_x|^2 > |C_x1|^2 + ··· + |C_xα|^2, so merging coalitions increases the variance of the corresponding coalition value.
  • The merged coalition structure is more likely to have a value greater than r and therefore more likely to be optimal.
  • For the uniform case, the proof intuition similarly states that the merged coalition has a lower probability of falling below high values r.

Appendix G. Proof of Theorem 6.

The proof sets up independence and distributional assumptions for coalition values before deriving the theorem’s final relation.

  • The proof requires coalition structures’ values to be independently drawn from the same normal distribution.
  • It invokes the normal-distribution rule for sums of independent random variables with specified means and variances.
  • The argument applies this rule to pairs of coalition values because they are independent random variables.
Loading 1401.3466v1…