Online Matching and Ad Allocation by Aranyak Mehta | Chap. 3.1 - 3.2


表題論文[PDF](http://algomagic.com/41870-16.pdf)の輪読会、3.1-3.2章の発表資料です。

# Chap.3 Online Bipartite Matching

- オンライン２部マッチングは `Karp et al. (1990)` によって提案された
	- ` > problem statement: U (the boys) and V (the girls)`
- ２部グラフ $G(U, V, E)$
	- $U$ : known vertexs
	- $V$ : オンラインで到着するvertexs
	- $E$ : すでに作られたMatchings
- 到着した $v \in V$ はもし隣接する $u \in U$ が存在したらマッチング可能
- 一度作られたマッチは取り消しできない
- マッチングのサイズを最大にするのを目的とする
- 以下、競合比 (competitive ratio) については[前回資料](http://www.slideshare.net/tsubosaka/onlinematching)を参照のこと
- Online Bipartite Matchingで検索すると、大学の講義資料も多々見つかる[link](https://www.google.co.jp/webhp?sourceid=chrome-instant&ion=1&espv=2&ie=UTF-8#q=online+bipartite+deterministic+algorithm&start=10)

## Chap.3.1 Adversarial Order

![image](https://qiita-image-store.s3.amazonaws.com/0/5950/14ffcf16-f240-b24a-ce3b-0641d4b1d11c.png)



### GREEDY 

- GREEDYアルゴリズム : 到着した $v$ に対してマッチング可能な $u$があればマッチングさせる

- Deterministic Algorithm（決定的アルゴリズム）でまず考えてみる。
- 決定的、とはinputに対してあらかじめ結果が決まっていること。
- adversarialな状況では、最悪となるようにマッチングが行われる
- GREEDYのアルゴリズムは以下
	
![Kobito.kUrJUV.png](https://qiita-image-store.s3.amazonaws.com/0/5950/d009a2db-623e-c26b-1022-4c701941bfa3.png "Kobito.kUrJUV.png")


- 図(a), 図(b)の黒線がedge。図(b)の状態を隣接行列で表すと、図(c)となる。この図で1はエッジを表す。
- 図(a)の状況でadversarialを考えると、v1に対してu2がマッチングされる。そのため、v2に対してマッチングはできない。
- GREEDYではこれ以上edgeが追加できない極大マッチングとなるはず。よって`Theorem 1.2`より、competitive ratioは $\frac{1}{2}$
	- よって、

```
Theorem 3.1
決定的アルゴリズムでは競合比の上限は 1/2 となり、GREEDYは 1/2.
```

### RANDOM
- RANDOMアルゴリズム : 到着した $v$ に対して、マッチング可能な $u$ 群からランダムにマッチング対象を引き当てる
- 単純な乱択アルゴリズム
- 決定的アルゴリズムと異なり、入力に対してランダムにマッチングを決定する
- この場合、$\frac{1}{2}$よりは悪くならない

![Kobito.pobW4d.png](https://qiita-image-store.s3.amazonaws.com/0/5950/c8d7afe9-f2c6-f0a2-2316-3ce5187a56ce.png "Kobito.pobW4d.png")

- これを使うと、 図3.1の左では競合比は $\frac{3}{4}$ となる
- しかし、上図のように２部クリークがあるようなグラフにおいて、V1群とU2群がマッチングされてしまった場合、 $\frac{1}{2} + o(1)$となる。
	- クリーク: 任意のV1群頂点と任意のU2群頂点の間に枝が存在すること
- 基本的には極大マッチングなので、最悪は $\frac{1}{2}$
- 多くの場合は $\frac{1}{2}$ しか達成できない

```
Theorem 3.2
RANDOMの競合比は 1/2
```


## Chap.3.1.2 RANKING: An Optimal Algorithm

- RANKING
	- `correlated randomness` を考慮すれば、RANDOMより改善する、はず
	- `Karp et al. (1990)` により考案
	- 競合比 $1 - \frac{1}{e} \simeq 0.63$ となる
	- あらかじめ、 $U$ の順列 $\pi$ をランダムに選定
	- $v$ に対して $\pi(u)$ の最小値となる $u$ とマッチング
	- 全ての $v \in V$ について、同じ $u \in U$を使用することになるので、correlated randomnessが存在する


```
Theorem 3.3
RANKINGはadversarialな状況において競合比の上限は 1 - 1/e となる
```

- Miss event $(\pi, u^*)$ はn個の Match event $(\pi^{(i)}, u_i)$ と対応付けることが出来る ( $u_i \in U$ )
- よって

```math
\forall t \in [n]:\space n \cdot {\rm Pr[ Miss\, event\, at\, position\,} t] \leq \sum_{s \leq t} {\rm Pr[Match\, event\, at\, position\,} s]
```

- $x_t\, =\, {\rm Pr[Match\, event\, at\, position\,} t]$ とおくと

```math
\forall t:\, 1 - x_t\, \leq \frac{1}{n} \sum_{s \leq t} x_s
```

- Factor-Revealing LPを使うと、

```math

ALG = \sum_t x_t \geq (1 - 1/e) n
\\
OPT = n
```

- よって最悪 $1 - \frac{1}{e}$

![image](https://qiita-image-store.s3.amazonaws.com/0/5950/bd235e02-c9ca-d47a-245b-337aeabf9534.png)


- Yao's lemma

- 乱択アルゴリズムでは、1 - 1/eを超えることは出来ない

# Chap.3.2 Random Order

- GREEDY with random order は RANKING with adversarial でシミュレート出来る

```
Theorem 3.4
GREEDY with random orderで、 競合比 1 - 1/eを達成できる。
決定的アルゴリズムでは最高3/4, 乱択アルゴリズムでは5/6となる
```

- RANKING with random orderでは最悪 1 - 1/e (Karande et al. etc.)

```
Theorem 3.5
RANKING with random orderにより、競合比0.696を出せる。
もし G(U,V,E)が k個の disjoint perfect matchingであるならば、上限 1 - 1/sqrt(k) となる。
```

![image](https://qiita-image-store.s3.amazonaws.com/0/5950/6e42c939-69d6-dac0-cd90-5f6b6207fe0b.png)