# マッチングゲームのポテンシャル関数
- $\mathcal{S} = \{1, \cdots, N\}$: 戦略（出かける日）の集合．
- $\boldsymbol{x} = (x_{i}: i \in \mathcal{S})$: 系の状態($x_{i}$: 戦略$i$を選択する利用者数)
- $\mathcal{X} = \left\{\boldsymbol{x}: \sum_{i \in \mathcal{S}} x_{i} = 1, \quad x_{i} \geq 0, \ \forall i \in \mathcal{S}\right\}$: 状態空間
- $F_{i}(\boldsymbol{x}) = v_{i} - p\left(1 - \sum_{j \in \mathcal{S}} q_{j,i} x_{j}\right)$: 状態が$\boldsymbol{x}$であるときの戦略$i$の期待利得．
- $v_{i}$: 戦略$i$固有の効用（$i$曜日に出かけることの効用）
- $p$: 基本運賃
- $q_{j,i} = \begin{cases} \alpha_{i} & i=j\\0&i \ne j\end{cases}$: 戦略$j$ の利用者とマッチした時の戦略$i$ の利用者の運賃の割引額．ここで，$0 < \alpha_{i}\leq 1$とする．

期待利得は以下のようにベクトル表現できる：
\begin{align}
\boldsymbol{F}(\boldsymbol{x}) &=
\begin{bmatrix}
F_{1}(\boldsymbol{x})\\ \vdots \\ F_{N}(\boldsymbol{x})
\end{bmatrix} \\&
= \begin{bmatrix}v_{1} \\ \vdots \\ v_{N}\end{bmatrix}-
p\left(\begin{bmatrix}1 \\ \vdots \\ 1\end{bmatrix}-\begin{bmatrix}
\alpha_{1} & \cdots & 0\\
\vdots & \ddots & \vdots \\
0 & \cdots & \alpha_{N}
\end{bmatrix}\begin{bmatrix} x_{1}\\ \vdots \\ x_{N}\end{bmatrix}\right)\\
&= \boldsymbol{v}-p\left(\boldsymbol{1}-\boldsymbol{Q} \boldsymbol{x}\right)
\end{align}$\boldsymbol{Q}$は非対角成分がゼロなので対称行列である（異なる曜日でマッチングした時には割引がゼロなので）．さらに，$0< \alpha_{i} \leq 1$より，正定値行列となることも保証できる．

## 相補性条件としての均衡条件
マッチング・ゲームの均衡条件を以下のように定義する：
::: success
**(Nash)均衡状態**：どの利用者にとっても，自分だけが戦略を変更することでそれ以上利得を改善できない状態．
:::
明らかに，均衡状態では以下の原則が成立する：
::: success
**Wardrop原則**： **均衡状態**において，選択されている戦略の利得は全て等しく，それより利得の小さい戦略は選択されない．
:::
選択されている戦略に共通する利得を**均衡利得** $\rho^{\ast}$ で表せば， Wardrop 原則（均衡条件）は，以下の **相補性条件 (complementarity conditions)** として記述できる:$$
\begin{cases}
x_{i}^{\ast} > 0 &\rightarrow F_{i}(\boldsymbol{x}^{\ast}) = \rho^{\ast} \\
x_{i}^{\ast} = 0 &\leftarrow F_{i}(\boldsymbol{x}^{\ast}) < \rho^{\ast}
\end{cases}, \quad \forall i \in \mathcal{S}.
$$
この条件は， $x_{i}^{\ast} \geq 0, F_{i}(\boldsymbol{x}^{\ast}) - \rho^{\ast}\leq 0$ かつ， $x_{i}^{\ast}$ および $F_{i}(\boldsymbol{x}^{\ast}) - \rho^{\ast}$ の内，少なくとも一方が0となることを意味している． 従って，以下のように記述できる：
$$\begin{cases}
x_{i}^{\ast} \left\{F_{i}(\boldsymbol{x}) - \rho^{\ast}\right\} = 0\\
x_{i}^{\ast} \geq 0, \quad F_{i}(\boldsymbol{x}) - \rho^{\ast} \leq 0
\end{cases}, \quad \forall i \in \mathcal{S}$$
いま，全ての $i \in \mathcal{S}$ について上記が成り立つならば，
$$
\sum_{i\in \mathcal{S}} x_{i}^{\ast} \left\{F_{i}(\boldsymbol{x}) - \rho^{\ast}\right\} =
{\boldsymbol{x}^{\ast}}^{\top} \left\{ \boldsymbol{F}(\boldsymbol{x}^{\ast}) - \boldsymbol{1} \rho^{\ast}
\right\}
= 0
$$
である．ここで，$\boldsymbol{1}$は全ての要素が1である$N$ 次元列ベクトル，$^{\top}$は転置記号である．

