###### 回到首頁: [:link:][HomePage]

# **An efficient algorithm for task allocation with the budget constraint**
### [LLV+22](https://www.dropbox.com/s/quhysuvfpryigis/LLV%2B22.pdf?dl=0)

## Section 1 : Introduction

考慮了預算 (budget) 的演算法，用來解決 task allocation problem。

---

## Section 2 : Related works

暫略

---

## Section 3 : Problem description

$T = \{t_1,...,t_n\}$
* 表示 **n** 個 **tasks**

$A = \{a_1,...,a_m\}$
* 表示 **m** 個 **agents**
* 每個 **agent** $a_i$ 都有一個 $p_i$ 代表 **cost**

$S = \{C_1,...,C_n\}$　
* 表示 **task i** 被 assign 給哪個 **agent** (coalition structure)
* 每個 agent 最多只能參加一個 coalition
* $S_{a_i}$ 代表 agent $a_i$ 可以加入的 set of coalition

以下假設：
* 不管這個 agent 做了哪些工作，他的 **cost** 都是固定的 $p_i$
* agent 不做工作就不會有 cost
* 每個 agent 都願意為此系統做出貢獻

---
### Task and system utilities

$U_j(C_j)$
* 表示 $t_j$ 的 task **utility**

$\displaystyle\Phi(S) = \sum_{C_j\in S}U_j(C_j)$
$\displaystyle\text{EMD}^i_j = \sum_{l\in\mathcal{L}}||P_i(y = l) - P_j(y = l)||$
* 表示整個系統的 **utility** (加總所有 task 的 utility)

---
### Marginal contribution

$\sigma_j(a_i,C_j) = U_j(C_j) - U_j(C_j\setminus\{a_i\})$
* 表示 **agent** $a_i$ (**加入後**的 utility) 扣掉 (**加入前**的 utility)

---
### Cost

$p_j(C_j) = \displaystyle\sum_{a_i\in C_j}p_i$
* 表示 **coalition** $C_j$ 解決 **task** $t_j$ 所花費的 cost
* 因為不同的 agent 有不同的 cost，task 的 cost 只會跟組成的 agent 有關

$P(S) = \displaystyle\sum_{C_j\in S}p_j(C_j)$
* 表示 **system cost**，也就是把所有 task 的 cost 作加總

---
### Objective

$S^* = \displaystyle \arg \max_{S \in O} \Phi(S),\ and\ P(S^*) \le B.$

* 目標為找出能**最大化 utility 並且不超過 budget $B$** 的 allocation solution S*
* O 為所有可能的 allocation solutions

---
### Scenario


* 上圖是災難救援的示意圖，$t_1$, $t_2$ 為2種不同的**災害現場**，$a_1$~$a_5$ 是5種不同的**救難工具**


* 每一種 task (災害現場) 都有各自所需要的救援資源
* 這邊的 $f_1$ 代表**醫療資源**，$f_2$ 代表**吊掛機械**
* 此圖表示 $t_1$ 需要醫療資源及吊掛機械，而 $t_2$ 只需要醫療資源

* 每一個 agent (救援器具) 都有自己能提供的能力，以及花費
* $a_5$ 表示可提供 10 點的醫療能力，以及 8 點的吊掛能力，並且花費為 9 點

* $e^l_i$ 表示 $a_i$ 可以提供多少資源在 $f_l$，ex: $e^1_5$ = 10，$e^2_5$ = 8

$U_j(C_j) = \displaystyle\sum_{f_l\in F_{t_j}}\mathop{max}_{a_i \in C_j } e^l_i$
* 這篇的 utility function 被設定為，加總 Coalition 中，各項所需救援資源中，能提供最高資源的 agent 的 $e^l_i$
* $C_0$ 代表 **dummy coalition**，也就是什麼 task 都沒有去幫忙
* 不管 **dummy coalition** 的成員組成為何，**dummy task** 的 utility always = 0
* 假設現在的 Coalition structure 為: $C_0 = \{a_1,a_5\}, C_1 = \{a_2,a_4\}, C_2 = \{a_3\}$
* 則 $U_1(\{a_2,a_4\}) = 10 + 3 = 13$ , $U_2(\{a_3\}) = 1$

---

## Section 4 : Game formulation for the task allocation problem

### Payoff

* 不超過 budget $B$ 限制的 coalition structure 為 valid 的解
* 所有在超過 budget 限制的 coalition 中的 agent ，所得 payoff = 0
* 否則加入 coalition $C_j$ 的 payoff = **marginal contribution**：$\sigma_j(a_i,C_j)$
* 每個 agent 的目標都是要透過**挑選最好的 strategy 來最大化自己的 payoff**
* agent 可以隨時更改自己的 strategy ，從一個 coalition 跳到另一個 coalition，以達到更好的 payoff，直到達到 Nash Equilibrium

