Lecture 7: Computational Coalition Formation

목차

What is an Agent?

- Intelligent entity that is situated in an environment and can perceive the environment. Agent has goals and a list of available actions and act autonomously to satisfy goals and is social.

가상공간에 위치 하여 특별한 응용 프로그램을 통해 사용자를 도울 목적으로 반복 작업을 자동으로 처리하는 컴퓨터 프로그램

 

 

Example: the Prisoner's Dilemma

- 두 명의 에이전트가 있고 범죄를 질렀다. 

- 법원은 증거가 없어서 경범죄만 우선 적용됐다. (감방 1년씩)

- 만약에 한명만 자백하면 바로 나가고, 나머지가 4년을 지낸다.

- 둘 다 자백하면 둘다 3년을 지내야 한다.

- 그리고 에이전트들은 no way of communicating or making binding agreements.

 

이 상황을 매트릭스로 표현하면 다음과 같다. 

 

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.

 

a1's reasoning:

- if a2 stays quiet, I should confess

- if a2 confesses, I should confess too.

Same goes for a2.

 

Result: they both confess and get 3 years in prison.

 

 

Cooperative vs. Non-Cooperative Games

In Non-Cooperative games, players cannot make binding agreements.

 

Cooperative games model scenarios in which:

- binding agreements are possible

- agents can benefit by cooperating

In a cooperative game, agents, whether selfish or working towards a common goal, benefit from cooperation

 

 

Agent Coalitions (연합)