従って，均衡条件は，以下のようにベクトル表記することもできる：
$$
{\boldsymbol{x}^{\ast}}^{\top}\left\{ \boldsymbol{F}(\boldsymbol{x}^{\ast}) - \boldsymbol{1} \rho^{\ast}
\right\}= 0, \quad \boldsymbol{x}^{\ast} \geq \boldsymbol{0}, \quad \boldsymbol{F}(\boldsymbol{x}^{\ast}) - \boldsymbol{1} \rho^{\ast} \leq \boldsymbol{0}
$$

## 等価な最適化問題
マッチング均衡条件が以下の最適化問題の最適性条件（必要条件）となることを示そう：
\begin{align}
\text{[P0]} \quad
\min_{\boldsymbol{x}} \quad &
Z(\boldsymbol{x}) = - \frac{p}{2}\boldsymbol{x}^{\top} \boldsymbol{Q} \boldsymbol{x} - \boldsymbol{x}^{\top}\left(\boldsymbol{v}-\boldsymbol{1}p\right)\\
\text{s.t.} & \sum_{i \in \mathcal{S}} x_{i} - 1 = 0\\
& x_{i} \geq 0, \quad \forall i \in \mathcal{S}
\end{align}

まず，[P0]の目的関数の$x_{i}$についての導関数は，
\begin{align}
\frac{\partial Z(\boldsymbol{x})}{\partial x_{i}} &=
\frac{\partial}{\partial x_{i}}
\left(- \frac{p}{2}\sum_{j}\sum_{k} q_{ji} x_{j} x_{k} - \sum_{j} v_{j} x_{j} + p
\right)\\
&= - v_{i} + p\left(1 - \sum_{j} q_{ji} x_{j}\right)\\
&= - F_{i}(\boldsymbol{x})
\end{align}である． このとき，$-Z(\boldsymbol{x})$を，マッチングゲームの**ポテンシャル関数**と呼ぶ．

次に，[P0]の$\boldsymbol{x}$についての等式制約は，2つの不等式制約：
\begin{align}
\sum_{i\in\mathcal{S}} x_{i} \leq 1\\
\sum_{i\in\mathcal{S}} x_{i} \geq 1\\
\end{align}に分解できるから，[P0]は，等式制約を不等式制約に置き換えた問題:
\begin{align}
\text{[P1]} \quad
\min_{\boldsymbol{x}} \quad &
Z(\boldsymbol{x}) \\
\text{s.t.} & \sum_{i \in \mathcal{S}} x_{i} - 1 \leq 0\\
& \sum_{i \in \mathcal{S}} x_{i} - 1 \geq 0\\
& x_{i} \geq 0, \quad \forall i \in \mathcal{S}
\end{align}
と等価である．

最適化問題[P1]に対する Lagrangian を以下のように定義する：
\begin{multline}
L(\boldsymbol{x}, \rho^{-}, \rho^{+}) = -
\frac{p}{2}\boldsymbol{x}^{\top} \boldsymbol{Q} \boldsymbol{x} - \boldsymbol{x}^{\top}\left(\boldsymbol{v}-\boldsymbol{1}p\right) \\+ \rho^{-}
\left\{\sum_{i \in \mathcal{S}} x_{i}-1\right\}+\rho^{+}\left\{
1-\sum_{i \in \mathcal{S}} x_{i}
\right\}
\end{multline}
この Lagrangian の第1項および第2項は，もとの目的関数$Z(\boldsymbol{x})$であり，第3項および第4項は，それおれ，制約条件 $\sum_{i} x_{i} - 1\leq 0$ および $\sum_{i} x_{i} - 1\geq 0$を破った場合のペナルティと解釈できる． すなわち，
- $\sum_{i} x_{i} > 1$となる場合，その差分$\sum_{i}x_{i}-1$に係数$\rho^{-}$を乗じたペナルティが（最小化したい）目的関数に加算され，
- $\sum_{i} x_{i} < 1$となる場合，その差分$1-\sum_{i}x_{i}$に係数$\rho^{+}$を乗じたペナルティが目的関数に加算される．