---
### **Nash Equilibrium**
定義：在 coalition structure S 中，**沒有 agent 可以透過加入其他 coalition 來達到更好的 payoff**

---
### **Movement Value**
${mv}^i_{j\rightarrow h } = \sigma_h(a_i,C^\prime_h) - \sigma_j(a_i,C_j), C^\prime_h = C_h \cup \{a_i\}$

* agent $a_i$ 從 $C_j$ 移動到 $C_h$ (移過去後會變成 $C^\prime_h$ )之間的 **payoff (marginal contribution)** 之差
* 如果 j = h，理所當然 ${mv}^i_{j\rightarrow h } = 0$
* 如果 agent $a_i$ 從 $C_j$ 移動到 $C_h$ 後，不滿足 budget constraint，則 ${mv}^i_{j\rightarrow h } = 0$
* 假設現在的 Coalition structure 為: $C_0 = \{a_1,a_5\}, C_1 = \{a_2,a_4\}, C_2 = \{a_3\}$
* 則 ${mv}^2_{1\rightarrow 2 }$ = $\sigma_2(a_2,C^\prime_2) - \sigma_1(a_2,C_1) = (10 - 1) - (13 - 11) = 9 - 2 = 7$
* 因為 agent $a_i$ 的移動，coalition $C_j$ 和 $C_h$ 的成員會因此改變，這也代表 $C_j$ 和 $C_h$ 成員的 marginal contribution 也會因此改變

---

考慮一個 Nash Equilibrium solution $S：C_0 = \{a_1,a_5\}, C_1 = \{a_2,a_3\}, C_2 = \{a_4\}$
* 在此解中，所有 agent 的 movement value 都 $\le 0$
* $a_2$：${mv}^2_{1\rightarrow 0 } = -9,\ {mv}^2_{1\rightarrow 1 } =\ \ 0\ ,\ {mv}^2_{1\rightarrow 2} = -7$
* $a_3$：${mv}^3_{1\rightarrow 0 } = -5,\ {mv}^3_{1\rightarrow 1 } =\ \ 0\ ,\ {mv}^3_{1\rightarrow 2} = -5$
* $a_4$：${mv}^4_{2\rightarrow 0 } = -8,\ {mv}^4_{2\rightarrow 1 } = -8,\ {mv}^4_{2\rightarrow 2} = 0$
* $a_1$ 和 $a_5$ 因為 budget 限制，沒有辦法再被 assign 到任何一個 coalition ，因此他們的 movement value = 0
* 此時系統的 utility $\phi(S) = 17 + 8 = 25$ 為 optimal，cost $P(S) = 4 + 2 + 3 = 9$
* **optimal solution 必為 NE，反過來不成立**

---
### Feasible Movement

* 不違反 budget 限制的 movement 即為 feasible movement
---

## Section 5 : The proposed CF algorithm

### Cost-Efficiency (CP 值)


* 概念同 CP 值
* j $=$ 0 代表 agent 一開始從 dummy coalition 出發， CP 值為 movement value / cost
* j $\ne$ 0 代表 agent 已經被 assign 過， CP 值為 movement value
* 其他代表 agent 還沒被 assign，而且是 unfeasible movement，則 CP 值為 0
---
### CF Algorithm


分成三個階段：

**1. Calculation**
* 算出所有 agent $a_i$ 從目前的 coalition $j$ 到其他可到達的 coalition $h$ 的 CP 值 ${ce}^i_{j\rightarrow h}$

**2. Selection**
* 挑選所有 CP 值中，最大的那個 ${ce}^{i^*}_{S(i^*)\rightarrow h^*}$
* 最大的 ${ce}^{i^*}_{S(i^*)\rightarrow h^*} <= 0$ ：表示系統到達 NE

**3. Assignment**
* 最大的 ${ce}^{i^*}_{S(i^*)\rightarrow h^*} > 0$ ：表示系統還有進步空間，agent $a_i^*$ 會從 $C_{j^*}(j^*=S(i^*))$ 轉移到 $C_{h^*}$
* 這意味著 ${mv}^{i^*}_{S(i^*)\rightarrow h^* }$ 必 $\ge 0$，且必為 feasible
* 更新 coalition 成員、以及系統剩餘 budget

---
### Efficient update of cost efficiency
因為並不是所有 agent 的 movement value 在每回合都會變動，為了節省計算資源，演算法只更改：