- Coalitions in general are goal-directed and short-lived (once the purpose is met, the coalition doesn't exist anymore)

- No coordination among members of different coalitions

- The organizational structure within each coalition is flat (the hierarchy is flat)

 

 

Why agents form Coalitions?

Agents can improve their performance by forming coalitions (achieve the tasks in a more efficient way).

This holds both for cooperative agents, i.e. agents who share a common set of goals, and for selfish agents who only care about their own payoffs.

For cooperative agents, to find the optimal collaboration pattern, it suffices to identify the best way of splitting agents into teams.

In contrast, when the agents are selfish, we also have to specify how to distribtue the gains from cooperation, since each agent needs to be incentivized to participate in the proposed solution. 

 

즉, cooperative agent들은 같은 목표를 가지고 있기 때문에 연합을 하면 더 효율적으로 목표를 이룰 수 있다. 단, selfish agent들은 각자의 이익을 우선시하기 때문에 목표를 이룬 다음에 이익을 어떻게 배분할 지도 알아야한다.

 

 

Coalition Formation Games

 

Partition Function Game (PFG)

In a partition function game, the game is defined by specifying a partition function, which represents the set of feasible payoff allocations that can be achieved by various coalitions.
Unlike the characteristic function, which directly assigns a value to each coalition, the partition function specifies which allocations of the worth among the players are feasible.
The partition function captures the idea that different coalitions may achieve the same total worth but distribute it among the players in different ways.

 

Characteristic Function Game (CFG)

In a characteristic function game, the worth or value of each coalition (subset of players) is explicitly defined by a characteristic function.
The characteristic function assigns a value to each possible coalition of players, indicating the total worth or payoff that the coalition can achieve by cooperating.

 

 

Example: Buying Ice-Cream

n children, each has some money:

Supermarket sells many icecream tubs in different sizes:

- Type 1 contains 500g, $7

- Type 2 contains 650g, $9

- Type 3 contains 1kg, $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 - icecream is transferrable

CFG - many available tubs 

CFG 인 이유: 연합이 받을 수 있는 보상은 연합의 멤버들이 돈을 모아서 살 수 있는 아이스크림의 개수이기 때문. 

 

 

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

- teaching load reduction

 

NTU (payoffs are non-transferable - you can't transfer promotion) - 승진 같은거는 나눌 수 없음

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 - money is transferable

PFG - a group can influence another (과일의 가격이 공급에 따라 달라지기 때문)

 

 

 

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: 2^A → 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

 

 

 

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,

     - C¡ ∩ Cj = Ø for i ≠ j

 

- x = (x1, ... , xn) is a payoff vector, which specifies the payoff of each agent:

     - x¡ ≥ 0 for all a¡ ∈ A

     - ∑i: a¡ ∈ C x¡ = v(C) for all C ∈ CS

 

Coalition Formation Process

즉, 연합의 보상이 최적인지 아닌지 확인하는 과정.

 

 

Coalition Structure Generation in CFGs

 

 

 

Example:

여기서 optimal solution은 { {1}, {2}, {3, 4} }가 되겠다.

 

 

 

 

Greedy Algorithm for CSG

Explore the CS graph greedily

Start from single-agent coalition structure and work your way down the CS graph

→ 이 그래프에 나와있는 것처럼, agent들이 하나씩 있는 노드에서 시작해서 그리디 방법으로 나아간다.

 

At each level in the graph: what do we gain by merging two coalitions? 

Stop when there is no more gain in merging.

 

Given two coalitions Ci and Cj: 

Gain(Ci, Cj) = v(Ci ∪ Cj) - v(Ci) - v(Cj)

 

→ 즉, 두개의 연합을 합쳤을 때 보상과 두개의 연합이 따로 따로 있었던 보상을 빼줌으로 얼마나 이익인지를 확인.

 

위에 있었던 그래프를 예시로 보겠다.

 

이 표에 나와있는 것처럼, a3, a4 합쳤을 때 value가 가장 크므로 {a3, a4} 합친다 (연합). 

 

a3와 a4를 연합한 이후에 표다. 여기서는 어떤 연합들을 합치든간에 다 마이너스이기 때문에 여기서 중단. 

 

 

Advantages and Disadvantages

Advantage:

- Efficient: O(n³)

 

Disadvantage:

- Does not guarantee optimal solution (최적의 솔루션을 못 찾을 수도 있음)

 

 

 

Dynamic Programming 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.

 

 

 

예시

 

1. 우선 시작은 연합이 없는 상태 (크기 = 1). 이 상태에서 각 coalition들의 value (이익)을 본다.

 

2. 두번째 단계는 연합의 크기가 2인 상태이다. 여기서, 만들 수 있는 모든 경우를 보고 가능한 각 연합마다 최대 값을 구한다. 예를 들어서, 1과 2같은 경우에는 연합을 안 한 경우에 값이 더 높으므로 연합을 안 한 상태인 {1}, {2}로 유지. 

 

3. 이 과정에서는 연합의 크기가 3인 것들을 확인하는 단계이다. 여기서도 마찬가지로, 가능한 모든 경우를 보고 연합을 합치는게 나을지 아니면 따로 따로 유지하는게 나을지를 확인. 

 

마지막에 f( {1, 2} ) + f( {3, 4})의 값이 가장 크게 나왔다. 이 과정에서 저장된 값 (memoized) 값을 보는것이므로 {1, 2} = {1} {2}가 되고 {3, 4}는 그대로인 상태이다. 

 

 

Advantages and Disadvantages

Advantage

- Guaranteed to find an optimal solution

 

Disadvantage

- Efficiency: O(3ⁿ) → DP is better than brute-force but worse than the greedy algorithm

 

 

 

 

 

Integer Partitioning Algorithm (IP)

Divide large search space into subspaces and for each sub-space, set upper bounds and lower bounds. 

 

1. Start with a search space and divide with sub-spaces.

 

2. For each sub-space, identify upper bounds and lower bounds

 

3. Start with the sub-space with the highest upper bound and calculate the actual value. (가장 높은 값을 찾는 것이기 때문) 이 예시에서는 가장 높은 upper-bound를 가지고 있는 sub-space의 값이 400이 나왔다. Upper-bound가 400이하인 sub-space는 탐색을 할 필요가 없으므로 지운다.

4. Go through the remaining sup-spaces until the sub-space with the highest value is found. 즉, 가장 값이 높은 sub-space를 찾을 때 까지 반복.

 

 

How to find the subspaces

이 경우에는 agent가 총 4개가 있다. 따라서, 다음과 같은 경우로 나눌 수 있다. 

 

 

 

 

How the bounds are computed

예시를 들어보겠다. S[4] 같은 경우에 여기서 value가 가장 높은 425가 된다. 그리고 S[1, 3] 같은 경우에는 L1에서의 최댓값과 L3에서의 최댓값을 더한게 S[1, 3]의 upper-bound가 된다. 마찬가지로, lower-bound는 최소값 대신에 평균값을 사용한다.

 

 

 

 

Example: 8 Agents

 

1. 해답이 하나만 있는 경우에는 초반에 탐색된다. 남아있는 모든 경우의 upper bound와 lower bound를 구한다. 그리고 여기서 가장 큰 upper-bound와 lower-bound가 우리가 원하는 범위가 된다. 이 경우에는 [1, 3, 4]의 700이 Upper bound가 되고 [1, 1, 2, 4]의 Lower-bound가 해답의 Lower-bound가 된다.

 

 

2. Sub-space의 Upper bound가 해답의 Lower-bound보다 작거나 같은 경우들은 탐색 범위에서 제외시킨다.

 

 

3. 남아있는 탐색 범위들에서 Upper-bound가 가장 큰 Subs-space를 탐색한다. 여기서는 [1, 3, 4]가 된다. 여기서 값이 600이 나왔다고 하겠다. 그러면 Lower bound를 550에서 600으로 수정해주고 그다음에 가장 큰 Upper-bound인 650 ([1, 1, 1, 1, 2, 2])가 해답의 Upper-bound가 된다.

 

 

4. 이 과정을 반복한다. 

 

 

 

Advantages and Disadvantages

Advantages:

- Guaranteed to find an optimal solution

- Anytime algorithm (Algorithm that provides useful results incrementally). 계속 solution이 optimal solution까지 좋은 답을 찾는 알고리즘.

- Works fast in practice

 

Disadvantages:

- Efficiency: O(nⁿ)

- In the worst case, IP may have to search the entire space