ここで，ペナルティが相殺しないようにするためには，
- $\sum_{i}x_{i} \leq 1$となる時には$\rho^{-}=0$,
- $\sum_{i}x_{i} \geq 1$となる時には$\rho^{+}=0$

としておく必要がある． この条件は，
$$\begin{cases}
\rho^{-} > 0 \rightarrow \sum_{i} x_{i} = 1 \\
\rho^{-} = 0 \leftarrow \sum_{i} x_{i} < 1
\end{cases}\quad
\begin{cases}
\rho^{+} > 0 \rightarrow \sum_{i} x_{i} = 1 \\
\rho^{+} = 0 \leftarrow \sum_{i} x_{i} > 1
\end{cases}
$$あるいは，等価であるが，
$$\begin{split}
\rho^{-} \left(\sum_{i \in \mathcal{S}} x_{i} -1\right) = 0,
\quad \rho^{-} \geq 0, \quad \sum_{i \in \mathcal{S}} x_{i}-1\leq 0\\
\rho^{+} \left(1-\sum_{i \in \mathcal{S}} x_{i} \right) = 0,
\quad \rho^{+} \geq 0, \quad 1-\sum_{i \in \mathcal{S}} x_{i}\leq 0
\end{split}$$と書ける（これも相補性条件である）．

このとき，問題[P1]は，未知変数を$(\boldsymbol{x}, \rho)$とし，その**非負条件のみ**を制約として目的関数$L(\boldsymbol{x}, \rho)$を最小化させる以下の問題に帰着する:
\begin{align}
\text{[P2]} \quad \min_{\boldsymbol{x}, \rho^{-}, \rho^{+}}
& L(\boldsymbol{x}, \rho^{-}, \rho^{+})\\
\text{s.t.} \quad &\boldsymbol{x} \geq \boldsymbol{0} \\
&\rho^{-}, \rho^{+} \geq 0
\end{align}

非負制約のみが与えられた問題[P2]の最適性条件は，以下のように記述できる：
\begin{align}
&
\begin{cases}
x_{i} > 0 &\rightarrow \frac{\partial L}{\partial x_{i}} = \frac{\partial Z(\boldsymbol{x})}{\partial x_{i}} + (\rho^{-}-\rho^{+})= 0 \\
x_{i} = 0 &\leftarrow \frac{\partial L}{\partial x_{i}} = \frac{\partial Z(\boldsymbol{x})}{\partial x_{i}} + (\rho^{-}-\rho^{+}) > 0
\end{cases}, \quad \forall i \in \mathcal{S}\\
&\begin{cases}
\rho_{i}^{-} > 0 &\rightarrow \frac{\partial L}{\partial \rho^{-}}=\sum_{i} x_{i} - 1= 0\\
\rho_{i}^{-} = 0 &\leftarrow \frac{\partial L}{\partial \rho^{-}}= \sum_{i} x_{i} - 1< 0
\end{cases}\\
&\begin{cases}
\rho_{i}^{+} > 0 &\rightarrow \frac{\partial L}{\partial \rho^{+}}=1 - \sum_{i} x_{i} = 0\\
\rho_{i}^{+} = 0 &\leftarrow \frac{\partial L}{\partial \rho^{+}}=1 - \sum_{i} x_{i} < 0
\end{cases}
\end{align}
このうち，2つ目および3つ目の式は，ペナルティの係数$\rho$が満たすべき相補性条件に他ならない． さらに，1つ目の式は，$\rho = \rho^{-}-\rho^{+}$とすれば，
$$
\begin{cases}
x_{i} \left\{-F_{i}(\boldsymbol{x})+\rho\right\}= 0, \\
x_{i} \geq 0, \, -F_{i}(\boldsymbol{x})+\rho \geq 0
\end{cases}, \quad i \in \mathcal{S}
$$となる．これは，均衡条件に他ならない．