1. 因為只有 $C_{j^*}$ 和 $C_{h^*}$ 的成員改變，所以更新此兩 coalition 所有成員到其他 coalition 之 CP 值
2. 其他 agent 到 $C_{j^*}$ 和 $C_{h^*}$ 的 CP 值也需更新
3. 所有加入後會讓 budget 爆掉的 agent，其 CP 值都 $= 0$

---
### Illustration of CF Algorithm

* 一開始 $S：C_0 = \{a_1,a_2,a_3,a_4,a_5\}\ ,\ C_1 = \{\}\ ,\ C_2 = \{\}\ , P(S) = 0\ , \phi(S) = 0$
(a.) $S：C_0 = \{a_1,a_2,a_4,a_5\}\ ,\ C_1 = \{a_3\}\ ,\ C_2 = \{\}\ , P(S) = 2\ ,\ \phi(S) = 8$
(b.) $S：C_0 = \{a_1,a_2,a_5\}\ ,\ C_1 = \{a_3\}\ ,\ C_2 = \{a_4\}\ , P(S) = 5\ ,\ \phi(S) = 16$
(c.) $S：C_0 = \{a_1,a_5\}\ ,\ C_1 = \{a_2,a_3\}\ ,\ C_2 = \{a_4\}\ , P(S) = 9\ ,\ \phi(S) = 25$
(d.) 所有 CP 值都 $\le 0$ ，達到 NE

---
### GreedyNE* algorithm
* 跟 CF 唯一的差別在於 GreedyNE* 並沒有考慮 agent 的 cost ，也就是不算 CP 值，而是計算 movement value
* 會在後面與 CF 演算法做比較

---
## Section 6 : Properties of CF algorithm

### Flexibility to perform local search

* 如果沒有事先 input 初始的 coalition structure， CF 會預設所有 agent 都在 dummy coalition
* 如果有初始的 coalition structure， CF 會在每一回合試圖增加總體 utility，直到系統達到 NE，或是時間上限

---
### Solution quality

* 只要不提早中斷程式，CF 回傳的 coalition structure 必為 NE (證明略)
* 只要初始的 input 是 valid 的， CF 回傳的 coalition structure 也必為 valid (證明略)

---
### Monotonicity
* CF 是一個 anytime monotonic 的 algorithm (證明略)
* anytime monotonic
* 如果 CF 在第 $l$ 回合被終止，則形成的 coalition structure $S^l$ 其 system utility 必 $\ge$ 在更早第 $k$ 回合形成的 coalition structure $S^k$ 之 system utility，$(l>k)$
---
### Complexity
* m agents and n tasks
* CF 每一回合的 worst case 為 $O(m\cdot n)$
* 因為每回合最多要計算 $m\cdot (n+1)$ 個 CP 值 ($C_0 \sim C_n$ 有 n+1 個 coalition)
---
## Section 7 : Experiments and evaluation

### Benchmark algorithms
* GreedyNE*
* GA
* Random

### Experimental results
* 跑 100 次取平均
* 時間限制 1000 秒
* 20 種 capabilities
* 隨機生成每個 task 和 agent 的 capabilities [0,20]
* agent 在每個 capability 的能力由 0~10 隨機生成
* graph density $d = |T|/2$
* 用來表示每個 agent 可以選擇/執行的 task 數量，或者是說可以加入的 coalition 數量
* cost 跟 agent 的能力成正比，並且控制在 [1,20]
* agent $|A| = 3 \cdot |T|$

#### General performance
* budget $B = 5 \cdot |T|$
* task $|T| \in \{100,200,...,1000\}$


* 所有的 benchmark 的結果都比 Rand 好
* 在 task = 1000 時， CF 的 utility 達到 60000，而其他 benchmark都未達 CF 的 2/3
* GA 要跑很久，比其他 benchmark 都要久
* GA-mid 是用 GA 跑得跟 CF 一樣時間後停下來的結果


* 當 task 比較小，CF 和 GA 的 utiility 都很接近 optimal
* 當 task 越來越大，CF 開始表現得比 GA 還好

#### Different variations of agent cost
* $|T| = 100, B = 5\cdot |T|, v\in \{0,0.1,...,1\}$

* variation 由小到大代表 agent 的 cost 跟自身能力的程度從緊密相關到隨機
* 因為 CF 會考慮 CP值 ，所以當 variation 越大， CF 和 GA、GreedyNE* 之間的差距會越來越明顯

#### Different budget states
* $|T| = 100, |A| = 300, v = 0.3$, budget rate = $B/|T|$

* budget 越大代表系統越寬裕
* 系統 budget 越緊繃， CF 與其他 benchmark 的差距就越大，因為 CF 有考慮 CP 值

---
[HomePage]: https://hackmd.io/V22Sk3kRS8-sP2QUWPnjww#-%E5%9C%98%E5%92%AA%E5%A0%B1%E5%91%8A