---
lang: ja
tags: OptMech-2021, lecture
---
# 2021年度 知的システム<br>第10回：割当問題とオークション(2) 線形計画問題としての割当問題
[ポータルへ戻る](https://hackmd.io/@nagae/OptMech_2021)
<div style="text-align: center">

このページへは以下のQRコードまたはURLからアクセスできます：
<code style="font-size:20pt">https://hackmd.io/@nagae/OptMech_2021-Ch09</code>
</div>

# この回で学ぶこと
1. 本来は二値線形計画問題として定式化される割当問題が，等価な線形計画問題に帰着する．
2. 線形計画問題として定式化された割当問題の双対問題が，財の価格を明示的な未知変数として買手の利得と社会的余剰(の上限値)を推定する問題として解釈できる．

# 割当問題と等価な線形計画問題

**特定の条件** の下では **割当問題** が **線形計画問題** (LP: linear programming) と等価になる
- 最適割当を求めるのが **劇的にラク**(変数1万個の0-1整数計 画問題より変数 100 万個の LP の方が解き易い)
- 特定のケースではVCG価格(次回で解説)が **双対変数** として計算可能 (勝者の数だけ割当問題を解かなくてよい)
- 直感的に理解し易い **競り上げオークションに** よって最適配分と価格を **同時** に求められる (Demange et al., 1986; Bikhchandani and Ostroy, 2002, 2006; de Vries et al., 2007) → 第9回で解説した手続きの理論的根拠

# 線形計画問題としての割当問題
- $\mathcal{N}$: 買手集合
- $\mathcal{G}$: 財集合
- $d_{i}$： 財$i \in \mathcal{G}$ の供給量
- $v_{ij}$: 買手$j \in \mathcal{N}$ の財$i \in \mathcal{G}$ に対する評価値(支払い意思額/留保価格)
- $x_{ij}$: 割当． 買手$j \in \mathcal{N}$ に財$i \in \mathcal{G}$ が配分されるなら1， そうでなければ0．

### 割当ルール
1. 各買手$j \in \mathcal{N}$ は高々1つの財しか割当られない:
$$
\sum_{i \in \mathcal{G}} x_{i, j} \leq 1
$$
2. 各財$i \in \mathcal{G}$ は供給量までしか割り当てられない:
$$
\sum_{j \in \mathcal{N}} x_{i, j} \leq d_{i}
$$

## 二値線形計画問題としての割当問題
$$\begin{align}
\max_{\mathbf{x}} &\sum_{i \in \mathcal{G}} \sum_{j \in \mathcal{N}} v_{ij} x_{ij} \\
\text{s.t. } \quad &
\sum_{i \in \mathcal{G}} x_{i, j} \leq 1 && \forall j \in \mathcal{N} \\&
\sum_{j \in \mathcal{N}} x_{i, j} \leq d_{i} && \forall i \in \mathcal{G} \\&
x_{i, j} \in \{0, 1\} && \forall (i,j) \in \mathcal{G} \times \mathcal{N}
\end{align}$$

## 連続緩和した線形計画問題としての割当問題
$$\begin{align}
\max_{\mathbf{x}} &\sum_{i \in \mathcal{G}} \sum_{j \in \mathcal{N}} v_{ij} x_{ij} \\
\text{s.t. } \quad &
\sum_{i \in \mathcal{G}} x_{i, j} \leq 1 && \forall j \in \mathcal{N} \\&
\sum_{j \in \mathcal{N}} x_{i, j} \leq d_{i} && \forall i \in \mathcal{G} \\&
\color{red}{x_{i, j} \geq 0} && \forall (i,j) \in \mathcal{G} \times \mathcal{N}
\end{align}$$

上述の割当問題は **等式標準形** の左辺係数行列が **全単模(total unimodular)** であるため，0-1整数制約($x_{ij} \in \{0, 1\}$)を **連続緩和** ($x_{i,j} \in [0, 1]$)した線形計画問題と元の二値線形計画問題の **解が一致する** ことが保証される → 以下，**単体法**をおさらいしながらこのことを説明していこう．

## 割当問題(線形計画問題)の等式標準形
- $\hat{\mathcal{N}} = \mathcal{N} \cup \{0\}$: もともとの買手集合に不在買手 $0$ を加えた **拡張買手集合**
- $\hat{\mathcal{G}} = \mathcal{G} \cup \{\emptyset\}$: もともとの財集合に空の財$\emptyset$ を加えた **拡張財集合**
- $x_{i, 0}$ : 財$i \in \mathcal{G}$ のうち買手に割当られなかった余り
- $x_{\emptyset, j}$: 空の財の割当． 買手$j \in \mathcal{N}$ にどの財も割り当てられなければ1，そうでなければ0となる．

$$\begin{align}
\min_{\mathbf{x}} & -\sum_{i \in \mathcal{G}} \sum_{j \in \mathcal{N}} v_{ij} x_{ij} \\
\text{s.t. } \quad &
\sum_{i \in \mathcal{G}} x_{i, j} + x_{\emptyset,j} = 1 && \forall j \in \mathcal{N} \\&
\sum_{j \in \mathcal{N}} x_{i, j} + x_{i, 0} = d_{i} && \forall i \in \mathcal{G} \\&
x_{i, j}, x_{\emptyset, j}, x_{i,0} \geq 0 && \forall (i,j) \in \mathcal{G} \times \mathcal{N}
\end{align}$$

## 等式標準形の例
買手集合$\mathcal{N} = \{1, 2, 3\}$, 財集合$\{A, B\}$の場合:
$$
%\begin{array}{crrrrrrrrrrrcl}
\begin{eqnarray}
\min_{\mathbf{x}} & -v_{A,1} x_{A,1} &-v_{B,1} x_{B,1} & - v_{A,2}x_{A,2} & - v_{B,2}x_{B,2} & -v_{A,3} x_{A,3} & - v_{B,3} x_{B,3}\\
\text{s.t.} & x_{A,1} &+ x_{B,1} & & & & & +x_{\emptyset, 1} & & &&&=1\\
& & & x_{A,2} &+x_{B,2} & & && +x_{\emptyset, 2} & &&&=1\\
& & & & & x_{A,3} &+ x_{B,3} & & &+x_{\emptyset,3} &&&= 1\\
& x_{A, 1}& & +x_{A, 2}& &+x_{A,3}& & & & &+x_{A, 0} & &=d_{A}\\
& & x_{B, 1}& & +x_{B, 2}& & +x_{B,3}& & & & &+x_{B, 0} &=d_{B}\\
& x_{A,1}, & x_{B,1}, & x_{A,2}, & x_{B,2}, & x_{A,3}, & x_{B,3}, & x_{\emptyset,1}, & x_{\emptyset, 2},& x_{\emptyset, 3} & x_{A, 0}, & x_{B, 0} &\geq 0
\end{eqnarray}
%\end{array}
$$

ベクトル・行列で表現すれば，
$$
\min_{\mathbf{x}} \left\{
\left.\mathbf{c}^{\top} \mathbf{x} \right|
\mathbf{A} \mathbf{x} = \mathbf{b}, \,
\mathbf{x} \geq \mathbf{0}
\right\}
$$

## 基底解の許容性と最適性
**割当問題**の等式標準形は，$N=|\mathcal{N}\times\mathcal{G}| + |\mathcal{N}| + |\mathcal{G}|$次元の**未知変数**と$M = |\mathcal{N}| + |\mathcal{G}|$本の**等式制約**で構成される．

上述の例では，$N = 11$, $M=5$．

つまり「求めるべき未知変数の数$N$ > 方程式の数$M$」なので，等式制約だけから未知変数の全てを求めることはできない．

線形計画問題の目的関数の等高線は係数$\mathbf{c}$を法線ベクトルとする平行線(超平面)なので，**最適解**は許容領域の**端点**のいずれか．この端点とは，許容領域を構成する超平面($i$番目超平面が$x_{i}=0$に対応する)が**交わってできる点**に他ならない．この交点を**基底解**と呼ぶ．

**基底解**とその**最適性条件**は，次のように求められる．
未知変数$\mathbf{x}$ を $M$次元の**基底変数** $\mathbf{x}_{B}$と$(N-M)$次元の**非基底変数**$\mathbf{x}_{N}$に分解し，
$$\begin{equation}
\mathbf{x} = \left(\mathbf{x}_{B} | \mathbf{x}_{N}\right)
\end{equation}$$
と表すことにする．この分割に合わせて，目的関数および等式制約の左辺も，
$$\begin{align}
\mathbf{c}^{\top} \mathbf{x}=z &\rightarrow \mathbf{c}_{B}^{\top} \mathbf{x}_{B} + \mathbf{c}_{N}^{\top} \mathbf{x}_{N} =z\\
\mathbf{A} \mathbf{x} = \mathbf{b} &\rightarrow \mathbf{A}_{B} \mathbf{x}_{B} + \mathbf{A}_{N} \mathbf{x}_{N} = \mathbf{b}
\end{align}$$
と分解できる．ここで，$\mathbf{c} = \left(\mathbf{c}_{B}|\mathbf{c}_{N}\right), \mathbf{A} = \left(\mathbf{A}_{B}|\mathbf{A}_{N}\right)$と分割しており，それぞれの次元は
$$\begin{align}
\mathbf{c}_{B} & \in \mathcal{R}^{M},&
\mathbf{c}_{N} & \in \mathcal{R}^{N-M}, &
\mathbf{A}_{B} & \in \mathcal{R}^{M\times{}M},&
\mathbf{A}_{N} & \in \mathcal{R}^{M\times{}(N-M)}
\end{align}$$
となる．$\mathbf{A}_{B}$を**基底行列**，$\mathbf{A}_{N}$を**非基底行列**と呼ぶ．

一般に，$\mathbf{A}$のランク(独立な行の数)が$M$であるとき(i.e. 全ての制約条件が互いに独立=冗長な制約条件が無いとき)，基底行列$\mathbf{A}_{B}$は逆行列$\mathbf{A}_{B}^{-1}$を持つ． このとき，等式制約より
$$\begin{equation}
\mathbf{x}_{B} = \mathbf{A}_{B}^{-1} \mathbf{b} - \mathbf{A}_{B}^{-1} \mathbf{A}_{N} \mathbf{x}_{N}
\end{equation}$$
を得る．これを目的関数に代入すれば，
$$\begin{align}
z &= \mathbf{c}_{B}^{\top} \mathbf{x}_{B} + \mathbf{c}_{N}^{\top} \mathbf{x}_{N}\\
&= \mathbf{c}_{B}^{\top} \mathbf{A}_{B}^{-1} \mathbf{b} + \left(\mathbf{c}_{N}^{\top} - \mathbf{c}_{B}^{\top} \mathbf{A}_{B}^{-1} \mathbf{A}_{N} \right) \mathbf{x}_{N}\\
&= \mathbf{c}_{B}^{\top} \mathbf{A}_{B}^{-1} \mathbf{b} + \mathbf{\pi}^{\top} \mathbf{x}_{N}
\end{align}$$
を得る．ここで，
$$\begin{equation}
\mathbf{\pi} = \mathbf{c}_{N} - \mathbf{A}_{N}^{\top} \left(\mathbf{A}_{B}^{-1}\right)^{\top} \mathbf{c}_{B}^{\top}
\end{equation}$$
は**相対費用係数**と呼ばれる．

ある分割$\mathbf{x} = \left(\mathbf{x}_{B} | \mathbf{x}_{N}\right)$に対して**非基底変数**を$\mathbf{x}_{N} = \mathbf{0}$とおいた解:
$$\begin{equation}
(\mathbf{x}_{B} | \mathbf{x}_{N}) = \left(\left.\mathbf{A}_{B}^{-1} \mathbf{b}\right|\mathbf{0}\right)\end{equation}$$
を**基底解**と呼ぶ．非負制約$\mathbf{x}_{B} = \mathbf{A}_{B}^{-1}\mathbf{b} \geq \mathbf{0}$を満たす基底解は**許容**である． **許容基底解**に対して**相対費用係数**が$\mathbf{\pi} \geq \mathbf{0}$であるとき，**最適解**となる．

## 線形計画問題が整数解を持つには
ここでは，表記を簡単にするために，$M$次元正方行列$\mathbf{A}_{B} \in \mathcal{R}^{M\times M}$を$\mathbf{A}$と書いている．

一般に，$M$次元の線形方程式$\mathbf{A} \mathbf{x}= \mathbf{b}$の$m$番目の解 $x_{m}=\left(\mathbf{A}^{-1}\mathbf{b}\right)_{m}$は， **Cramer の公式**より，$$\begin{equation}
x_{m} = \frac{\left|\mathbf{A}_{m}\right|}{\left|\mathbf{A}\right|}
\end{equation}$$
と得られる．ここで，$\mathbf{A}_{m}$は，$\mathbf{A}$の第$m$列を$\mathbf{b}$に置き換えたもの:
$$\begin{equation}
\mathbf{A}_{m} =\begin{bmatrix}
a_{1,1} & \cdots & a_{1,m-1} & b_{1} & a_{1,m+1} & \cdots & a_{1,M}\\
\vdots & & \vdots & \vdots & \vdots & & \vdots\\
a_{M,1} & \cdots & a_{M,m-1} & b_{M} & a_{M,m+1} & \cdots & a_{M,M}\\
\end{bmatrix}
\end{equation}$$

$\mathbf{A}_{m}$の行列式は，**余因子展開**より，
$$\begin{equation}
\left|\mathbf{A}_{m}\right| = \sum_{n=1}^{M}(-1)^{n+m}b_{n}\left|\mathbf{A}_{n,m}\right|
\end{equation}$$
と求められる．ここで，$\mathbf{A}_{n,m}$は行列$\mathbf{A}$の第$n$行と第$m$列を取り除いて得られる小行列．

従って，
- $|\mathbf{A}|$が$1$または$-1$.
- 任意の$n,m = 1, \cdots, M$について$\left|\mathbf{A}_{n,m}\right|$が整数
- 任意の$m = 1, \cdots, M$について$b_{m}$が整数

ならば，$\mathbf{x}=\mathbf{A}^{-1}\mathbf{b}$は**整数**．

## 全単模性(total unimodularity)
:::info
ある行列$\mathbf{A}$からいくつかの行と列を取り除いてできる**任意の正方行列**の行列式が1,0または-1であるとき，$\mathbf{A}$は **全単模 (total unimodular)** であると言う．その定義上，全単模行列は，1,0または-1のみを要素に持つ．
:::

線形計画問題
$$\begin{equation}\min_{\mathbf{x}} \left\{\mathbf{c}^{\top} \mathbf{x} \left|\mathbf{A} \mathbf{x} = \mathbf{b}, \mathbf{x} \geq \mathbf{0} \right.\right\}\end{equation}$$
は，係数行列$\mathbf{A}$が**全単模**かつ$\mathbf{b}$が**整数**であるとき，常に**整数解**を持つ．

### 全単模性を持つ行列の例
- 各買手に**高々1つの財しか配分されない(unit demand)割当問題**の係数行列(i.e. **本講義で扱う割当問題の解は==整数==**)
- 各列の非ゼロ要素($1$または$-1$)が2つ以下で，かつ，非ゼロ要素が2つある時はその和が$0$ (ネットワークの**リンク-ノード接続行列**).

# 双対問題
## 割当問題と双対問題
### 主問題(割当問題)
$$\begin{align}
\max_{\mathbf{x}} &\sum_{i \in \mathcal{G}} \sum_{j \in \mathcal{N}} v_{ij} x_{ij} \\
\text{s.t. } \quad &
\sum_{i \in \mathcal{G}} x_{i, j} \leq 1 && \forall j \in \mathcal{N} &&(\pi_{j})\\&
\sum_{j \in \mathcal{N}} x_{i, j} \leq d_{i} && \forall i \in \mathcal{G} &&(p_{i})\\&
x_{i, j} \geq 0 && \forall (i,j) \in \mathcal{G} \times \mathcal{N}
\end{align}$$
括弧内は対応する**双対変数**.

### 双対問題
$$\begin{align}
\min_{\mathbf{p}, \mathbf{\pi}} &\sum_{j \in \mathcal{N}} \pi_{j} + \sum_{i \in \mathcal{G}} d_{i} p_{i}\\
\text{s.t.} \quad &
\pi_{j} + p_{i} \geq v_{ij} && \forall i \in \mathcal{G}, \forall j \in \mathcal{N} && (x_{ij})\\
&\pi_{j} \geq 0 && \forall j \in \mathcal{N}\\
&p_{i} \geq 0 && \forall i \in \mathcal{G}
\end{align}$$

## 双対問題の経済学的解釈
双対問題は，以下のように解釈できる:
:::success
財$i \in \mathcal{G}$の**価格**を$p_{i}$，買手$j \in \mathcal{N}$の**利得**(の最大値)を$\pi_{j}$と見なせば，
**価格$\mathbf{p}$の下で実現し得る社会的余剰$\sum \pi_{j} + \sum d_{i} p_{i}$の上限値**を見積る問題
:::

### $\mathbf{p}$と$\mathbf{\pi}$の関係
任意の買手$j \in \mathcal{N}$について，制約条件$\pi_{j} + p_{i} \geq v_{ij}$より，
$$\begin{equation}
\pi_{j} \geq \max_{i \in \mathcal{G}} \left\{v_{ij} - p_{i}\right\}
\end{equation}$$
である．さらに，非負制約$\pi_{j} \geq 0$より，
$$\begin{equation}
\pi_{j} \geq \left[\max_{i \in \mathcal{G}} \left\{v_{ij} - p_{i}\right\}\right]_{+}
\end{equation}$$
である．ただし，$[z]_{+} = \max\{z,0\}$は非負空間への射影演算子．目的関数は$\pi_{j}$について単調のため，ある価格$\mathbf{p}$を与件とした時の$\pi_{j}$の最適値は
$$\begin{equation}
\pi_{j} = \left[\max_{i \in \mathcal{G}} \left\{v_{ij} - p_{i}\right\}\right]_{+}
\end{equation}$$
となる．これは，**買手$j$が価格$\mathbf{p}$の下で実現し得る最大の利得**に他ならない．なお，どの財からも正の利得が得られない(価格$p_{i}$の方が評価値$v_{ij}$より高い)場合，買手$j$は市場から撤退することで，少なくともゼロ利得$(\pi_{j}=0)$を獲得できる．

### 目的関数
$$\begin{equation}
\sum_{j \in \mathcal{N}} \pi_{j} + \sum_{i \in \mathcal{G}} d_{i} p_{i}
\end{equation}$$
のうち，第1項は**買手の(最大)利得の総和**であり，第2項は**売手の総収入**(i.e. $d_{i}$個の財$i$を価格$p_{i}$で売却して得る収入の総和)であるから，目的関数は**社会的余剰**と解釈できる．

### 最適配分
**相補性定理**より， 主変数$\mathbf{x}$と双対変数$(\mathbf{p}, \mathbf{\pi})$ がともに**実行可能**であるとき，これらが**最適解**となるための**必要十分条件**は，
$$\begin{align}
&\sum_{i \in \mathcal{G}} \sum_{j \in \mathcal{N}}x_{ij} \left(\pi_{j}+p_{i}-v_{ij}\right) = 0\\
&\sum_{i \in \mathcal{G}} p_{i}
\left(d_{i} - \sum_{j \in \mathcal{N}}x_{ij}\right) = 0\\
&\sum_{j \in \mathcal{N}} \pi_{j}
\left(1 - \sum_{i \in \mathcal{G}} x_{ij}\right) = 0
\end{align}$$
あるいは，等価であるが，
$$\begin{align}
&\begin{cases}
x_{ij} > 0 &\rightarrow \pi_{j} = v_{ij} - p_{i} \\
x_{ij} = 0 &\leftarrow \pi_{j} > v_{ij} - p_{i}
\end{cases}
&& \forall i \in \mathcal{G},
\forall j \in \mathcal{N},\\
&\begin{cases}
p_{i} > 0 &\rightarrow \sum_{i \in \mathcal{N}} x_{ij} = d_{i} \\
p_{i} = 0 &\leftarrow \sum_{i \in \mathcal{N}} x_{ij} < d_{i}
\end{cases}
&& \forall i \in \mathcal{G},\\
&\begin{cases}
\pi_{j} > 0 &\rightarrow \sum_{j \in \mathcal{G}} x_{ij} = 1 \\
\pi_{j} = 0 &\leftarrow \sum_{j \in \mathcal{G}} x_{ij} < 1
\end{cases}
&& \forall j \in \mathcal{N}
\end{align}$$
と表される． すなわち，割当$\mathbf{x}$および価格/最大利得$(\mathbf{p}, \mathbf{\pi})$が最適となるのは，
- 各買手には==利得が最大となる財==しか配分されない．
- ==需給が一致する財==にしか正の価格がつかない．
- ==財が配分される買手==にしか正の利得が得られない．

が満たされるとき，かつその時に限られる．

# 2財3人の例
$\mathcal{N} = \{1, 2, 3\}, \mathcal{G} = \{A, B\}$とし，評価値$\{v_{ij}\}$が下記で与えられるとする．各財の供給量は，それぞれ，$d_{A} = d_{B} = 1$とする．
||買手1|買手2|買手3|
|---|---|---|---|
|財$A$|70 | 30 | 40|
|財$B$|60 | 20 | 10 |

### 主問題(割当問題)
$$\begin{align}
\max_{\mathbf{x}} & 70x_{A1} + 60 x_{B1} + 30 x_{A2} + 20 x_{B2} + 40 x_{A3} + 10 x_{B3}
\\
\text{s.t.} &
x_{A1} + x_{B1} \leq 1 \qquad(\pi_{1})\\&
x_{A2} + x_{B2} \leq 1 \qquad(\pi_{2})\\&
x_{A3} + x_{B3} \leq 1 \qquad(\pi_{3})\\&
x_{A1} + x_{A2} + x_{A3} \leq 1 \qquad (p_{A})\\&
x_{B1} + x_{B2} + x_{B3} \leq 1 \qquad (p_{B})\\&
x_{A1}, x_{B1}, x_{A2}, x_{B2}, x_{A3}, x_{B3} \geq 0
\end{align}$$

- 最適解: $x_{B1}=x_{A3} = 1$
- 最適値: $60 + 40 = 100$

| |買手1|買手2|買手3|
|---|---|---|---|
|財$A$| 70 | 30 | <div style="background-color:orange">40</div>|
|財$B$|<div style="background-color:orange">60</div> | 20 | 10 |

### 双対問題
$$\begin{align}
\min_{\mathbf{p}, \mathbf{\pi}} & \pi_{1} + \pi_{2} + \pi_{3} + p_{A} + p_{B}\\
\text{s.t.} &
\pi_{1} + p_{A} \geq 70 \qquad (x_{A1})\\&
\pi_{1} + p_{B} \geq 60 \qquad (x_{B1})\\&
\pi_{2} + p_{A} \geq 30 \qquad (x_{A2})\\&
\pi_{2} + p_{B} \geq 20 \qquad (x_{B2})\\&
\pi_{3} + p_{A} \geq 40 \qquad (x_{A3})\\&
\pi_{3} + p_{B} \geq 10 \qquad (x_{B3})\\&
\pi_{1}, \pi_{2}, \pi_{3}, p_{A}, p_{B} \geq 0
\end{align}$$

価格$\mathbf{p}=(p_{A}, p_{B})$に対する各買手の最大利得:
- $\pi_{1} = \max\{70-p_{A}, 60-p_{B}, 0\}$
- $\pi_{2} = \max\{30-p_{A}, 20-p_{B}, 0\}$
- $\pi_{3} = \max\{40-p_{A}, 10-p_{B}, 0\}$

### ■ $(p_{A}, p_{B}) = (0,0)$の場合
$(\pi_{1}, \pi_{2}, \pi_{3}) = (70, 30, 40)$ で目的関数は $70 + 30 + 40 + 0 + 0=140$.
### ■ $(p_{A}, p_{B}) = (10,0)$の場合
$(\pi_{1}, \pi_{2}, \pi_{3}) = (60, 20, 30)$ で目的関数は $60 + 20 + 30 + 10 + 0 = 120$.

$(p_{A},p_{B}) = (0,0)\rightarrow (10,0)$ とした場合，**全ての買手の利得**が10づつ減少するのに対し，売手の収入の増加は10だけなので，目的関数が減少する．

### ■ $(p_{A}, p_{B}) = (10,10)$の場合
$(\pi_{1}, \pi_{2}, \pi_{3}) = (60, 20, 30)$ で目的関数は $60 + 20 + 30 + 10 + 10 = 130$.

$(p_{A},p_{B}) = (10,0)\rightarrow (10,10)$とした場合，買手の利得は減少せず，売手の収入のみが増えるため，目的関数が増えてしまう．

### ■ $(p_{A}, p_{B}) = (20,10)$の場合
$(\pi_{1}, \pi_{2}, \pi_{3}) = (50, 10, 20)$ で目的関数は $50 + 10 + 20 + 20 + 10 = 110$.

$(p_{A},p_{B}) = (10,0)\rightarrow (20,10)$とした場合，**全ての買手の利得**が10づつ減少するのに対し，売手の収入の増加は20だけなので，目的関数が減少する．

### ■ $(p_{A}, p_{B}) = (30,20)$の場合
$(\pi_{1}, \pi_{2}, \pi_{3}) = (40, 0, 10)$ で目的関数は $40 + 0 + 10 + 30 + 20 = 100$.

この時，買手1にとって$A$, $B$のどちらからも最大の利得40を獲得できるが，買手3にとって最大の利得10を獲得できるのは財$A$だけ．買手2は財$A$, $B$ともに利得ゼロ．このため，買手3に財$A$，買手1に財$B$を配分するのが**最適解**．

### ■ $(p_{A}, p_{B}) = (50,40)$の場合
$(\pi_{1}, \pi_{2}, \pi_{3}) = (20, 0, 0)$ で目的関数は $20 + 0 + 0 + 50 + 40 = 110$.

$(p_{A},p_{B}) = (30,20)\rightarrow (50,40)$とした場合，買手2と買手3は**市場から撤退して利得ゼロを獲得する**(i.e. 買手1の利得は20減少するが，買手3は利得が10だけ減少したところで市場から撤退してしまう)ので，買手の利得の総和は30しか減少しないのに対し，売手の収入は40増えるので，目的関数が増加してしまう．

# 練習問題
下記の2財4人からなる割当問題に対して，以下を答えよ．
1. 等価な線形計画問題の主問題および双対問題を書き下せ．
2. 主問題および双対問題の最適解が相補性条件を満足することを示せ．

||買手1|買手2|買手3|買手4|供給量|
|---|---|---|---|---|---|
|財$A$|100|50|90|120|1|
|財$B$|80|50|40|90|2|