## 最適化問題の解法
問題[P0]の目的関数は非凸関数（凹関数）であり，汎用ソルバで解くことは難しい．そこで，[清水・長江(2020)](https://doi.org/10.2208/jscejipm.76.3_264)が提案する Frank-Wolfe 法を用いた解法を開発する． この手続きでは，目的関数を一次近似（線形近似）して得られる線形計画問題（補助問題）を用いて，均衡解に収束するような解のシーケンス$\boldsymbol{x}^{(1)}, \boldsymbol{x}^{(2)}, \cdots,\boldsymbol{x}^{(k)}$を生成する．

いま，$k$回目の繰返しにおける暫定解 $\boldsymbol{x}^{(k)}$ の周りで目的関数を Taylor 展開すれば，
\begin{multline}
Z(\boldsymbol{y}) = Z(\boldsymbol{x}^{(k)}) + \nabla Z(\boldsymbol{x}^{(k)})^{\top} (\boldsymbol{y} - \boldsymbol{x}^{(k)}) \\+ \frac{1}{2} (\boldsymbol{y} - \boldsymbol{x}^{(k)})^{\top} \nabla^{2} Z(\boldsymbol{y}^{(k)}) (\boldsymbol{y} - \boldsymbol{x}^{(k)}) + O(|(\boldsymbol{y} - \boldsymbol{x}^{(k)})|^{2})
\end{multline}となる．ただし，$O(|\boldsymbol{z}|^{2})$は $\boldsymbol{z}^{\top}\boldsymbol{z}$ より高次の項である．このうち，2次以上の項を無視して目的関数を一次近似したもの：\begin{equation}
\hat{Z}(\boldsymbol{y}) = Z(\boldsymbol{x}^{(k)}) + \nabla Z(\boldsymbol{x}^{(k)})^{\top} (\boldsymbol{y} - \boldsymbol{x}^{(k)})
\end{equation}を最小化するように $\boldsymbol{y} \in \mathcal{X}$ を決定する問題（**補助問題**)を考えよう． この式の右辺第1項やおよび$\nabla Z(\boldsymbol{x}^{(k)})^{\top} \boldsymbol{x}^{(k)}$は未知変数$\boldsymbol{y}$によらない定数項だから，補助問題は，以下の線形計画問題：
\begin{align}
\text{[Aux$^{(k)}$]} \quad \min_{\boldsymbol{y}} \quad &\nabla Z(\boldsymbol{x}^{(k)})^{\top}\boldsymbol{y}\\
\text{s.t.} \quad & \sum_{i \in \mathcal{S}} y_{i} = 1\\
& y_{i} \geq 0 \quad \forall i \in \mathcal{S}
\end{align}
に帰着する．後述するように，この補助問題は極めて容易に解くことができる．

$k$回目繰返しにおいて得られる補助問題[Aux$^{(k)}$]の解を$\boldsymbol{y}^{(k)}$とすれば，解の降下方向は
$$\boldsymbol{d}^{(k)} = \boldsymbol{y}^{(k)} - \boldsymbol{x^{(k)}}$$で表される． こうして得られた補助解$\boldsymbol{y}^{(k)}$と現在の暫定解$\boldsymbol{x}^{(k)}$との線形結合として新しい暫定解を得ることにしよう：\begin{align}
\boldsymbol{x}^{(k+1)} &:= (1-\alpha) \boldsymbol{x}^{(k)} + \alpha \boldsymbol{y}^{(k)}\\
&= \boldsymbol{x}^{(k)} + \alpha \boldsymbol{d}^{(k)}
\end{align}ここで，$0 \leq \alpha \leq 1$はステップ・サイズであり，新しい暫定解における目的関数値$Z(\boldsymbol{x}^{(k+1)})$が最小となるように決定される．

