Report

Computational Coalition Formation Talal Rahwan (University of Southampton, UK) What is an Agent? Hello… I am an intelligent entity…. I am situated in a an environment… I can perceive the environment I have goals… I have a list of available actions… I act autonomously to satisfy my goals and… most importantly… I am social !!! Organizations in Multi-Agent Systems Hierarchies Compounds Markets Teams Coalitions MatrixControl Organizations Holarchies Congregations Federations Societies Data Organizations in Multi-Agent Systems Hierarchies Compounds Markets Teams Coalitions Matrix Organizations Holarchies Congregations Federations Societies seller buyer Organizations in Multi-Agent Systems Hierarchies Compounds Markets Teams Coalitions Matrix Organizations Holarchies Congregations Federations Societies Coalition Formation Main characteristicis Coalitions in general are goal-directed and short-lived No coordination among members of different coalitions The organizational structure within each coalition is flat Applications of Coalition Formation Smart Energy Grids Intelligent appliances and energy storage devices coordinate for optimal energy use Electronic-commerce Cooperation among buyers to obtain quantity discounts, and sellers to maintain cartel pricing. Disaster Management UN report said: "Efforts by the United Nations in Haiti have lacked sufficient coordination“ Applications of Coalition Formation Distributed sensor networks: Coalitions of sensors can work together to track targets of interest [Dang et al. 2006] Distributed vehicle routing: Coalitions of delivery companies can be formed to reduce the transportation costs by sharing deliveries [Sandholm and Lesser, 1997]. Information gathering: Several information servers can form coalitions to answer queries [Klusch and Shehory, 1996]. Cooperative Game Theory Game theory studies interactions between agents in situations known as games Coalition Formation is studied in a field of Game theory, called Cooperative Game Theory In cooperative game, agents benefit from cooperation, but is that all that makes a game a cooperative one? Example: the Prisoner’s Dilemma • Two agents committed a crime. • Court does not have enough evidence to convict them of the crime, but can convict them of a minor offence (1 year in prison each) • If one suspect confesses (acts as an informer), he walks free, and the other suspect gets 4 years • If both confess, each gets 3 years • Agents have no way of communicating or making binding agreements Prisoners’ Dilemma: Matrix Representation a2 quiet confess quiet (-1,-1) (-4, 0) confess (0, -4) (-3, -3) a1 • Interpretation: the pair (x, y) at the intersection of row i and column j means that the row player gets x and the column player gets y Prisoners’ Dilemma: the Rational Outcome • a1’s reasoning: – if a2 stays quiet, I should confess – if a2 confesses, I should confess, too • • • • a1 a 2 Quite Confess Quite (-1,-1) Confess (-4, 0) (0, -4) (-3, -3) a2 reasons in the same way Result: both confess and get 3 years in prison. But: they could have got only 1 year each! So why do not they cooperate? Cooperative vs. Non-Cooperative Games • In Non-Cooperation games, players cannot make binding agreements • But what if binding agreements are possible? • Cooperative games model scenarios, where – agents can benefit by cooperating – binding agreements are possible Cooperative Games Does a coalition influence other co-existing coalitions? Cooperative Game Can a player transfer part of its utility to another? Partition Function Game (PFG) Characteristic Function Game (CFG) Transferable Utility (TU) Game Non-Transferable Utility (NTU) Game Example: Writing Papers • n researchers working at n different universities can form groups to write papers • the composition of a group determines the quality of the paper they produce • each author receives a payoff from his own university: – promotion – bonus – teaching load reduction • TU or NTU? NTU (payoffs are non-transferable) • CFG or PFG? CFG (a group does not influence others) Example: Growing Fruits • n farmers can cooperate to grow fruit • Each group grows apples or oranges • a group of size k can grow f(k) tons of apples, or g(k) tons of oranges, where f() and g() are convex functions of k • The market price of a fruit drops monotonically as the number of tons available in the market increases • TU or NTU? TU (money is transferable) • CFG or PFG? PFG (a group can influence another) Example: Buying Ice-cream • n children, each has some money: • Supermarkets sells many ice-cream tubs, in different sizes: – Type 1 contains 500g, costs $7 – Type 2 contains 750g, costs $9 – Type 3 contains 1kg, costs $11 • children have utility for ice-cream, and don‘t care about money • The payoff of a group is the maximum amount of ice-cream the members of the group can buy by pooling their money • TU or NTU? TU (ice-cream is transferable) • CFG or PFG? CFG (many available tubs) How is a Cooperative Game Played? • Although agents work together, they can still be selfish • We need to: – Partition the agents into coalitions – Divide the payoff of each coalition among its members such that the outcome is stable (i.e., no player, or group of players, has an incentive to deviate) • We may also want to ensure that the outcome is fair • We will now see how to formalize these ideas Cooperative Games Does a coalition influence other co-existing coalitions? Cooperative Game Can a player transfer part of its utility to another? Partition Function Game (PFG) Characteristic Function Game (CFG) Transferable Utility (TU) Game Non-Transferable Utility (NTU) Game Focus of this talk Transferable Utility Games Formalized • A transferable utility game is a pair (A, v), where: – A ={a1, ..., an} is the set of players (or agents) – v: 2A → R is the characteristic function • for each C ⊆ A, v(C) is the value of C, i.e., the payoff that members of C can attain by working together – usually it is assumed that • v(Ø) = 0 • v(C) ≥ 0 for any C ⊆ A • v(C) ≤ v(D) for any C, D such that C ⊆ D • The biggest possible coalition (the one containing all agents) is called the grand coalition Ice-Cream Game: Characteristic Function C: $6, M: $4, P: $3 w = 500g w = 750g w = 1000g p = $7 p = $9 p = $11 • v(Ø) = v({C}) = v({M}) = v({P}) = 0 • v({C, M}) = 750, v({C, P}) = 750, v({M, P}) = 500 • v({C, M, P}) = 1000 Transferable Utility Games: Outcome An outcome of a TU game G =(A, v) is a pair (CS, x), where: • CS =(C1, ..., Ck) is a coalition structure, i.e., a partition of A into coalitions: – C1 ... Ck = A, – Ci Cj = Ø for i ≠ j • x = (x1, ..., xn) is a payoff vector, which specifies the payoff of each agent: – xi ≥ 0 for all ai A – S∶ xi = v(C) for all CCS Superadditive Games • Definition: a game G = (A, v) is called superadditive iff: v(C U D) ≥ v(C)+v(D) for any two disjoint coalitions C and D • Example: v(C) = |C|2: v(C U D) = (|C|+|D|)2 ≥ |C|2+|D|2 = v(C) + v(D) • In superadditive games, any two coalitions can always merge without losing money; hence, we can assume that players form the grand coalition Superadditive Games • In super-additive games, the grand coalition forms, so: Which coalition structure is optimal? How should we divide the payoffs? Non-Superadditive Game Grand coalition is always optimal ! Superadditive Game How to divide payoff of grand coalition ? What Is a Good Outcome? • • • • • C: $4, M: $3, P: $3 v(Ø) = v({C}) = v({M}) = v({P}) = 0 v({C, M}) = 500, v({C, P}) = 500, v({M, P}) = 0 v({C, M, P}) = 750 This is a superadditive game – outcomes are payoff vectors • How should the players share the ice-cream? – if they share as (200, 200, 350), Charlie and Marcie can get more ice-cream by buying a 500g tub on their own, and splitting it equally – the outcome (200, 200, 350) is not stable! Transferable Utility Games: Stability • Definition: the core of a game is the set of all stable outcomes, i.e., outcomes that no coalition wants to deviate from. That is: core(G) = {(CS, x) | S∶ xi ≥ v(C) for any C ⊆ A} • Note: G is not necessarily superadditive • Example: a2 a4 a 1 – v({a1, a2, a3}) = 9 a3 a5 – v({a4, a5}) = 4, – but if v({a2, a4}) = 7 ? – then (({a1, a2, a3}, {a4, a5}), (3, 3, 3, 3, 1)) is NOT in the core Ice-Cream Game: Core • C: $4, M: $3, P: $3 • v(Ø) = v({C}) = v({M}) = v({P}) = 0, v({C, M, P}) = 750 • v({C, M}) = 500, v({C, P}) = 500, v({M, P}) = 0 • (200, 200, 350) is not in the core: – v({C, M}) > xC + xM • (250, 250, 250) is in the core: – no subgroup of players can deviate so that each member of the subgroup gets more • (750, 0, 0) is also in the core: – Marcie and Pattie cannot get more on their own! Games with Empty Core • The core is a very attractive solution concept • However, some games have empty cores • G = (A, v) – – – – A = {a1, a2, a3}, v(C) = 1 if |C| > 1 and v(C) = 0 otherwise consider an outcome (CS, x) if CS = ({a1}, {a2}, {a3}), the grand coalition can deviate if CS = ({a1, a2}, {a3}), either a1 or a2 gets less than 1, so can deviate with a3 – same argument for CS = ({a1, a3}, {a2}) or CS = ({a2, a3}, {a1}) – suppose CS = {a1, a2, a3}: xi > 0 for some ai, so x(A\{ai}) < 1, yet v(A\{ai}) = 1 e-Core • If the core is empty, we may want to find approximately stable outcomes • Need to relax the notion of the core: core: (CS, x): x(C) ≥ v(C) for all C N e-core: (CS, x): x(C) ≥ v(C) - e for all C N • Is usually defined for superadditive games only • Example: G = (A, v), A = {a1, a2, a3}, v(C) = 1 if |C| > 1, v(C) = 0 otherwise – 1/3-core is non-empty: (1/3, 1/3, 1/3) 1/3-core – e-core is empty for any e < 1/3: xi ≥ 1/3 for some i = 1, 2, 3, so x(A\{ai}) ≤ 2/3, v(A\{ai}) = 1 What is a Good Outcome ? Given 3 agents, the set of agents is: A = {a1, a2, a3} The possible coalitions are: a1 a2 a3 a1 a2 a1 a3 a2 a3 a1 a2 a3 5 5 5 12 12 12 24 A solution of a coalitional game: STABILITY THE CORE STABILITY <? ? ?> Characteristic Function Games Given 3 agents, the set of agents is: N = {a1, a2, a3} The possible coalitions are: a1 a2 a3 a1 a2 a1 a3 a2 a3 5 5 5 12 12 12 A solution of a coalitional game: a2 : Wait! But it is not fair! STABILITY THE CORE Such division of payoff that no sub-coalition wants to deviate a1 : Great! I like this core division!` a1 a2 a3 24 <13 7 4> <10 7> a3 : My contribution to every coalition in the game is the same as a1 Characteristic Function Games Given 3 agents, the set of agents is: N = {a1, a2, a3} The possible coalitions are: a1 a2 a3 a1 a2 a1 a3 a2 a3 5 5 5 12 12 12 A solution of a coalitional game: Fairness criteria: FAIRNESS SHAPLEY VALUE A unique division of payoff That meets fairness criteria (axioms) a1 a2 a3 24 <8 <? ?8 ?> 8> Symmetry Null-player Additivity Efficiency Shapley Value – Definition a1 a2 a3 a1 a2 a3 a2 a1 a3 a2 a3 a1 a3 a1 a2 a3 a2 a1 a1 a2 a3 a1 a2 a1 a3 a2 a3 5 5 5 12 12 12 Shapley Value – Definition a1 a2 a3 a1 a2 a3 a2 a1 a3 a2 a3 a1 a3 a1 a2 a3 a2 a1 a1 a2 a3 a1 a2 a1 a3 a2 a3 5 5 5 12 12 12 Shapley Value – Definition MC(a1) 0 a1 a2 a3 +5 0 a1 a2 a3 +5 a2 a1 a3 +7 a2 a3 a1 a3 a1 a2 a3 a2 a1 +12 = 8 48/6 = Sh(a +7 1) +12 a1 a2 a3 a1 a2 a1 a3 a2 a3 5 5 5 12 12 12 Coalition Formation Process optimal? Coalition structure generation Value Value Payoff distribution Value Value Coalition Structure Generation (in Characteristic Function Games) Given 3 agents, the set of agents is: {a1,a2,a3} The possible coalitions are: {a1} 20 {a2} 40 {a3} 30 {a1,a2} 70 40 {a1,a3} {a2,a3} 65 95 {a1,a2,a3} The possible coalition structures: {{a1},{a2},{a3}} 20+40+30=90 {{a1,a2},{a3}} 70+30= 100 {{a2},{a1,a3}} 40+40= 80 {{a1},{a2,a3}} 20+65 = 85 {{a1,a2,a3}} 95 Input: a value of every possible coalition Output: a coalition structure in which the sum of values is maximized L1 value {1} {2} {3} {4} 30 40 25 45 value L2 {1, {1, {1, {2, {2, {3, 2} 3} 4} 3} 4} 4} 50 60 80 55 70 80 L3 {1, {1, {1, {2, 2, 2, 3, 3, 3} 4} 4} 4} Exercise What is the optimal coalition structure ? Answer { {1}, {2}, {3,4} } value L4 value 90 120 100 115 {1,2,3,4} 140 L1 value L2 value L3 value L4 value L5 value L6 value 826 1108 1065 890 907 1024 1750 1670 1989 1664 2023 2083 2272 2082 1995 1807 2529 2045 1683 2115 1956 1, 2, 3 1, 2, 4 1, 2, 5 1, 2, 6 1, 3, 4 1, 3, 5 1, 3, 6 1, 4, 5 1, 4, 6 1, 5, 6 2, 3, 4 2, 3, 5 2, 3, 6 2, 4, 5 2, 4, 6 2, 5, 6 3, 4, 5 3, 4, 6 3, 5, 6 4, 5, 6 3352 3102 3301 3119 3287 2696 2950 3324 2460 3134 2943 2956 2950 3661 2618 2906 2769 3070 3135 1, 2, 3, 4 1, 2, 3, 5 1, 2, 3, 6 1, 2, 4, 5 1, 2, 4, 6 1, 2, 5, 6 1, 3, 4, 5 1, 3, 4, 6 1, 3, 5, 6 1, 4, 5, 6 2, 3, 4, 5 2, 3, 4, 6 2, 3, 5, 6 2, 4, 5, 6 3, 4, 5, 6 4355 4373 3770 3528 3967 3647 4142 3875 3905 3645 3850 4099 3967 3318 3576 1, 2, 3, 4, 5 1, 2, 3, 4, 6 1, 2, 3, 5, 6 1, 2, 4, 5, 6 1, 3, 4, 5, 6 2, 3, 4, 5, 6 4804 5657 4609 4829 5650 5852 1,2, 3, 4, 5, 6 6217 1 2 3 4 5 6 1, 2 1, 3 1, 4 1, 5 1, 6 2, 3 2, 4 2, 5 2, 6 3, 4 3, 5 3, 6 4, 5 4, 6 5, 6 Exercise What is the optimal coalition structure ? Limit the permitted sizes, and use greedy algorithms (Shehory & Kraus 1999, 1996, 1995) Example: The set of possible coalitions of agents: A = {1, 2, 3, 4, 5, 6} CL 1 CL2 CL3 CL4 CL5 CL6 1 2 3 4 5 6 1,2 1,3 1,4 1,5 1,6 2,3 2,4 2,5 2,6 3,4 3,5 3,6 4,5 4,6 5,6 1,2,3 1,2,4 1,2,5 1,2,6 1,3,4 1,3,5 1,3,6 1,4,5 1,4,6 1,5,6 2,3,4 2,3,5 2,3,6 2,4,5 2,4,6 2,5,6 3,4,5 3,4,6 3,5,6 4,5,6 1,2,3,4 1,2,3,5 1,2,3,6 1,2,4,5 1,2,4,6 1,2,5,6 1,3,4,5 1,3,4,6 1,3,5,6 1,4,5,6 2,3,4,5 2,3,4,6 2,3,5,6 2,4,5,6 3,4,5,6 1,2,3,4,5 1,2,3,4,6 1,2,3,5,6 1,2,4,5,6 1,3,4,5,6 2,3,4,5,6 1, 2, 3, 4, 5, 6 Integer programming (IP) C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 C13 C14 C15 Z= 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 {1,2,4} {3} 2n The integer model: max Sv(ci) . xi s.t. Z . x = (1,…,1) xi {1,0} i=1 1 2 3 4 Order-based genetic algorithms (OBGA) (S. Sen & P. Dutta 2000) 1 7 6 3 8 4 2 5 9 { {1}, 2 5 7 1 4 3 9 8 6 { {2, 5}, {1, 4, 3} {3}, {4, 2, 5} } } GA consists of 3 steps: (1) Evalutation (2) Selection (3) Re-combination Samples 7 1 5 6 2 3 4 8 9 9 3 2 8 6 1 7 5 4 Parents Offspring 6 1 2 3 4 8 7 5 9 9 3 2 8 6 1 7 5 4 9 3 2 8 6 1 9 5 3 3 8 9 1 5 4 2 6 7 4 2 1 7 6 8 9 5 3 4 2 1 7 6 8 7 5 4 4 2 1 7 6 8 9 5 3 {{3, 2}, {1}, {5, 3}} 6 9 3 1 7 8 4 5 2 {{4, 2, 1}, {5, 4}} Related Work Dynamic Programming techniques IDP [Rahwan & Jennings N. R., An Improved Dynamic Programming Algorithm for Coalition Structure Generation, AAMAS 2008]. Anytime with guarantees on solution quality IP Property [Rahwan et al., An Anytime Algorithm for Optimal Coalition Structure Generation, AAAI 2007, JAIR 2009]. Algorithm IDP IP Worst case performance O(3n) O(nn) Return solutions anytime False True Time to return optimal solution Slow Fast The Dynamic Programming (DP) Algorithm Main observation: To find the optimal partition of a set of agents, it is sufficient to: • try the possible ways to split the set into two sets, and • For every half, find the optimal partition of that half. size coalition 1 2 3 4 Evaluations performed before setting f {1} {2} {3} {4} V({1})=30 V({2})=40 V({3})=25 V({4})=45 Best split f {1} {2} {3} {4} 30 40 25 45 {1,2} V({1,2})=50 f({1})+f({2})=70 {1} {2} 70 {1,3} V({1,3})=60 f({1})+f({3})=55 {1,3} 60 {1,4} V({1,4})=80 f({1})+f({4})=75 {1,4} 80 {2,3} V({2,3})=55 f({2})+f({3})=65 {2} {3} 65 {2,4} V({2,4})=70 f({2})+f({4})=85 {2} {4} 85 {3,4} V({3,4})=80 f({3})+f({4})=70 {3,4} 80 {2} {1,3} 100 {1,2,4} 120 {1,2,3} V({1,2,3})=90 f({2})+f({1,3})=100 {1,2,4} V({1,2,4})=120 f({1})+f({2,4})=115 f({2})+f({1,4})=110 f({4})+f({1,2})=115 f({1})+f({2,3})=95 f({3})+f({1,2})=95 {1,3,4} V({1,3,4})=100 f({3})+f({1,4})=105 f({1})+f({3,4})=110 f({4})+f({1,3})=105 {1} {3,4} 110 {2,3,4} V({2,3,4})=115 f({3})+f({2,4})=110 f({2})+f({3,4})=120 f({4})+f({2,3})=110 {2} {3,4} 120 {1,2,3,4} V({1,2,3,4})=140 f({2})+f({1,3,4})=150 f({4})+f({1,2,3})=145 f({1,3})+f({2,4})=145 f({1})+f({2,3,4})=150 f({3})+f({1,2,4})=145 f({1,2})+f({3,4})=150 f({1,4})+f({2,3})=145 {1,2} {3,4} 150 The Coalition Structure Graph {a1},{a2},{a3},{a4} V = 140 optimal {a1},{a2},{a3,a4} {a3},{a4},{a1,a2} {a1},{a3}},{a2,a4} {a2},{a4},{a1,a3} {a1},{a4},{a2,a3} {a2},{a3},{a1,a4} V = 150 V = 120 V = 125 V = 145 V = 130 V = 145 {a1},{a2,a3,a4} {a1,a2},{a3,a4} {a2},{a1,a3,a4} {a1,a3}},{a2,a4} {a3},{a1,a2,a4} {a1,a4},{a2,a3} {a4},{a1,a2,a3} V = 145 V = 130 V = 140 V = 130 V = 145 V = 135 V = 135 {a1,a2,a3,a4} V = 140 The Improved Dynamic Programming Algorithm (IDP) We define a subset of edges E* We prove that the edges in E* are sufficient to form a path to every node in the graph We modify the original algorithm such that it only evaluates the movements through the edges in E* The Coalition Structure Graph {a1},{a2},{a3},{a4} optimal {a1},{a2},{a3,a4} {a3},{a4},{a1,a2} {a1},{a3},{a2,a4} {a2},{a4},{a1,a3} {a1},{a4},{a2,a3} {a2},{a3},{a1,a4} {a1},{a2,a3,a4} {a1,a2},{a3,a4} {a2},{a1,a3,a4} {a1,a3},{a2,a4} {a3},{a1,a2,a4} {a1,a4},{a2,a3} {a4},{a1,a2,a3} {a1,a2,a3,a4} size Coalition 1 Evaluations performed before setting f Best split V({1})=50 V({2})=30 V({3})=45 V({4})=35 {1} {2} {3} {4} 50 30 45 {1} {2} {3} {4} 2 3 35 {1,2} V({1,2})=90 f({1})+f({2})=80 {1,2} 90 {1,3} V({1,3})=80 f({1})+f({3})=95 {1} {3} 95 {1,4} V({1,4})=65 f({1})+f({4})=85 {1} {4} 85 {2,3} V({2,3})=90 f({2})+f({3})=75 {2,3} 90 {2,4} V({2,4})=70 f({2})+f({4})=65 {2,4} 70 {3,4} V({3,4})=60 f({3})+f({4})=80 {3} {4} 80 {1} {2,3} 140 {1,2,3} {1,2,4} 4 f V({1,2,3})=125 f({2})+f({1,3})=125 V({1,2,4})=120 f({2})+f({1,4})=115 f({1})+f({2,3})=140 f({3})+f({1,2})=135 f({1})+f({2,4})=120 f({4})+f({1,2})=125 {1,2,3} {4} {1,2} {1,2,4} 125 125 120 {1,3,4} V({1,3,4})=135 f({3})+f({1,4})=130 f({1})+f({3,4})=130 f({4})+f({1,3})=130 {1,3,4} 135 {2,3,4} V({2,3,4})=115 f({2})+f({3,4})=110 {4} {2,3} 125 f({3})+f({2,4})=115 f({4})+f({2,3})=125 {2,3,4} {1,2,3,4} V({1,2,3,4})=160 f({2})+f({1,3,4})=160 f({4})+f({1,2,3})=175 f({1,3})+f({2,4})=165 f({1})+f({2,3,4})=175 f({3})+f({1,2,4})=170 f({1,2})+f({3,4})=170 f({1,4})+f({2,3})=175 {4} {1,4}{1,2,3} {2,3} 115 175 Evaluation of IDP The total number of evaluations performed by IDP is only 38.7% of those performed by the original dynamic programming (DP) algorithm Question How can we reduce the memory requirements ? size Coalition Evaluations performed before setting f Best split f V[{1}]=30 V[{2}]=40 V[{3}]=25 V[{4}]=45 {1} {2} {3} 30 40 1 2 3 4 {4} 25 45 V[{1,2}]=50 f[{1}]+f[{2}]=70 {1} {2} 70 V[{1,3}]=60 f[{1}]+f[{3}]=55 {1,3} 60 V[{1,4}]=80 f[{1}]+f[{4}]=75 {1,4} 80 V[{2,3}]=55 f[{2}]+f[{3}]=65 {2} {3} 65 V[{2,4}]=70 f[{2}]+f[{4}]=85 {2} {4} 85 V[{3,4}]=80 f[{3}]+f[{4}]=70 {3,4} 80 {2} {1,3} 100 {1,2,4} 120 V[{1,2,3}]=90 f[{2}]+f[{1,3}]=100 f[{1}]+f[{2,3}]=95 f[{3}]+f[{1,2}]=95 V[{1,2,4}]=120 f[{2}]+f[{1,4}]=110 f[{1}]+f[{2,4}]=115 f[{4}]+f[{1,2}]=115 V[{1,3,4}]=100 f[{3}]+f[{1,4}]=105 f[{1}]+f[{3,4}]=110 f[{4}]+f[{1,3}]=105 {1} {3,4} 110 V[{2,3,4}]=115 f[{2}]+f[{3,4}]=120 {2} {3,4} 120 f[{3}]+f[{2,4}]=110 f[{4}]+f[{2,3}]=110 V[{1,2,3,4}]=140 f[{2}]+f[{1,3,4}]=150 f[{4}]+f[{1,2,3}]=145 f[{1,3}]+f[{2,4}]=145 f[{1}]+f[{2,3,4}]=150 f[{3}]+f[{1,2,4}]=145 f[{1,2}]+f[{3,4}]=150 f[{1,4}]+f[{2,3}]=145 {1,2} {3,4} 150 Related Work Dynamic Programming techniques IDP [Rahwan & Jennings N. R., An Improved Dynamic Programming Algorithm for Coalition Structure Generation, AAMAS 2008]. Anytime with guarantees on solution quality IP [Rahwan et al., An Anytime Algorithm for Optimal Coalition Structure Generation, AAAI 2007, JAIR 2009]. Basic Idea of IP Upper bound = 550 Sub-space 500 Upper bound = 450 Sub-space Lower bound = 200 Lower bound = 250 Search space Upper bound = 250 Upper bound = 300 Sub-space Lower bound = 100 Sub-space Upper bound = 600 Sub-space 400 Lower bound = 100 Lower bound = 200 Upper bound = 350 Sub-space Lower bound = 150 Basic Idea of IP S {{a1, a2, a3, a4}} Upper bound [4] = 550 Sub-space 500 {{a1,a2}, {a3,a4}} Lower bound S [2,2] {{a1,a3},={a200 2,a4}} {{a1,a4}, {a2,a3}} Upper bound = 300 SSub-space 1 3 [1,3] Lower bound = 200 Upper bound = 450 Sub-space {{a=1}, {a2}, {a3,a4}} Lower bound 250 {{a1}, {a3}, {a2,a4}} {{a1}, {a4}, {a2,a3}} Upper bound = 250 S [1,1,2] } {a1}}, {a2,a3,aSub-space {{a2}, {a3}, {a1,a4}} {{a }} 4 Upper bound = 600 bound = 100 {{a }, ,a } {a2}}, {a1,aLower {{a }} 2 {a4}, {a1,a3}} 3 4 Sub-space {{a3}, {a4}, {a1400 ,a2}} {a3}}, {a1,a2,a4}}} {{a Lower bound = 100 {a4}}, {a1,a2,a3}}} {{a Upper bound = 350 Sub-space S[1,1,1,1] Lower {{a1bound }, {a2},= 150 {a3}, {a4}} How the Bounds are Computed value L1 1 2 3 4 125 50 75 150 Max1 = 150 Avg1 = 100 value L2 {1, {1, {1, {2, {2, {3, 2} 3} 4} 3} 4} 4} 175 150 100 150 200 125 Max2 = 200 Avg2 = 150 {1, {1, {1, {2, 2, 2, 3, 3, S [4] Avg=425 S [2,2] Avg=300 UB=400 S[1,1,2] Avg=350 UB=500 value L3 UB=425 {{a1,a2}, {a3,a4}} {{a1,a3}, {a2,a4}} {{a1,a4}, {a2,a3}} {{a1}, {a2}, {a3,a4}} {{a1}, {a3}, {a2,a4}} {{a1}, {a4}, {a2,a3}} {{a2}, {a3}, {a1,a4}} {{a2}, {a4}, {a1,a3}} {{a3}, {a4}, {a1,a2}} 3} 4} 4} 4} 200 150 300 150 Max3 = 300 Avg3 = 200 L4 value {1, 2, 3, 4} 425 Max4 = 425 Avg4 = 425 {{a1, a2, a3, a4}} S [1,3] Avg=300 UB=450 S [1,1,1,1] Avg=400 UB=600 {{a1}, {a2}, {a3}, {a4}} { {a1}, {a1, a2, a3} } { {a1}, {a1, a2, a4} } { {a1}, {a1, a3, a4} } { {a1}, {a2, a3, a4} } { {a2}, {a1, a2, a3} } {{a { {a2}, {a1, a2, a4} 1}, {a 2,a 3,a 4}}} { {a2}, {a1, a3, a4} } {{a 2}, {a 1,a 3,a 4}}} { {a2}, {a2, a3, a4} {{a3}, {a1,a2,a4}} { {a3}, {a1, a2, a3} } {{a { {a3}, {a1, a2, a4} 4}, {a 1,a 2,a 3}}} { {a3}, {a1, a3, a4} } { {a3}, {a2, a3, a4} } { {a4}, {a1, a2, a3} } { {a4}, {a1, a2, a4} } { {a4}, {a1, a3, a4} } { {a4}, {a2, a3, a4} } Searched initially (contains one solution) [8] Searched while scanning the input [4,4] [2,3,3] Avg=350 Avg=450 Avg=520 UB=600 [1,3,4] UB=575 Avg=450 UB=520 [1,1,2,2,2] Avg=380 UB=490 [1,1,1,1,2,2] Avg=500 UB=480 [1,1,1,2,3] Avg=470 UB=650 UB=525 Searched initially (contains one solution) Avg=390 UB=480 Avg=550 Avg=320 UB=390 [1,1,1,1,1,1,1,1] UB=620 Avg=420 UB=400 Avg=460 UB=510 [1,1,1,5] [1,1,1,1,4] [1,1,1,1,1,3] [1,1,1,1,1,1,2] Avg=360 [1,1,6] [1,1,2,4] [1,1,3,3] Avg=440 [1,7] [1,2,5] Avg=500 UB=700 [1,2,2,3] [2,2,2,2] [2,6] [3,5] [2,2,4] UB=400 Upper bound = 700 Lower bound = 550 UB=475 Avg=520 UB=540 Searched initially (contains one solution) [8] Searched while scanning the input [4,4] [2,3,3] Avg=350 Avg=450 Avg=520 UB=600 [1,3,4] UB=575 Avg=450 UB=520 [1,1,2,2,2] Avg=380 UB=490 [1,1,1,1,2,2] Avg=500 UB=480 [1,1,1,2,3] Avg=470 UB=650 UB=525 Searched initially (contains one solution) Avg=390 UB=480 Avg=550 Avg=320 UB=390 [1,1,1,1,1,1,1,1] UB=620 Avg=420 UB=400 Avg=460 UB=510 [1,1,1,5] [1,1,1,1,4] [1,1,1,1,1,3] [1,1,1,1,1,1,2] Avg=360 [1,1,6] [1,1,2,4] [1,1,3,3] Avg=440 [1,7] [1,2,5] Avg=500 UB=700 [1,2,2,3] [2,2,2,2] [2,6] [3,5] [2,2,4] UB=400 700 Upper bound = 650 550 Lower bound = 600 UB=475 Avg=520 UB=540 Why select sub-space with highest UB ? UB* UB* UB* UB* V* UB* Exercise: find the optimal solution using IP L1 Value 1 2 3 4 5 20 10 30 30 10 L2 Avg=20 Max=30 1, 1, 1, 1, 2, 2, 2, 3, 3, 4, Value 2 3 4 5 3 4 5 4 5 5 40 30 30 40 40 20 30 20 65 35 L3 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 2, 2, 2, 3, 3, 4, 3, 3, 4, 4, Avg=35 Max=65 Value 3 4 5 4 5 5 4 5 5 5 70 70 60 60 40 80 70 50 75 75 Avg=65 Max=80 [5] Avg=165 UB=165 [1,4] [2,3] Avg=140 UB=180 Avg=100 UB=145 [1,1,3] [1,2,2] Avg=105 UB=140 Avg=90 UB=160 [1,1,1,2] [1,1,1,1,1] Avg=95 UB=155 Avg=100 UB=150 L4 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4 5 5 5 5 value L5 value 110 140 100 150 100 1, 2, 3, 4, 5 165 Avg=120 Max=150 Avg=165 Max=165 Scanning the input L1 value 1 2 3 4 5 6 826 1108 1065 890 907 1024 L2 value 1, 2 1, 3 1, 4 1, 5 1, 6 2, 3 2, 4 2, 5 2, 6 3, 4 3, 5 3, 6 4, 5 4, 6 5, 6 1742 1667 1989 1664 2023 2083 2272 2082 1995 1807 2529 2045 1683 2115 1956 value L4 value L5 value L6 value 1, 2, 3 1, 2, 4 1, 2, 5 1, 2, 6 1, 3, 4 1, 3, 5 1, 3, 6 1, 4, 5 1, 4, 6 1, 5, 6 2, 3, 4 2, 3, 5 2, 3, 6 2, 4, 5 2, 4, 6 2, 5, 6 3, 4, 5 3, 4, 6 3, 5, 6 4, 5, 6 3352 3102 3301 3119 3287 2696 2950 3324 2460 3134 2943 2956 2950 3661 2618 2906 2769 3070 3135 1, 2, 3, 4 1, 2, 3, 5 1, 2, 3, 6 1, 2, 4, 5 1, 2, 4, 6 1, 2, 5, 6 1, 3, 4, 5 1, 3, 4, 6 1, 3, 5, 6 1, 4, 5, 6 2, 3, 4, 5 2, 3, 4, 6 2, 3, 5, 6 2, 4, 5, 6 3, 4, 5, 6 4355 4373 3770 3528 3967 3647 4142 3875 3905 3645 3850 4099 3967 3318 3576 1, 2, 3, 4, 5 1, 2, 3, 4, 6 1, 2, 3, 5, 6 1, 2, 4, 5, 6 1, 3, 4, 5, 6 2, 3, 4, 5, 6 4804 5657 4609 4829 5650 5852 1,2, 3, 4, 5, 6 6217 [6] L=1 L=2 L3 [3,3] [2,4] [1,5] Searching a Sub-space Example: Search the following sub-space Coalitions of size x Coalitions of size y [x, y, z] Coalitions of size z Direction of cycle C3 Overlap with {C1, C2} C2 C3 C2 Overlap with C1 Overlap with {C1, C2} C3 C1 C1 C1 C1 Overlap with C1 Overlap with {C1, C2} Example L3 C3 A = {1, 2, 3, 4, 5, 6, 7} Subspace = [2, 2, 3] Direction of cycle L2 C1 C1 C1 6, 5, 5, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, L2 7 7 6 7 6 5 7 6 5 4 7 6 5 4 3 7 6 5 4 3 2 C2 C2 C2 6, 5, 5, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 7 7 6 7 6 5 7 6 5 4 7 6 5 4 3 7 6 5 4 3 2 invalid 5, 4, 4, 4, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 6, 6, 5, 5, 6, 5, 5, 4, 4, 4, 6, 5, 5, 4, 4, 4, 3, 3, 3, 3, 6, 5, 5, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 7 7 7 6 7 7 6 7 6 5 7 7 6 7 6 5 7 6 5 4 7 7 6 7 6 5 7 6 5 4 7 6 5 5 4 3 invalid Searching a Sub-space Example: Search the following sub-space [x, y, z] Applying Branch and Bound: Example: If value of best solution found so far is 500, then if: Direction of cycle Coalitions of size x Coalitions of size y Coalitions of size z C2 C3 Value=100 C2 Overlap with C1 Value=100 C1 Overlap with C1 Maxz=200 then prune and gowith back Overlap {C1, C2} one step. Overlap with {C1, C2} Overlap with {C1, C2} A1 = A = { a, b , c , d , e , f ,g } Searching a subset A = {a,b,c,d,e,f,g} 6, 7 G = {2, 2, 3} 5, 7 5, 6 Direction of cycle 4, 7 4, 6 4, 5 M1 3, 3, 3, 3, 7 6 5 4 2, 2, 2, 2, 2, 7 6 5 4 3 1, 1, 1, 1, 1, 1, 7 6 5 4 3 2 A2 = A1 / C1 = { b, c, d, e, fg} 4, 5 3, 5 3, 4 C1={a,g} C1={a,f} M2 2, 5 2, 4 2, 3 M2 1, 1, 1, 1, 5 4 3 2 C2={c,d} c b, d e , fe g} C2={b,g} A3=A2 / C2 = {d C2={b,c} M3 1, 2, 3 Evaluation (Time to Terminate) 2.5 days 4 hours 25 min 379 sec CPLEX IDP-IP The Integer-Partition Graph [1,1,1,1,1,1,1,1] Level8 [1,1,1,1,1,1,2] Level7 [1,1,1,1,2,2] [1,1,2,2,2] 1,1 [2,2,2,2] 2 [2,3,3] [1,2,2,3] [2,2,4] [4,4] Level6 [1,1,1,1,1,3] [1,1,1,2,3] [1,1,3,3] [1,3,4] [2,6] [3,5] [8] Level5 [1,1,1,1,4] [1,1,2,4] [1,1,1,5] Level4 [1,2,5] [1,1,6] Level3 [1,7] Level2 Level1 Coalition Structure Graph {a1},{a2},{a3},{a4} {a1},{a 2},{a3,a4} {a3},{a4},{a1,a2} {a1},{a3},{a2,a4} {a2},{a4},{a1,a3} {a1},{a4},{a2,a3} {a2},{a3},{a1,a4} {1},{2},{3,4} {a{1},{2,3,4} 1},{a2,a3,a4} {a1,a2},{a3,a4} {a2},{a1,a3,a4} {a1,a3},{a2,a4} {a3},{a1,a2,a4} {a1,a4},{a2,a3} {a4},{a1,a2,a3} {a1,a2,a3,a4} Integer Partition Graph [1,1,1,1] {{a1}, {a2}, {a3,a4}} , {{a1}, {a3}, {a2,a4}} {{a1}, {a4}, {a2,a3}} , {{a2}, {a3}, {a1,a4}} {{a2}, {a4}, {a1,a3}} , {{a3}, {a4}, {a1,a2}} {{a1}, {a2,a3,a4}} {{a2}, {a1,a3,a4}} {{a3}, {a1,a2,a4}} {{a4}, {a1,a2,a3}} {{a1, a2, a3, a4}} Level3 [1,1,2] [2,2] [1,3] [4] Level4 {{a1,a2}, {a3,a4}} {{a1,a3}, {a2,a4}} {{a1,a4}, {a2,a3}} {{a1}, {a2}, {a3}, {a4}} Level2 Level1 IDP-IP The Integer-Partition Graph [1,1,1,1,1,1,1,1] IDP Level8 [1,1,1,1,1,1,2] IDP Level7 [1,1,1,1,2,2] IDP [1,1,2,2,2] [2,2,2,2] IDP [2,3,3] IDP [1,1,1,2,3] IDP IDP [1,2,2,3] IDP [2,2,4] IDP [4,4] IDP [1,1,1,1,1,3] [1,1,3,3] IDP [1,3,4] IDP [3,5]IDP Level6 [1,1,1,1,4] IDP [1,1,2,4] IDP [1,2,5] [2,6]IDP [8] IDP IDP IDP Level5 [1,1,1,5] IDP Level4 [1,1,6] IDP [1,7] IDP Level3 Level2 Level1 IDP-IP The Integer-Partition Graph [1,1,1,1,1,1,1,1] Which one should we search first ? [1,1,1,1,1,1,2] [1,1,1,1,2,2] [1,1,2,2,2] IP No edge! [2,2,2,2] IDP Level8 IDP Level7 [1,1,1,1,1,3] [1,1,1,2,3] IDP IDP [1,2,2,3] IDP IDP [1,1,3,3] IDP IDP Level6 [1,1,1,1,4] [1,1,2,4] IDP IDP Level5 [1,1,1,5] IDP Level4 ? IP No edge! IP No edge! [2,3,3] [2,2,4] ? ? [4,4] IDP IP No edge! [1,3,4] [1,2,5] IDP [1,1,6] IDP Level3 ? [3,5]IDP [2,6]IDP [8] IDP [1,7] IDP Level2 Level1 Exercise By setting m=2, which subspaces are searched by IP, and in which order ? 1 [1,1,1,1,1,2] 21 [1,1,1,2,2] 105 [1,2,2,2] [1,3,3] [3,4] size of subspace [1,1,1,1,1,1,1] 70 35 105 [1,1,2,3] 210 [1,2,4] 105 21 [2,5] [7] 35 [1,1,1,1,3] 1 35 [1,1,1,4] 21 [1,1,5] [1,6] 7 Exercise By setting m=2, which subspaces are searched by IP, and in which order ? [1,1,1,1,1,1,1] 1 [1,1,1,1,1,2] 21 [1,1,1,2,2] 105 [1,2,2,2] [1,3,3] [3,4] 70 35 105 35 [1,1,1,1,3] [1,1,2,3] 210 [1,2,4] 105 21 [2,5] [7] delete 1 35 [1,1,1,4] 21 [1,1,5] [1,6] 7 Exercise By setting m=2, which subspaces are searched by IP, and in which order ? [1,1,1,1,1,1,1] IDP 1 [1,1,1,1,1,2] IDP 21 [1,1,1,2,2] [1,2,2,2] IP 105 [1,3,3] IP 70 [3,4] IDP 35 IDP 105 [1,1,1,1,3] IDP 35 [1,1,2,3] IP 210 [1,1,1,4] [1,2,4] [2,5] [7] IP 105 IDP 21 IDP 1 [1,1,5] [1,6] IDP 35 IDP 21 IDP 7 Exercise By setting m=2, which subspaces are searched by IP, and in which order ? [1,1,1,1,1,1,1] IDP 1 [1,1,1,1,1,2] IDP 21 [1,1,1,2,2] [1,2,2,2] IP 105 105+105+21+1 = 2.21 105 [1,3,3] 70 70 [1,1,1,1,3] IDP 35 [1,1,2,3] IP 210 [1,1,1,4] 210+35 210 IP 70 IDP 35 [1,2,4] [2,5] [7] IDP 35 = 1.16 105+35 105 =1 [3,4] IDP 105 IP 105 [1,1,5] IDP 21 = 1.33 IDP 21 IDP 1 [1,6] IDP 7 Coalition Structure Generation in Multi-Agent Systems with Positive and Negative Externalities CSG in Characteristic Function Games Given 3 agents: the set of agents is: {a1,a2,a3} INPUT The possible coalitions are: {a1} 20 {a2} 40 {a3} 30 {a1,a2} 70 40 a value for every coalition {a1,a3} {a2,a3} 65 95 {a1,a2,a3} OUTPUT The possible coalition structures: {{a1},{a2},{a3}} 20+40+30=90 {{a1,a2},{a3}} 70+30= 100 an optimal coalition structure {{a2},{a1,a3}} {{a1},{a2,a3}} {{a1,a2,a3}} 40+40 = 80 20+65= 85 95 Assumption: The value of a coalition structure is the sum of the values of the coalitions within that structure CSG in Characteristic Function Games Given 3 agents: the set of agents is: {a1,a2,a3} INPUT The possible coalitions are: {a1} 20 {a2} 40 {a3} 30 {a1,a2} 70 40 a value for every coalition {a1,a3} {a2,a3} 65 95 OUTPUT The possible coalition structures: {{a1},{a2},{a3}} {{a1,a2},{a3}} 90 70+30 = 100 35 +40+30= 105 20 {a1,a2,a3} an optimal coalition structure {{a2},{a1,a3}} {{a1},{a2,a3}} {{a1,a2,a3}} 40+40= 80 +65 =15 20 95 80 85 Assumption: The value of a coalition structure is the sum of the values of the coalitions within that structure The merging of two coalitions may affect the values of other coalitions in the structure! Michalak et. al. [ECAI-2008] focused on the following classes: - CS' C1 + externality CS' C2 U CC 3 1 C2 U C3 - + CS CS C1 C2 C31 C2 C3 Sub-additive values, Super-additive values, Games with externalities are known as Partition Function Games positive externalities negative externalities Computing Upper & Lower Bounds We need to compute upper and lower bounds on the value of any combination of disjoint coalitions Example: C1 C2 The maximum possible value of this combination is 500, and the minimum possible value is 100 : PF <> PF + < > Establishing Worst-Case Guarantees We need to identify the minimum set of coalition structures that must be searched in order to establish a worst-case guarantee We need to develop a novel algorithm for improving the worst-case bound with further search the best coalition structure in this set is within a bound m from the optimal coalition structure Search space Main Theorem X is a set of elements Y is a set of subsets of X Every xi X may have different values in different subsets Let Y' be a subset of Y such that every element in X appears with its maximum value in Y' then the value of the best subset in Y' is within a bound m from the optimal, where m is the size of the biggest subset in Y The bound equals the size of the biggest subset MUS T BE Y/Y’ Y x2 x3 x1 x2 x4 x4 x5 Y' x 3 x4 50 x3 x 5 x1 x5 30 x 2 x5 x1 x3 x1 x4 x5 20 70 X x2 x 4 x 1 x 3 x5 In the next few slides, we will be using the following graphical representation: i,j,k,... integers represent coalition sizes 2 {a1, a2} {a1,a3} {a1,a4} {a2,a3} {a2,a4} {a3,a4} 1,1 {{a1}, {a2}} {{a1}, {a3}} {{a1}, {a4}} {{a2}, {a3}} {{a2}, {a4}} {{a3}, {a4}} { {a1,a2}, { {a1,a3}, { {a1,a4}, { {a2,a3}, { {a2,a4}, { {a3,a4}, 2,1,1 {a3}, {a2}, {a2}, {a1}, {a1}, {a1}, 4 1,3 2,1,1 2 2,2 1,1,1,1 Set of coalition structures 1 4 3 Set of coalitions {a4} } {a4} } {a3} } {a4} } {a3} } {a2} } Establishing the Worst-Case Bound Y' in this set, every coalition appears with its maximum value [10] Y [8,1,1] [9,1] [8,2] [7,2,1] [6,3,1] [7,1,1,1] [5,1,1,1,1,1] [5,2,1,1,1] [4,1,1,1,1,1,1] [3,1,1,1,1,1,1,1] [3,1,1,1,1,1,1,1 [6,4] [4,2,2,2] [3,3,1,1,1,1] [3,2,1,1,1,1,1] [2,2,1,1,1,1,1,1] [1,1,1,1,1,1,1,1,1,1] [4,4,2] [5,2,2,1] [3,3,3,1] [4,2,2,1,1] [5,5] [5,3,2] [5,4,1] [5,3,1,1] [4,3,1,1,1] [4,2,1,1,1,1] the bound equals the size of the biggest subset [6,2,2] [6,2,1,1] [4,3,2,1] [6,1,1,1,1] [7,3] [4,3,3] [4,4,1,1] [3,3,2,2] [3,3,2,1,1] [3,2,2,2,1] [3,2,2,1,1,1] [2,2,2,2,2] [2,2,2,2,1,1] [2,2,2,1,1,1,1] X [2,1,1,1,1,1,1,1,1] ? [1,1] [2,2] [1,1,1,1] [1] [2] [3] [6] [7] [9] [4] [8] [10] [5] Solve Using Integer Programming Constrained Coalition Formation 88 Constrained Coalition Formation (CCF) In conventional models: • every possible subset of agents is a potential coalition, • every possible partition of the set of agents is a potential coalition structure. Many times we have constraints that enforce or prohibit the co-existence of certain agents in a coalition. To date, very limited work on constraints, e.g., only permitting certain sizes. 89 General Model Let P(A) be the set of all coalition structures. A constrained coalition formation (CCF) game is a tuple G = 〈A,CS, v〉 where: • A = {a1, …, an} is the set of agents • CS ⊆ P(A) is the set of coalition structures that are feasible • v : (⋃CS ∈ CS ⋃C ∈ CS {C}) → ℝ assigns a value to every coalition that appears in some feasible coalition structure Feasibility is defined for coalition structures rather than for coalitions: • Example: a coalition structure is feasible only if it contains coalitions of equal sizes. • In this example, {{a1},{a2},{a3,a4}} is not feasible, even though each of its coalitions may be a part of some feasible coalition structure 90 Locally Constrained Games A CCF game G = 〈A,CS, v〉 is locally constrained if there exists a set of coalitions, C ⊆ 2A, such that CS = {CS ∈ P(A) : CS ⊆ C }. • We will refer to the coalitions in C as feasible coalitions. Constraints are represented using propositional logic: • Boolean variables correspond to agents: BA = { bi : ai ∈ A } • Let d be a propositional formula over BA constructed using the classical connectives ( ⋀, ⋁, ¬, →, …). • Coalition C satisfies d iff d is satisfied under the truth assignment that sets all bi : i ∈ C to true, and all bi : i ∉ C to false. • Example: C = {a1,a4,a5,a7} satisfies d = b4 ⋀ b5 Proposition: The class of propositionally definable CCF games is equal to the class of locally constrained CCF games. 91 Basic CCF Model A basic CCF game is a tuple G = 〈A, P, N, S, v〉 where: • P is a set of subsets of A (Positive constraints) • N is a set of subsets of A (Negative constraints) • S ⊆ ℕ (permitted sizes) A coalition C is feasible if: • P ⊆ C for some P ∈ P • N ⊈ C for all N ∈ N • |C| ∈ S We will denote the feasible coalitions as c (A, P, N, S) 92 Basic CCF Model 93 94 Basic CCF Model N P S 1 3 2 9 4 General CCF games Constraints are placed on Coalition Structures Local CCF games Constraints are placed on Coalitions • Constraint can be expressed using propositional logic Basic CCF games Constraints are placed on Coalitions In the form of: • Size constraints • Positive constraints • Negative constraints 95 How to Generate Feasible Coalitions? Given a set of constraints, how do we generate the feasible coalitions? P = {Ø} , N = { {1,2,3,4}, {1,2,4,5}, {5,6} } size=1 size = 2 size = 3 size = 4 size = 5 size = 6 1 1, 2 1, 2, 3 1, 2, 3, 4 1, 2, 3, 4, 5 1, 2, 3, 4, 5, 6 2 1, 3 1, 2, 4 1, 2, 3, 5 1, 2, 3, 4, 6 3 1, 4 1, 2, 5 1, 2, 3, 6 1, 2, 3, 5, 6 4 1, 5 1, 2, 6 1, 2, 4, 5 1, 2, 4, 5, 6 5 1, 6 1, 3, 4 1, 2, 4, 6 1, 3, 4, 5, 6 6 2, 3 1, 3, 5 1, 2, 5, 6 2, 3, 4, 5, 6 2, 4 1, 3, 6 1, 3, 4, 5 2, 5 1, 4, 5 1, 3, 4, 6 2, 6 1, 4, 6 1, 3, 5, 6 3, 4 1, 5, 6 1, 4, 5, 6 3, 5 2, 3, 4 2, 3, 4, 5 3, 6 2, 3, 5 2, 3, 4, 6 4, 5 2, 3, 6 2, 3, 5, 6 4, 6 2, 4, 5 2, 4, 5, 6 5, 6 2, 4, 6 3, 4, 5, 6 2, 5, 6 3, 4, 5 3, 4, 6 3, 5, 6 4, 5, 6 96 Divide & Conquer A P N N∗ P∗ f ( {12345678} , {158},{257},{578} , {123}{235} , Ø , Ø ) f ( {2345678} , {58}{257}{578} , {23}{235} , {1} , Ø ) f ( {2345678} , {257}{578} , {235} , Ø , {1} ) 97 Divide & Conquer Repeat the division recursively until we reach: • an impossible case, where: P = Ø or N ∋ Ø • or a base case, where: |P| = 1 and ∩N = Ø and |{N ∈ N : |N|>1 }| < 1 99 f ( A, P, N, P*, N*) = f ( {12345678} , {158}{257}{578} , {123}{235} , Ø , Ø ) Divide & Conquer f ( {2345678} , {58}{257}{578} , {23}{235} , {1} , Ø ) f ( {234678} , {8}{27} , {23} , {15} , Ø ) f ( {34678} , {8}{7} , {3} , {152} , Ø ) f ( {234678} , Ø , {23} , {1} , {5} ) f ( {34678} , {8} , Ø , {15} , {2} ) Impossible case P* = {{158}} , N* = {{2}} f ( {467} , Ø{7} , Ø , {1528} , Ø ) P* = {{1528}} , N* = Ø f ( {467} , {7} , Ø , {152} , {8} ) P* = {{1527}} , N* = {{8}} f ( {2345678} , {257}{578} , {235} , Ø , {1} ) f ( {345678} , {57}{578} , {35} , {2} , {1} ) f ( {345678} , {578} , Ø , Ø , {1}{2} ) P* = {{578}} , N* = {{1}{2}} f ( {45678} , {57} , {5} , {23} , {1} ) Impossible case f ( {45678} , {57}, Ø , {2} , {1}{3} ) P* = {{257}} , N* = {{1}{3}} 100 How to Generate the coalitions that correspond to a base case? Example: base case give 10 agents P* = {{1,2}} , N* = { {3,4,5},{6},{7}} , S* = {1,2} The single constraint in P* {1,2} X C {3,4,5} : |C| ∈ S* Ø {3} {4} {5} {3,4} {3,5} {4,5} X C {8,9,10} : |C| ∈ S* Ø {8} {9} {10} {8,9} {8,10} {9,10} 101 Back to our Example We wanted to generate the feasible coalitions using the base cases P = {Ø} , N = { {1,2,3,4}, {1,2,4,5}, {5,6} } size=1 size = 2 size = 3 size = 4 size = 5 size = 6 1 1, 2 1, 2, 3 1, 2, 3, 4 1, 2, 3, 4, 5 1, 2, 3, 4, 5, 6 2 1, 3 1, 2, 4 1, 2, 3, 5 1, 2, 3, 4, 6 3 1, 4 1, 2, 5 1, 2, 3, 6 1, 2, 3, 5, 6 4 1, 5 1, 2, 6 1, 2, 4, 5 1, 2, 4, 5, 6 5 1, 6 1, 3, 4 1, 2, 4, 6 1, 3, 4, 5, 6 6 2, 3 1, 3, 5 1, 2, 5, 6 2, 3, 4, 5, 6 2, 4 1, 3, 6 1, 3, 4, 5 2, 5 1, 4, 5 1, 3, 4, 6 2, 6 1, 4, 6 1, 3, 5, 6 3, 4 1, 5, 6 1, 4, 5, 6 3, 5 2, 3, 4 2, 3, 4, 5 3, 6 2, 3, 5 2, 3, 4, 6 4, 5 2, 3, 6 2, 3, 5, 6 4, 6 2, 4, 5 2, 4, 5, 6 5, 6 2, 4, 6 3, 4, 5, 6 2, 5, 6 3, 4, 5 3, 4, 6 3, 5, 6 4, 5, 6 102 Back to our Example This can be done using the base cases as follows: P = {Ø} , N = { {1,2,3,4}, {1,2,4,5}, {5,6} } size=1 size = 2 size = 3 size = 4 size = 5 size = 6 1 1, 2 1, 2, 3 1, 2, 3, 4 1, 2, 3, 4, 5 1, 2, 3, 4, 5, 6 2 1, 3 1, 2, 4 1, 2, 3, 5 1, 2, 3, 4, 6 3 1, 4 1, 2, 5 1, 2, 3, 6 1, 2, 3, 5, 6 4 1, 5 1, 2, 6 1, 2, 4, 5 1, 2, 4, 5, 6 5 1, 6 1, 3, 4 1, 2, 4, 6 1, 3, 4, 5, 6 6 2, 3 1, 3, 5 1, 2, 5, 6 2, 3, 4, 5, 6 2, 4 1, 3, 6 1, 3, 4, 5 P1* = {Ø} N1* = {{1},{5,6}} P2* = {{1}} N2* = {{2},{5,6}} 2, 5 1, 4, 5 1, 3, 4, 6 2, 6 1, 4, 6 1, 3, 5, 6 P3* = {{1,2}} N3* = {{3},{4},{5,6}} 3, 4 1, 5, 6 1, 4, 5, 6 3, 5 2, 3, 4 2, 3, 4, 5 3, 6 2, 3, 5 2, 3, 4, 6 4, 5 2, 3, 6 2, 3, 5, 6 4, 6 2, 4, 5 2, 4, 5, 6 5, 6 2, 4, 6 3, 4, 5, 6 P4* = {{1,2,4}} N4* = {{3},{5}} P5* = {{1,2,3}} N5* = {{4},{5,6}} 2, 5, 6 3, 4, 5 3, 4, 6 3, 5, 6 4, 5, 6 How to search the feasible coalition structures? 103 Searching Feasible Coalition Structures a5 a1 a4 a7 a2 a2 (P2*,N2*) a1 a2 a6 (P4*,N4*) a4 (P1*,N1*) a5 a1 a7 (P3*,N3*) impossible case a8 (P5*,N5*) (P8*,N8*) a3 (P7*,N7*) a4 (P6*,N6*) a6 (P9*,N9*) a1 a1 a6 a1 a8 a2 a6 a4 a8 a3 a7 (P11*,N11*) impossible case (P12*,N12*) (P10*,N10*) a8 a7 a6 (P13*,N13*) (P15*,N15*) a6 (P14*,N14*) (P1*,N1*) (P5*,N5*) (P2*,N2*) (P6*,N6*) (P9*,N9*) (P12*,N12*) (P3*,N3*) (P7*,N7*) (P10*,N10*) (P13*,N13*) (P15*,N15*) (P4*,N4*) (P8*,N8*) (P11*,N11*) (P14*,N14*) L5 L1 L2 L3 L4 10 4 Searching Feasible Coalition Structures (P1*,N1*) (P2*,N2*) (P3*,N3*) (P4*,N4*) (P5*,N5*) L1 (P6*,N6*) (P10*,N10*) (P7*,N7*) (P11*,N11*) (P8*,N8*) (P12*,N12*) (P9*,N9*) (P13*,N13*) L2 L3 (P14*,N14*) (P15*,N15*) (P17*,N17*) (P16*,N16*) L5 L4 Every feasible coalition structure contains exactly one coalition from L1, and at most one coalition from Li : i = 2, 3, … For every coalition C1 ∈ L1: add C1 to CS and, and add the agents in C1 to Nj* for every (Pj*,Nj*) ∈ L2 If UCS ≠ A, the process is repeated: add a coalition C2 ∈ L2 to CS, and add the agents in C1 U C2 to every (Pj*,Nj*) ∈ L3… etc. To speed up the search, we apply a branch-and-bound technique. 105 Experimental Results Time in log scale to find an optimal coalition structure We outperform existing algorithms by several orders of magnitude 106