---
lang: ja
tags: MTNS-2022, lecture, linear programming
---
# 2022年度 交通社会システム論<br>第10回：割当問題とオークション(2) 線形計画問題としての割当問題 | Assignment Problem as Linear Programming Problem
[ポータルへ戻る](https://hackmd.io/@nagae/MTNS_2022)
<div style="text-align: center">

このページへは以下のQRコードまたはURLからアクセスできます：

<code style="font-size:20pt">https://hackmd.io/@nagae/MTNS_2022-Ch09</code>
</div>

# この回で学ぶこと | What you will learn in this session
1. 本来は二値線形計画問題として定式化される割当問題が，等価な線形計画問題に帰着する．
The assignment problem, originally formulated as a binary programming problem, is reduced to an equivalent linear programming problem.
2. 線形計画問題として定式化された割当問題の双対問題が，財の価格を明示的な未知変数として社会的余剰(の上限値)を推定する問題として解釈できる．
The dual of the equivalent linear programing problem can be interpreted as an estimation problem of the upper bound of the social benefit with the prices of the goods as explicit unknowns.

# 割当問題と等価な線形計画問題 | Reduction of An Assignment Problem to An Equivalent Linear Programming

**特定の条件** の下では **割当問題** が **線形計画問題** (LP: linear programming) と等価になる
Under specific conditions, the assignment problem can be reduced to a linear programming, providing the following advantages:
- 最適割当を求めるのが **劇的にラク**(変数1万個の0-1整数計画問題より変数 100 万個の LP の方が解き易い)
Finding the optimal assignment is **dramatically easier** (LP with 1 million unknowns is easier to solve than binary programming with 10 thousand unknowns);
- 特定のケースではVCG価格(次回で解説)が **双対変数** として計算可能 (勝者の数だけ割当問題を解かなくてよい)
In certain cases, VGG prices (to be discussed next session) can be computed as **dual variables** (without solving assignment problems as many times as the winners).
- 直感的で実装し易い **競り上げオークションに** よって最適配分と価格を **同時** に求められる (Demange et al., 1986; Bikhchandani and Ostroy, 2002, 2006; de Vries et al., 2007)
The optimal assignment as well as the optimal prices can be obtained simultaneously via an ascending auction, which is intuitive and easy to implement (Demange et al., 1986; Bikhchandani and Ostroy, 2002, 2006; de Vries et al., 2007).

# 線形計画問題としての割当問題 | Assignment Problem as LP
- $\mathcal{N}$: 買手集合 | set of buyers
- $\mathcal{G}$: 財集合 | set of goods
- $d_{i}$： 財$i \in \mathcal{G}$ の供給量 | the supply of goods $i\in\mathcal{G}$
- $v_{ij}$: 買手$j \in \mathcal{N}$ の財$i \in \mathcal{G}$ に対する評価値(支払い意思額/留保価格) | the value (willingness to pay/reservation price) of buyer $j \in \mathcal{N}$ to goods $i \in \mathcal{G}$
- $x_{ij}$: 割当． 買手$j \in \mathcal{N}$ に財$i \in \mathcal{G}$ が配分されるなら1， そうでなければ0 | assignment. $x_{ij}=1$ if goods $i$ is assigned to buyer $j$ and $x_{ij}=0$ otherwise.

### 割当ルール | Regulation
1. 各買手$j \in \mathcal{N}$ には高々1つの財しか割当られない:
No more than one goods are assigned to each buyer:
$$
\sum_{i \in \mathcal{G}} x_{i, j} \leq 1, \quad \forall j \in \mathcal{N}.
$$
2. 各財$i \in \mathcal{G}$ は供給量までしか割り当てられない:
No more than the supply of each good is assigned:
$$
\sum_{j \in \mathcal{N}} x_{i, j} \leq d_{i}, \quad \forall i \in \mathcal{G}.
$$

## 二値線形計画問題としての割当問題 | Assignment Problem as A Binary Programming
$$\begin{align}
\max_{\boldsymbol{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}$$

## 連続緩和した線形計画問題としての割当問題 | A LP relaxation of Assignment Problem
$$\begin{align}
\max_{\boldsymbol{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]$)した線形計画問題と元の二値線形計画問題の **解が一致する** ことが保証される．以下，**単体法**をおさらいしながらこのことを説明していこう．
For above LP-relaxed assignment problem, the left-hand side coefficient matrix of the standard equality form is **total unimodular** and thus it is guaranteed that its solution is equivalent to that of the original problem. This can be explained by reviewing the simplex method.

## 割当問題(線形計画問題)の等式標準形 | Standard Equality Form of the LP-formulated Assignment Problem
- $\hat{\mathcal{N}} = \mathcal{N} \cup \{0\}$: もともとの買手集合に不在買手 $0$ を加えた **拡張買手集合** | set of the expanded buyer's, which is obtained by adding the "absent buyer" $\{0\}$ to the original buyers' set
- $\hat{\mathcal{G}} = \mathcal{G} \cup \{\emptyset\}$: もともとの財集合に空の財$\emptyset$ を加えた **拡張財集合** | set of the expanded goods, which is obtained by adding the "empty goods" $\emptyset$ to the original goods' set.
- $x_{i, 0}$ : 財$i \in \mathcal{G}$ のうち買手に割当られなかった余り | the number of goods $i \in \mathcal{G}$ not assigned to the buyers
- $x_{\emptyset, j}$: 空の財の割当． 買手$j \in \mathcal{N}$ にどの財も割り当てられなければ1，そうでなければ0となる | the assignment of empty goods to buyer $j$. $x_{\emptyset,j}=1$ if buyer $j$ is not assigned any goods, otherwise $x_{\emptyset,j}=0$.

The standard equality form of the LP-formulated Assignment Problem is:
$$\begin{align}
\min_{\boldsymbol{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}$$

## 等式標準形の例 | An Example of Standard Equality Form of Assignment Problem
買手集合$\mathcal{N} = \{1, 2, 3\}$, 財集合$\{A, B\}$の場合:
The case with buyers' set $\mathcal{N} = \{1, 2, 3\}$ and goods set $\{A, B\}$:
$$
%\begin{array}{crrrrrrrrrrrcl}
\begin{eqnarray}
\min_{\boldsymbol{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}
$$

ベクトル・行列で表現すれば，
The standard equality form can be denoted by using vector/matrix as follows:
$$
\min_{\boldsymbol{x}} \left\{
\left.\boldsymbol{c}^{\top} \boldsymbol{x} \right|
\boldsymbol{A} \boldsymbol{x} = \boldsymbol{b}, \,
\boldsymbol{x} \geq \boldsymbol{0}
\right\}
$$

## 基底解の実行可能性と最適性 | Feasibility and Optimality of Basic Solutions
**割当問題**の等式標準形は，$N=|\mathcal{N}\times\mathcal{G}| + |\mathcal{N}| + |\mathcal{G}|$次元の**未知変数**と$M = |\mathcal{N}| + |\mathcal{G}|$本の**等式制約**で構成される．
The standard equality form of the LP-formulated assignment problem consists of the unknown variables with $N=|\mathcal{N}\times\mathcal{G}| + |\mathcal{N}| + |\mathcal{G}|$ dimension, as well as the constraint with $M = |\mathcal{N}| + |\mathcal{G}|$ equalities.

上述の例では，$N = 11$, $M=5$．
In the above example, $N = 11$, $M=5$.

つまり「求めるべき未知変数の数$N$ > 方程式の数$M$」なので，等式制約だけから未知変数の全てを求めることはできない．
Since the number of unknowns to be determined, $N$, is larger than the number of equations $M$, it is not possible to determine all of the unknowns from the equality constraints alone.

線形計画問題の目的関数の等高線は係数$\boldsymbol{c}$を法線ベクトルとする平行線(超平面)なので，**最適解**は許容領域の**端点**のいずれか．この端点とは，許容領域を構成する超平面($i$番目超平面が$x_{i}=0$に対応する)が**交わってできる点**に他ならない．この交点を**基底解**と呼ぶ．
According to the LP theory, the optimal solution can be either one of the vertices of the feasible region polygon. Note that each vertex is an intersection of $N-M$ out of $N$ hyperplanes consisting the feasible region, where the $i$-th hyperplane corresponds to $x_{i}=0$.

**基底解**とその**最適性条件**は，次のように求められることを思い出して欲しい．
Remember that the basic solutions and their optimality can be obtained as follows.

未知変数$\boldsymbol{x}$ を $M$次元の**基底変数** $\boldsymbol{x}_{B}$と$(N-M)$次元の**非基底変数**$\boldsymbol{x}_{N}$に分解し，
Let decompose the unknown variable $\boldsymbol{x}$ into $M$-dimensional **basic variables** $\boldsymbol{x}_{B}$ and $(N-M)$-dimensional **non-basic variables** $\boldsymbol{x}_{N}$ and denote it as
$$\begin{equation}
\boldsymbol{x} = \left(\boldsymbol{x}_{B} | \boldsymbol{x}_{N}\right)
\end{equation}$$
と表すことにする．この分割に合わせて，目的関数および等式制約の左辺も，
According to this decomposition, the objective function as well as the left hand side of the equality constraint can be decomposed into
$$\begin{align}
\boldsymbol{c}^{\top} \boldsymbol{x}=z &\rightarrow \boldsymbol{c}_{B}^{\top} \boldsymbol{x}_{B} + \boldsymbol{c}_{N}^{\top} \boldsymbol{x}_{N} =z\\
\boldsymbol{A} \boldsymbol{x} = \boldsymbol{b} &\rightarrow \boldsymbol{A}_{B} \boldsymbol{x}_{B} + \boldsymbol{A}_{N} \boldsymbol{x}_{N} = \boldsymbol{b}
\end{align}$$
と分解できる．ここで，$\boldsymbol{c} = \left(\boldsymbol{c}_{B}|\boldsymbol{c}_{N}\right), \boldsymbol{A} = \left(\boldsymbol{A}_{B}|\boldsymbol{A}_{N}\right)$と分割しており，それぞれの次元は
where $\boldsymbol{c} = \left(\boldsymbol{c}_{B}|\boldsymbol{c}_{N}\right), \boldsymbol{A} = \left(\boldsymbol{A}_{B}|\boldsymbol{A}_{N}\right)$ and their dimensions are
$$\begin{align}
\boldsymbol{c}_{B} & \in \mathcal{R}^{M},&
\boldsymbol{c}_{N} & \in \mathcal{R}^{N-M}, &
\boldsymbol{A}_{B} & \in \mathcal{R}^{M\times{}M},&
\boldsymbol{A}_{N} & \in \mathcal{R}^{M\times{}(N-M)}
\end{align}$$
となる．$\boldsymbol{A}_{B}$を**基底行列**，$\boldsymbol{A}_{N}$を**非基底行列**と呼ぶ．
$\boldsymbol{A}_{B}$ is referred to as **basis matrix**, while $\boldsymbol{A}_{N}$ is referred to as **non-basis matrix**.

一般に，$\boldsymbol{A}$のランク(独立な行の数)が$M$であるとき(i.e. 全ての制約条件が互いに独立=冗長な制約条件が無いとき)，基底行列$\boldsymbol{A}_{B}$は逆行列$\boldsymbol{A}_{B}^{-1}$を持つ． このとき，等式制約より
In general, when $\boldsymbol{A}$ is full-rank (i.e. every equality constraints are independent each other), the basis matrix $\boldsymbol{A}_{B}$ is invertible and the basic variable can be denoted by
$$\begin{equation}
\boldsymbol{x}_{B} = \boldsymbol{A}_{B}^{-1} \boldsymbol{b} - \boldsymbol{A}_{B}^{-1} \boldsymbol{A}_{N} \boldsymbol{x}_{N}
\end{equation}$$
を得る．これを目的関数に代入すれば，
By substituting this to the objective function, we have
$$\begin{align}
z &= \boldsymbol{c}_{B}^{\top} \boldsymbol{x}_{B} + \boldsymbol{c}_{N}^{\top} \boldsymbol{x}_{N}\\
&= \boldsymbol{c}_{B}^{\top} \boldsymbol{A}_{B}^{-1} \boldsymbol{b} + \left(\boldsymbol{c}_{N}^{\top} - \boldsymbol{c}_{B}^{\top} \boldsymbol{A}_{B}^{-1} \boldsymbol{A}_{N} \right) \boldsymbol{x}_{N}\\
&= \boldsymbol{c}_{B}^{\top} \boldsymbol{A}_{B}^{-1} \boldsymbol{b} + \hat{\boldsymbol{c}}^{\top} \boldsymbol{x}_{N}
\end{align}$$
を得る．ここで，
where
$$\begin{equation}
\hat{\boldsymbol{c}} = \boldsymbol{c}_{N} - \boldsymbol{A}_{N}^{\top} \left(\boldsymbol{A}_{B}^{-1}\right)^{\top} \boldsymbol{c}_{B}
\end{equation}$$

ある分割$\boldsymbol{x} = \left(\boldsymbol{x}_{B} | \boldsymbol{x}_{N}\right)$に対して**非基底変数**を$\boldsymbol{x}_{N} = \boldsymbol{0}$とおいた解:
For a given decomposition $\boldsymbol{x} = \left(\boldsymbol{x}_{B} | \boldsymbol{x}_{N}\right)$, the solution by letting $\boldsymbol{x}_{N}=\boldsymbol{0}$:
$$\begin{equation}
(\boldsymbol{x}_{B} | \boldsymbol{x}_{N}) = \left(\left.\boldsymbol{A}_{B}^{-1} \boldsymbol{b}\right|\boldsymbol{0}\right)\end{equation}$$
を**基底解**と呼ぶ．非負制約$\boldsymbol{x}_{B} = \boldsymbol{A}_{B}^{-1}\boldsymbol{b} \geq \boldsymbol{0}$を満たす基底解は**実行可能**である． **許容基底解**に対して$\hat{\boldsymbol{c}} \geq \boldsymbol{0}$であるとき，**最適解**となる．
is referred to as **basic solution**. The basic solution is **feasible** is $\boldsymbol{x}_{B} = \boldsymbol{A}_{B}^{-1} \boldsymbol{b} \geq \boldsymbol{0}$. A feasible basic solution is optimal when $\hat{\boldsymbol{c}} \geq \boldsymbol{0}$.

## 線形計画問題が整数解を持つには | When LP has integer solution?
ここでは，表記を簡単にするために，基底行列$\boldsymbol{A}_{B} \in \mathcal{R}^{M\times M}$を$\boldsymbol{A}$と書いている．
In the following, the basis matrix $\boldsymbol{A}_{B} \in \mathcal{R}^{M\times M}$ is denoted as $\boldsymbol{A}$ for the notational simplicity.

一般に，$M$次元の線形方程式$\boldsymbol{A} \boldsymbol{x}= \boldsymbol{b}$の$m$番目の解 $x_{m}=\left(\boldsymbol{A}^{-1}\boldsymbol{b}\right)_{m}$は， **Cramer の公式**より，
In general, $m$-th solution of $M$-dimensional linear equation system $\boldsymbol{A x} = \boldsymbol{b}$, $x_{m} = \left(\boldsymbol{A}^{-1}\boldsymbol{b}\right)_{m}$, can be obtained by the following Cramer's rule:
$$\begin{equation}
x_{m} = \frac{\left|\boldsymbol{A}_{m}\right|}{\left|\boldsymbol{A}\right|}
\end{equation}$$
と得られる．ここで，$\boldsymbol{A}_{m}$は，$\boldsymbol{A}$の第$m$列を$\boldsymbol{b}$に置き換えたもの:
where $\boldsymbol{A}_{m}$ is $M$-dimensional regular matrix obtained by replacing $m$-th column of $\boldsymbol{A}$ by $\boldsymbol{b}$:
$$\begin{equation}
\boldsymbol{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}$$

$\boldsymbol{A}_{m}$の行列式は，**余因子展開**より，
The determinant of $\boldsymbol{A}_{m}$ is obtained by the following **cofactor expansions**:
$$\begin{equation}
\left|\boldsymbol{A}_{m}\right| = \sum_{n=1}^{M}(-1)^{n+m}b_{n}\left|\boldsymbol{A}_{n,m}\right|
\end{equation}$$
と求められる．ここで，$\boldsymbol{A}_{n,m}$は行列$\boldsymbol{A}$の第$n$行と第$m$列を取り除いて得られる小行列．
where $\boldsymbol{A}_{n, m}$ is a minor matrix obtained from $\boldsymbol{A}$ by removing $n$th row and $m$th column.

従って，以下が満足されるなら$\boldsymbol{x}=\boldsymbol{A}^{-1}\boldsymbol{b}$ は**整数**．
Accordingly, $\boldsymbol{x} = \boldsymbol{A}^{-1} \boldsymbol{b}$ is integer if the followings are satisfied:
- $|\boldsymbol{A}|$が$1$または$-1$ (the determinant $\left|\boldsymbol{A}\right|$ is either $1$ or $-1$)
- 任意の$n,m = 1, \cdots, M$について$\left|\boldsymbol{A}_{n,m}\right|$が整数 ($\left|\boldsymbol{A}_{n, m}\right|$ is integer for any $n, m=1, \cdots, M$)
- 任意の$m = 1, \cdots, M$について$b_{m}$が整数 ($b_{m}$ is integer for any $m=1, \cdots, M$)

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

A matrix $\boldsymbol{A}$ is unimodular if its determinant $|\boldsymbol{A}|$ is $1$, $0$, or $-1$. A matrix $\boldsymbol{A}$ is **total unimodular** if every square submatrix of $\boldsymbol{A}$, which is obtained from $\boldsymbol{A}$ by removing several rows and columns, is unimodular.
:::

線形計画問題
A linear programming problem:
$$\begin{equation}\min_{\boldsymbol{x}} \left\{\boldsymbol{c}^{\top} \boldsymbol{x} \left|\boldsymbol{A} \boldsymbol{x} = \boldsymbol{b}, \boldsymbol{x} \geq \boldsymbol{0} \right.\right\}\end{equation}$$
は，係数行列$\boldsymbol{A}$が**全単模**かつ$\boldsymbol{b}$が**整数**であるとき，常に**整数解**を持つ．
has an integer solution if $\boldsymbol{A}$ is unimodular and $\boldsymbol{b}$ is integer.

### 全単模性を持つ行列の例 | Examples of Total Unimodular Matrices
- 各買手に**高々1つの財しか配分されない(unit demand)割当問題**の係数行列(i.e. **本講義で扱う割当問題の解は==整数==**)
The coefficient matrix of an assignment problem with unit demand, that is, each buyer is assigned at most one goods. That is, the assignment problem in this lecture has an integer solution.
- 各列の非ゼロ要素($1$または$-1$)が2つ以下で，かつ，非ゼロ要素が2つある時はその和が$0$ (ネットワークの**リンク-ノード接続行列**).
A matrix with every column has at most two non-zero elements and, when there are two non-zero elements, their sum is 0. (A link-node incident matrix of network).

# 割当問題の双対問題 | Dual of Assignment Problem
### 主問題(割当問題) | Primal (Assignment) Problem
$$\begin{align}
\max_{\boldsymbol{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}$$
括弧内は対応する**双対変数**.
Variables in the parenthesis are corresponding dual variable.

### 双対問題 | Dual Problem
$$\begin{align}
\min_{\boldsymbol{p}, \boldsymbol{\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}$$

## 双対問題の経済学的解釈 | Economic Implication of Dual Problem
双対問題は，以下のように解釈できる:
The dual problem can be interpreted as follows:
:::success
財$i \in \mathcal{G}$の**価格**$p_{i}$，買手$j \in \mathcal{N}$の**最大利得** $\pi_{j}$ を未知変数とし，
**価格$\boldsymbol{p}$の下で実現し得る社会的余剰$\sum \pi_{j} + \sum d_{i} p_{i}$の上限値**を見積る問題

The estimation of the **upper bound** of the social benefit $\sum_{j} \pi_{j} + \sum_{i} d_{i} p_{i}$ with the **price** of goods $i \in \mathcal{G}$, $p_{i}$, and the **maximum payoff** of buyer $j \in \mathcal{N}$, $\pi_{j}$, as unknown variables.
:::

### $\boldsymbol{p}$と$\boldsymbol{\pi}$の関係 | Relationship between $\boldsymbol{p}$ and $\boldsymbol{\pi}$
任意の買手$j \in \mathcal{N}$について，制約条件$\pi_{j} + p_{i} \geq v_{ij}$より，
From the dual constraint $\pi_{j} + p_{i} \geq v_{ij}$ for buyer $j \in \mathcal{N}$,
$$\begin{equation}
\pi_{j} \geq \max_{i \in \mathcal{G}} \left\{v_{ij} - p_{i}\right\}
\end{equation}$$
である．さらに，非負制約$\pi_{j} \geq 0$より，
and from the non-negativity constraint $\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\}$は非負空間への射影演算子．
where $[z]_{+} = \max\{z, 0\}$ is a projection of $z$ on a non-negative space.

目的関数は$\pi_{j}$について単調増加のため，ある価格$\boldsymbol{p}$を与件とした時の$\pi_{j}$の最適解は
Since the dual objective linearly decreases with respect to $\pi_{j}$, the optimal solution of $\pi_{j}$ given a certain price $\boldsymbol{p}$ is
$$\begin{equation}
\pi_{j} = \left[\max_{i \in \mathcal{G}} \left\{v_{ij} - p_{i}\right\}\right]_{+}
\end{equation}$$
となる．これは，**買手$j$が価格$\boldsymbol{p}$の下で実現し得る最大の利得**に他ならない．なお，どの財からも正の利得が得られない(価格$p_{i}$の方が評価値$v_{ij}$より高い)場合，買手$j$は市場から撤退することで，少なくともゼロ利得$(\pi_{j}=0)$を獲得できる．
which is nothing but the maximum payoff of buyer $j$ under price $\boldsymbol{p}$, while buyer $j$ yields at least zero payoff $\pi_{j}=0$ by leaving the market when he/she can not yield positive payoff from any goods (i.e. $v_{ij} < p_{j}$ for any $i \in \mathcal{G}$).

### 双対目的関数 | Dual Objective
$$\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}$で売却して得る収入の総和)であるから，目的関数は**社会的余剰**と解釈できる．
The first term is the buyers' total maximum payoff, while the second term is the sellers' total income (i.e. the sum of income of $d_{i}$ goods sold at price $p_{i}$). So, the dual objective can be regarded as the social benefit.

### 最適配分 | Optimal Assignment
**相補性定理**より， 主変数$\boldsymbol{x}$と双対変数$(\boldsymbol{p}, \boldsymbol{\pi})$ がともに**実行可能**であるとき，これらが**最適解**となるための**必要十分条件**は，
From Complementarity Theorem, a primal feasible solution $\boldsymbol{x}$ and a dual feasible solution $(\boldsymbol{p}, \boldsymbol{\pi})$ are optimal *if and only if*
$$\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}$$
あるいは，等価であるが，
or, equivalently,
$$\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}$$
すなわち，割当$\boldsymbol{x}$および価格/最大利得$(\boldsymbol{p}, \boldsymbol{\pi})$が最適となるのは，
In other words, the assignment $\boldsymbol{x}$ as well as the price and maximum payoff $(\boldsymbol{p}, \boldsymbol{\pi})$ are optimal if and only if
- 各買手には==利得が最大となる財==しか配分されない．
Each buyer is assigned only the goods that with the maximum payoff.
- ==需給が一致する財==にしか正の価格がつかない．
Each goods has a positive price only if its supply and demand matches.
- ==財が配分される買手==にしか正の利得が得られない．
Each buyer has a positive payoff only if he/she is assigned at least one goods.

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

# 2財3人の例 | An Example of Two Goods and Three Buyers
$\mathcal{N} = \{1, 2, 3\}, \mathcal{G} = \{A, B\}$とし，評価値$\{v_{ij}\}$が下記で与えられるとする．各財の供給量は，それぞれ，$d_{A} = d_{B} = 1$とする．
Suppose $\mathcal{N} = \{1, 2, 3\}, \mathcal{G} = \{A, B\}$ withunit supply $d_{A}=d_{B}=1$ and the following value $\{v_{ij}\}$.
||買手1<br>buyer 1|買手2<br>buyer 2|買手3<br>buyer 3|
|---|---|---|---|
|財$A$ |70 | 30 | 40|
|財$B$|60 | 20 | 10 |

### 主問題(割当問題) | Primal (Assignment) Problem
$$\begin{align}
\max_{\boldsymbol{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}$$

- 最適解(optimal solution): $x_{B1}=x_{A3} = 1$
- 最適値(optimal value): $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 |

### 双対問題 | Dual Problem
$$\begin{align}
\min_{\boldsymbol{p}, \boldsymbol{\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}$$

価格$\boldsymbol{p}=(p_{A}, p_{B})$に対する各買手の最大利得:
Each buyer's maximum payoff for given price $\boldsymbol{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)$
- 買手の最大利得(buyers' maximum payoff): $(\pi_{1}, \pi_{2}, \pi_{3}) = (70, 30, 40)$
- 社会的便益(social benefit): $\pi_{1}+\pi_{2}+\pi_{3} + d_{A}p_{A} + d_{B}p_{B} = 70 + 30 + 40 + 0 + 0=140$.
### ■ $(p_{A},p_{B}) = (0,0)\rightarrow (10,0)$
- 買手の最大利得(buyers' maximum payoff): $(\pi_{1}, \pi_{2}, \pi_{3}) = (60, 20, 30)$
- 社会的便益(social benefit): $\pi_{1}+\pi_{2}+\pi_{3} + d_{A}p_{A} + d_{B}p_{B} =60 + 20 + 30 + 10 + 0 = 120$.

$(p_{A},p_{B}) = (0,0)\rightarrow (10,0)$ とした場合，**全ての買手の利得**が10づつ減少するのに対し，売手の収入の増加は$10$だけなので，目的関数が$20$減少する．
When the price is changes as $(p_{A},p_{B}) = (0,0)\rightarrow (10,0)$, the maximum payoff of all buyers decreases by $10$, while the seller's income increases by only 10. Therefore the dual objective decreases (the upper bound is improved) by 20.

### ■ $(p_{A},p_{B}) = (10,0)\rightarrow (10,10)$
- 買手の最大利得(buyers' maximum payoff): $(\pi_{1}, \pi_{2}, \pi_{3}) = (60, 20, 30)$
- 社会的便益(social benefit): $60 + 20 + 30 + 10 + 10 = 130$.

$(p_{A},p_{B}) = (10,0)\rightarrow (10,10)$とした場合，買手の利得は減少せず，売手の収入のみが$10$増えるため，目的関数が増えてしまう．
When the price is changed as $(p_{A},p_{B}) = (10,0)\rightarrow (10,10)$, the buyers' maximum payoff remains unchanged, while the buyer's income increases by $10$. The dual objective is increased (the upper bound is worsen).

### ■ $(p_{A},p_{B}) = (10,0)\rightarrow (20,10)$
- $(\pi_{1}, \pi_{2}, \pi_{3}) = (50, 10, 20)$
- 社会的便益(social benefit): $50 + 10 + 20 + 20 + 10 = 110$.

$(p_{A},p_{B}) = (10,0)\rightarrow (20,10)$とした場合，**全ての買手の利得**が10づつ減少するのに対し，売手の収入の増加は20だけなので，目的関数が減少する．
When the price is changes as $(p_{A},p_{B}) = (10,0)\rightarrow (20,10)$, the maximum payoff of all buyers is reduced by $10$, while the seller's income increases by 20. Therefore the dual objective decreases (the upper bound is improved) by 10 (from 120 to 110).

### ■ $(p_{A}, p_{B}) = (20, 10)\rightarrow(30,20)$
- 最大利得(maximum payoff): $(\pi_{1}, \pi_{2}, \pi_{3}) = (40, 0, 10)$
- 社会的便益(social benefit): $40 + 0 + 10 + 30 + 20 = 100$.

$(p_{A}, p_{B}) = (20, 10)\rightarrow(30,20)$とした場合，全ての買手の利得は10づつ減少するのに対して，売手の収入の増加は10だけなので，目的関数が減少する．
When the price is changes as $(p_{A},p_{B}) = (20,10)\rightarrow (30,20)$, the maximum payoff of all buyers is reduced by $10$, while the seller's income increase by 20. Therefore the dual objective decreases (the upper bound is improved) by 10 (from 110 to 110).

買手2は正の利得を得られないため市場から撤退する．これにより配分が可能となる．残った2人の買手で2つの財を配分できる．買手1にとって$A$, $B$のどちらからも最大の利得40を獲得できるが，買手3にとって最大の利得10を獲得できるのは財$A$だけ．買手2は財$A$, $B$ともに利得ゼロ．このため，買手3に財$A$，買手1に財$B$を配分するのが**最適解**．
At this price, Buyer 2 leaves the market as he/she can not yield positive payoff. This allows assignment. For Buyer 1, both $A$ and $B$ are indifferent and achieve the maximum payoff $40$, while Buyer 3 achieve the maximum payoff $10$ from $B$. Then it is optimal to assign $A$ to Buyer 3 and $B$ to Buyer 1.

### ■ $(p_{A},p_{B}) = (30,20)\rightarrow (50,40)$
- 最大利得(maximum payoff): $(\pi_{1}, \pi_{2}, \pi_{3}) = (20, 0, 0)$
- 社会的便益(social benefit): $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増えるので，目的関数が増加してしまう．
When the price is changes as $(p_{A},p_{B}) = (30, 20)\rightarrow (50,40)$, Buyer 2 and 3 leave the market to yield zero payoff (i.e. Buyer 1's maximum payoff is decreased by 20, while Buyer 2's maximum payoff is decrease by 10 and Buyer 3's maximum payoff remains unchanged). That is, the buyers' total maximum payoff decreases by $30$, while the seller's income increases by $40$ (the objective becomes worse).

# 練習問題 | Exercise
下記の2財4人からなる割当問題に対して，以下を答えよ．
Suppose the following 2-item and 4-buyer assignment and answer the questions:
1. 等価な線形計画問題の主問題および双対問題を書き下せ．
Write down the primal and dual of the equivalent linear programming.
2. 主問題および双対問題の最適解が相補性条件を満足することを示せ．
Show that the primal/dual optimal solutions satisfy the complementarity condition.

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