### 最適ステップ・サイズの計算方法
簡単のため，
$$
\hat{Z}(\alpha) = Z(\boldsymbol{x}^{(k)} + \alpha \boldsymbol{d}^{(k)})
$$と記述する．この式の右辺を$\boldsymbol{x}^{(k)}$の周りで Taylor 展開すれば，$$\hat{Z}(\alpha) = Z(\boldsymbol{x}^{(k)}) + \alpha {\boldsymbol{d}^{(k)}}^{\top}\nabla Z(\boldsymbol{x}^{(k)}) + \frac{\alpha^{2}}{2} {\boldsymbol{d}^{(k)}}^{\top} \nabla^{2} Z(\boldsymbol{x}^{(k)}) \boldsymbol{d}^{(k)}\\
$$となる($Z$は二次関数なので，右辺は近似ではなく，恒等式であることに注意されたい)． その$\alpha$についての導関数は，
$$\begin{align}\frac{\mathrm{d} \hat{Z}}{\mathrm{d} \alpha} &= {\boldsymbol{d}^{(k)}}^{\top} \nabla Z(\boldsymbol{x}^{(k)}) + \alpha {\boldsymbol{d}^{(k)}}^{\top} \nabla^{2}Z(\boldsymbol{x}^{(k)}) \boldsymbol{d}^{(k)}
\\
&= A + \alpha B
\end{align}$$
となる．ただし，$$\begin{align}
A &= {\boldsymbol{d}^{(k)}}^{\top} \nabla Z(\boldsymbol{x}^{(k)}) = {\boldsymbol{d}^{(k)}}^{\top} , &
B &= {\boldsymbol{d}^{(k)}}^{\top} \nabla^{2}Z(\boldsymbol{x}^{(k)}) \boldsymbol{d}^{(k)} \\
&=- {\boldsymbol{d}^{(k)}}^{\top}\boldsymbol{F}(\boldsymbol{x}^{(k)})
&&=-p {\boldsymbol{d}^{(k)}}^{\top} \boldsymbol{Q} \boldsymbol{d}^{(k)}
\end{align}$$とした． これより，最適なステップ・サイズは，以下のように求められる：$$
\alpha^{\ast} = \begin{cases}
0 & \text{if } \left.\frac{\mathrm{d} \hat{Z}}{\mathrm{d} \alpha}\right|_{\alpha=0}=A < 0\\
1 & \text{if } \left.\frac{\mathrm{d} \hat{Z}}{\mathrm{d} \alpha}\right|_{\alpha=1}=A + B > 0\\
-\frac{A}{B} & \text{otherwise}
\end{cases}
$$
ただし， $B=0$の場合は，
$$
\alpha^{\ast} = \begin{cases}
0 & \text{if } \left.\frac{\mathrm{d} \hat{Z}}{\mathrm{d} \alpha}\right|_{\alpha=0}=A \leq 0\\
1 & \text{if } \left.\frac{\mathrm{d} \hat{Z}}{\mathrm{d} \alpha}\right|_{\alpha=1}=A > 0\\
\end{cases}
$$
とする．
### 補助問題の解法
補助問題[Aux$^{(k)}$]は， 単体上で線形関数$$
\nabla Z(\boldsymbol{x}^{k})^{\top} \boldsymbol{y}
= - \boldsymbol{F}(\boldsymbol{x}^{(k)}) \boldsymbol{y}
= - \sum_{i=1}^{K} F_{i}(\boldsymbol{x}^{(k)}) y_{i}
$$を最小化させる問題であるため， その解は， 貪欲法で極めて容易に求められる．すなわち， 最大の利得を$F^{\ast} = \displaystyle\max_{i\in \mathcal{S}} F_{i}(\boldsymbol{x}^{(k)})$ で表し， 利得が最大となる戦略数を$N^{\ast} = \#\left\{i: F_{i}(\boldsymbol{x}^{(k)}) = F^{\ast}\right\}$ とすれば，
$$
y_{i}^{\ast} = \begin{cases}
1/N^{\ast} & \text{if } F_{i}(\boldsymbol{x}^{(k)}) = F^{\ast} \\
0 & \text{if } F_{i}(\boldsymbol{x}^{(k)}) < F^{\ast}.
\end{cases}
$$すなわち，利得を最大とする戦略だけに全ての利用者を割り当てた(利得が最大となる戦略が複数存在する場合は按分した)ものが補助問題の解である．

### 解法の手続き
以上より，問題[P0]の解法は，下記のように整理できる：

- Step 0: (初期化)
適当な初期解 $\boldsymbol{x}^{(0)} \in \mathcal{X}$ を与える． $k:=1$ とする．
- Step 1: (降下方向の決定)
現在の暫定解$\boldsymbol{x}^{(k)}$ の下で各戦略の利得$\boldsymbol{F}^{(k)} = \boldsymbol{F}(\boldsymbol{x}^{(k)})$を求め， 補助問題[Aux${(k)}$]の解$\boldsymbol{y}^{(k)}$ を貪欲法で求める． 降下方向を$\boldsymbol{d}^{(k)}:= \boldsymbol{y}^{(k)} - \boldsymbol{x}^{(k)}$ とする．
- Step 2: (ステップサイズの決定)
$$\begin{align}
A &= - {\boldsymbol{d}^{(k)}}^{\top}\boldsymbol{F}^{(k)}&
B &= - p{\boldsymbol{d}^{(k)}}^{\top} \boldsymbol{Q} \boldsymbol{d}^{(k)}\\
&= - \sum_{i \in \mathcal{S}} (y_{i}^{(k)}-x_{i}^{(k)}) F_{i}^{(k)}
&&= - p \sum_{i \in \mathcal{S}} \sum_{j \in \mathcal{S}} Q_{i,j}(y_{i}^{(k)}-x_{i}^{(k)})(y_{j}^{(k)}-x_{j}^{(k)})
\end{align}$$を求め，最適なステップサイズを以下のように計算する：
$$
\alpha^{\ast} = \begin{cases}
0 & \text{if } \left.\frac{\mathrm{d} \hat{Z}}{\mathrm{d} \alpha}\right|_{\alpha=0}=A < 0\\
1 & \text{if } \left.\frac{\mathrm{d} \hat{Z}}{\mathrm{d} \alpha}\right|_{\alpha=1}=A + B > 0\\
-\frac{A}{B} & \text{otherwise}
\end{cases}
$$
ただし， $B=0$の場合は，
$$
\alpha^{\ast} = \begin{cases}
0 & \text{if } \left.\frac{\mathrm{d} \hat{Z}}{\mathrm{d} \alpha}\right|_{\alpha=0}=A \leq 0\\
1 & \text{if } \left.\frac{\mathrm{d} \hat{Z}}{\mathrm{d} \alpha}\right|_{\alpha=1}=A > 0\\
\end{cases}
$$
- Step 3: (解の改訂)
新しい暫定解を
$$
\boldsymbol{x}^{(k+1)}:= \boldsymbol{x}^{(k)} + \alpha^{\ast} \boldsymbol{d}^{(k)}
$$
とする．
- Step 4: (収束判定)
新旧の暫定解$\boldsymbol{x}^{(k+1)}$と$\boldsymbol{x}^{(k)}$とで解が大きく改善されていなければ収束と判定して終了．そうでなければ，$k:=k+1$として Step 1 へ．

Step 4 の判定基準としては，例えば，以下のようなものがある：
$$\begin{align}
\left\|\boldsymbol{x}^{(k+1)}-\boldsymbol{x}^{(k)}\right\| &< \epsilon_{1} & \text{(解の変化量の絶対値)}\\
\frac{\left\|\boldsymbol{x}^{(k+1)}-\boldsymbol{x}^{(k)}\right\|}
{\left\|\boldsymbol{x}^{(k)}\right\|} &< \epsilon_{2}& \text{(解の変化率)}\\
\frac{Z(\boldsymbol{x}^{(k)})-Z(\boldsymbol{x}^{(k-1)})}{Z(\boldsymbol{x}^{(k)})} &< \epsilon_{3} & \text{(目的関数の変化率)}
\end{align}$$