非分割財の分配問題（住宅配分問題）

非分割財の分配問題

初期時点において社会が共同所有する複数の商品を、何らかのルールにもとづいてプレイヤーたちに分配しようとしている状況を想定します。ただし、問題としている商品を細かく分割できないものとします。また、商品を分配した後、複数の商品を所有するプレイヤーや、商品を所有しないプレイヤーが発生する可能性を排除します。加えて、プレイヤーたちは商品を獲得する手段として金銭などの分割可能な交換媒体を使うことはできないものとします。つまり、プレイヤーは特定の商品を獲得するために対価として金銭を支払ったり、逆に特定の商品を受け取ることを認める対価として金銭を受け取ることはできないということです。また、それぞれのプレイヤーは商品どうしを比較する選好、すなわち好みの体系を持っているものとします。選好の内容はプレイヤーごとに異なりますが、これはプレイヤーの私的情報であり、他のプレイヤーたちがそれを事前に観察することはできません。以上のような資源配分問題を住宅配分問題（house allocation problem）やランダム割り当て問題（random assignment problem）などと呼びますが、以降ではこれは非分割財の分配問題（indivisible goods allocation problem）と呼ぶこととします。

プレイヤー集合

非分割財の配分問題をモデルとして定式化します。まずはプレイヤーの表現です。非分割財の配分問題に参加するすべてのプレイヤーからなる集合をプレイヤー集合（player set）やプレイヤー空間（player space）などと呼び、これを、\begin{equation*}
I
\end{equation*}で表記します。特に、\(n\)人のプレイヤーが参加する場合、プレイヤー集合を、\begin{equation*}I=\left\{ 1,2,\cdots ,n\right\}
\end{equation*}と特定します。プレイヤー集合\(I\)に属する\(i\ \left( =1,2,\cdots ,n\right) \)番目のプレイヤーをプレイヤー\(i\)（player \(i\)）と呼びます。\(i\in I\)です。

限られた商品を誰に割り当てるかという問題は、分配の対象者が複数人存在することにより生じるため、プレイヤーの数が複数であることは基本的な条件となります。そこで、プレイヤーの人数\(n\)は\(2\)以上の整数であるものと仮定します。

商品集合

初期時点において社会的に保有され、分配の対象となるすべての商品からなる集合を、\begin{equation*}
H
\end{equation*}で表記します。商品集合\(H\)に属する\(k\ \left( =1,2,\cdots,n\right) \)番目の商品を、\begin{equation*}h_{k}\in H
\end{equation*}で表記し、これを商品\(k\)（good \(k\)）と呼びます。

多くの場合、プレイヤーの人数と商品の個数は同数であるものと仮定します。つまり、有限\(n\)人のプレイヤーが参加する場合のプレイヤー集合と商品集合は、\begin{eqnarray*}I &=&\left\{ 1,2,\cdots ,n\right\} \\
H &=&\left\{ h_{1},h_{2},\cdots ,h_{n}\right\}
\end{eqnarray*}です。このとき、以下の関係\begin{equation*}
\left\vert I\right\vert =\left\vert H\right\vert =n
\end{equation*}が成り立ちます。つまり、プレイヤーの人数と財の個数はともに\(n\)です。

商品を分配した結果、それぞれのプレイヤー\(i\in I\)は商品集合\(H\)の要素である商品を1つだけ需要します。

商品どうしを比較する選好関係

非分割財の分配問題において、それぞれのプレイヤー\(i\in I\)は商品集合\(H\)の要素である商品どうしを比較する選好関係（preference relation）を持っているものとみなし、それを、\begin{equation*}\succsim _{i}
\end{equation*}で表記します。具体的には、それぞれのプレイヤー\(i\)の選好関係\(\succsim _{i}\)は商品集合\(H\)上に定義された二項関係であり、任意の商品\(h,h^{\prime }\in H\)に対して、\begin{equation*}h\succsim _{i}h^{\prime }\Leftrightarrow \text{プレイヤー}i\text{は商品}h\text{を商品}h^{\prime }\text{以上に好む}
\end{equation*}を満たすものとして定義されます。

プレイヤー\(i\)の選好関係\(\succsim _{i}\)が与えられたとき、任意の商品\(h,h^{\prime}\in H\)に対して、\begin{equation*}h\succ _{i}h^{\prime }\Leftrightarrow h\succsim _{i}h^{\prime }\wedge \lnot
\left( h^{\prime }\succsim _{i}h\right)
\end{equation*}を満たすものとして商品集合\(H\)の新たな二項関係\(\succ _{i}\)が定義可能です。つまり、プレイヤー\(i\)にとって\(h\)が\(h^{\prime }\)以上に望ましく、なおかつ、\(h^{\prime }\)が\(h\)以上に望ましくない場合にはそのことを\(h\succ_{i}h^{\prime }\)で表記するということです。言い換えると、\(h\succ _{i}h^{\prime }\)が成り立つこととは、プレイヤー\(i\)にとって\(h\)が\(h^{\prime }\)よりも望ましいことを意味します。この二項関係\(\succ _{i}\)をプレイヤー\(i\)の狭義選好関係（strict preference relation）と呼びます。

プレイヤー\(i\)の選好関係\(\succsim _{i}\)が与えられたとき、任意の商品\(h,h^{\prime}\in H\)に対して、\begin{equation*}h\sim _{i}h^{\prime }\Leftrightarrow h\succsim _{i}h^{\prime }\wedge
h^{\prime }\succsim _{i}h
\end{equation*}を満たすものとして商品集合\(H\)の新たな二項関係\(\sim _{i}\)が定義可能です。つまり、プレイヤー\(i\)にとって\(h\)が\(h^{\prime }\)以上に望ましく、なおかつ、\(h^{\prime }\)が\(h\)以上に望ましい場合にはそのことを\(h\sim _{i}h^{\prime }\)で表記するということです。言い換えると、\(h\sim _{i}h^{\prime }\)が成り立つこととは、プレイヤー\(i\)にとって\(h\)と\(h^{\prime }\)が同じ程度望ましいことを意味します。この二項関係\(\sim _{i}\)をプレイヤー\(i\)の無差別関係（indifference relation）と呼びます。

すべてのプレイヤーの選好関係からなる組を、\begin{equation*}
\succsim _{I}=\left( \succsim _{i}\right) _{i\in I}
\end{equation*}で表記し、これを選好プロファイル（preference profile）と呼びます。プレイヤー\(i\)以外のプレイヤーたちの選好からなる組を、\begin{equation*}\succsim _{-i}=\left( \succsim _{j}\right) _{j\in I\backslash \left\{
i\right\} }
\end{equation*}で表記することとします。\(\succsim _{I}=\left( \succsim _{i},\succsim_{-i}\right) \)です。

多くの場合、任意のプレイヤー\(i\)の選好関係\(\succsim _{i}\)は以下の条件\begin{equation*}\forall h,h^{\prime }\in H:\left( h\succsim _{i}h^{\prime }\vee h^{\prime
}\succsim _{i}h\right)
\end{equation*}を満たすものと仮定します。つまり、2つの商品\(h,h^{\prime }\)が任意に与えられたとき、プレイヤー\(i\)は\(h\)を\(h^{\prime }\)以上に好むか、\(h^{\prime }\)を\(h\)以上に好むか、その少なくとも一方であるという仮定です。これを完備性（completeness）の仮定と呼びます。この仮定の意味を以下で解説します。

2つの商品\(h,h^{\prime }\in H\)を任意に選んだとき、論理的には以下の\(\left( a\right) \)から\(\left( d\right) \)の4通りが起こり得ます。ただし、\(1\)は真を表す真理値であり、\(0\)は偽を表す真理値です。

$$\begin{array}{cccccc}
\hline
\quad & h\succsim _{i}h^{\prime } & h^{\prime }\succsim _{i}h & h\sim _{i}h^{\prime } & h\succ _{i}h^{\prime } & h^{\prime }\succ _{i}h \\
\hline
\left( a\right) & 1 & 1 & 1 & 0 & 0 \\ \hline
\left( b\right) & 1 & 0 & 0 & 1 & 0 \\ \hline
\left( c\right) & 0 & 1 & 0 & 0 & 1 \\ \hline
\left( d\right) & 0 & 0 & 0 & 0 & 0 \\ \hline
\end{array}$$

\(\left( a\right) \)はプレイヤー\(i\)にとって\(h\)と\(h^{\prime }\)が同じ程度望ましい場合、\(\left( b\right) \)はプレイヤー\(i\)にとって\(h\)が\(h^{\prime }\)よりも望ましい場合、\(\left( c\right) \)はプレイヤー\(i\)にとって\(h^{\prime }\)が\(h\)よりも望ましい場合に相当します。一方、\(\left( d\right) \)では\(h\)と\(h^{\prime }\)の間の優劣に関する情報が存在しないため、この場合、そもそも\(h\)と\(h^{\prime }\)を比べることができません。ただ、\(\succsim _{i}\)が完備性を満たす場合には\(h\succsim _{i}h^{\prime }\)と\(h^{\prime }\succsim _{i}h\)の少なくとも一方が成り立つことが保証されるため、\(\left( d\right) \)が起こる可能性は排除されます。つまり、\(\succsim _{i}\)が完備性を満たす場合には、2つの商品\(h,h^{\prime }\)を任意に選んだとき、\(\left( a\right) ,\left( b\right) ,\left(c\right) \)の中のどれか1つが成り立つことが保証されます。言い換えると、\(h\sim _{i}h^{\prime }\)と\(h\succ _{i}h^{\prime}\)と\(h^{\prime }\succ _{i}h\)の中のどれか1つが必ず成り立つことが保証されるということです。完備性のもとでは、プレイヤーがどのような商品の組を提示された場合においても、迷うことなく両者の優劣を判断できることになります。

多くの場合、任意のプレイヤー\(i\)の選好関係\(\succsim _{i}\)は以下の条件\begin{equation*}\forall h,h^{\prime },h^{\prime \prime }\in H:\left( h\succsim _{i}h^{\prime
}\wedge h^{\prime }\succsim _{i}h^{\prime \prime }\Rightarrow h\succsim
_{i}h^{\prime \prime }\right)
\end{equation*}を満たすものと仮定します。つまり、3つの商品\(h,h^{\prime },h^{\prime \prime }\)が任意に与えられたとき、プレイヤー\(i\)は\(h\)を\(h^{\prime }\)以上に好み、\(h^{\prime }\)を\(h^{\prime \prime }\)以上に好む場合、\(h\)を\(h^{\prime \prime }\)以上に好むことが保証されるということです。これを推移性（transitivity）の仮定と呼びます。

推移性の意味を深く理解するために、完備性を満たすが推移性を満たさない選好関係\(\succsim _{i}\)のもとでどのような問題が生じ得るかを考えます。\(\succsim _{i}\)が推移性を満たさない場合には、推移性の定義の否定に相当する以下の命題\begin{equation}\exists h,h^{\prime },h^{\prime \prime }\in H:\left[ h\succsim _{i}h^{\prime
}\wedge h^{\prime }\succsim _{i}h^{\prime \prime }\wedge \lnot \left(
h\succsim h^{\prime \prime }\right) \right] \quad \cdots (1)
\end{equation}が成り立ちます。\(\succsim_{i}\)が完備性を満たす場合には、\(\left( 1\right) \)中の商品\(h,h^{\prime \prime }\)の間に以下の関係\begin{equation*}h^{\prime \prime }\succ h\Leftrightarrow \lnot (h\succsim h^{\prime \prime })
\end{equation*}が成り立つため（確認してください）、これを用いて\(\left( 1\right) \)を言い換えると、\begin{equation*}\exists h,h^{\prime },h^{\prime \prime }\in H:\left( h\succsim _{i}h^{\prime
}\wedge h^{\prime }\succsim _{i}h^{\prime \prime }\wedge h^{\prime \prime
}\succ h\right)
\end{equation*}を得ます。つまり、\(h\)を出発点としたとき、\(h^{\prime \prime }\)のほうが\(h\)よりも厳密に望ましく（\(h^{\prime \prime }\succ h\)）、さらに\(h^{\prime }\)は\(h^{\prime \prime }\)以上に望ましい（\(h^{\prime }\succsim _{i}h^{\prime \prime }\)）という形で、\(h\)を出発点にそれより厳密に望ましいか、あるいは同等以上の消費ベクトルへ移行することで\(h^{\prime }\)へ至ったにも関わらず、最初の\(h\)はこの\(h^{\prime }\)以上に望ましい（\(h\succsim _{i}h^{\prime }\)）という奇妙な状況が発生しています。つまり、\begin{equation*}\cdots \succ h\succsim h^{\prime }\succsim h^{\prime \prime }\succ h\succsim
h^{\prime }\succsim h^{\prime \prime }\succ h\succsim h^{\prime }\succsim
h^{\prime \prime }\succ \cdots
\end{equation*}という形でプレイヤーの選好が循環してしまうということです。選好関係に対して推移性の仮定を設けることは、こうした状況が発生する可能性を排除することを意味します。

プレイヤー\(i\)の選好関係\(\succsim _{i}\)が完備性と推移性をともに満たす場合には、つまり、\begin{eqnarray*}&&\left( a\right) \ \forall h,h^{\prime }\in H:\left( h\succsim
_{i}h^{\prime }\vee h^{\prime }\succsim _{i}h\right) \\
&&\left( b\right) \ \forall h,h^{\prime },h^{\prime \prime }\in H:\left(
h\succsim _{i}h^{\prime }\wedge h^{\prime }\succsim _{i}h^{\prime \prime
}\Rightarrow h\succsim _{i}h^{\prime \prime }\right)
\end{eqnarray*}がともに成り立つ場合には、\(\succsim _{i}\)を選好順序（preference ordering）や合理的な選好関係（rational preference relation）などと呼びます。

プレイヤー\(i\)の選好関係\(\succsim _{i}\)が選好順序であるものとします。このとき、2つの商品\(h,h^{\prime }\in H\)を任意に選ぶと、\(\succsim _{i}\)の完備性より\(h\)と\(h^{\prime }\)は比較可能です。さらに、3つ目の商品\(h^{\prime \prime }\in H\)を任意に選ぶと、やはり\(\succsim _{i}\)の完備性より\(h\)と\(h^{\prime \prime }\)は比較可能であり、\(h^{\prime }\)と\(h^{\prime \prime }\)は比較可能です。したがって、\(h,h^{\prime },h^{\prime \prime }\)の中の任意の2つは比較可能であり、さらに\(\succsim _{i}\)の推移性より、それらを循環しない形でプレイヤー\(i\)にとって望ましい順に並べることができます。4つ目以降の商品についても同様に考えると、結局、選好順序\(\succsim _{i}\)のもとでは、商品集合\(H\)の要素であるすべての商品を循環しない形で並べることができることになります。加えて、2つの商品\(h,h^{\prime }\in H\)を任意に選んだとき、選好順序\(\succsim_{i}\)のもとでは\(h\succ _{i}h^{\prime }\)または\(h^{\prime }\succ _{i}h\)または\(h\sim_{i}h^{\prime }\)の中のどれか1つが必ず成り立ちます。したがって、プレイヤー\(i\)の選好関係\(\succsim_{i}\)が選好順序である場合、プレイヤー\(i\)は\(\succ_{i}\)と\(\sim _{i}\)を用いて商品集合\(H\)に属するすべての商品を最も望ましいものから最も望ましくないものまで順番に並べることができます。例えば、\begin{equation*}h\succ _{i}h^{\prime }\sim _{i}h^{\prime \prime }\sim _{i}h^{\prime \prime
\prime }\succ _{i}h^{\prime \prime \prime \prime }\cdots
\end{equation*}という具合にです。

プレイヤー\(i\)の選好関係\(\succsim _{i}\)が選好順序であるものとします。その上で、場合によっては、任意の2つの商品\(h,h^{\prime }\in H\)の間に\(h\sim_{i}h^{\prime }\)という関係が成り立たないものと仮定します。つまり、プレイヤー\(i\)にとって同じ程度望ましい複数の商品が存在しないという仮定です。これを狭義選好の仮定（assumption of strict preference）と呼びます。このとき、任意の2つの商品\(h,h^{\prime }\)の間に\(h\succ _{i}h^{\prime }\)または\(h^{\prime }\succ _{i}h\)のどちらか一方が成り立つため、商品集合\(H\)の要素であるすべての商品を\(\succ _{i}\)だけを用いて一列に並べることができます。例えば、\begin{equation*}h\succ _{i}h^{\prime }\succ _{i}h^{\prime \prime }\succ _{i}h^{\prime \prime
\prime }\succ _{i}h^{\prime \prime \prime \prime }\cdots
\end{equation*}という具合にです。選好順序だけを仮定する場合、すべての商品を最も望ましいものから最も望ましくないものまで順番に並べることができますが、その中に同じ程度望ましい複数の商品が存在する可能性は排除されません。一方、選好順序に加えて狭義選好を仮定する場合、すべての商品を最も望ましいものから最も望ましくないものまで順番に並べることができ、なおかつ、その中に同じ程度望ましい複数の商品は存在しないことが保証されます。

配分集合

非分割財の分配問題において、プレイヤーたちに商品を分配することで生じ得る結果を配分（allocation）やマッチング（matching）などと呼びます。具体的には、プレイヤー集合\(I\)と商品集合\(H=\left\{ h_{i}\right\} _{i\in I}\)が与えられたとき、個々の配分は以下の条件\begin{eqnarray*}&&\left( a\right) \ \forall i\in I:a_{i}\in H \\
&&\left( b\right) \ \bigcup\limits_{i\in I}\left\{ a_{i}\right\} =H \\
&&\left( c\right) \ \forall i,j\in I:\left( i\not=j\Rightarrow
a_{i}\not=a_{j}\right)
\end{eqnarray*}を満たす組\begin{equation*}
a_{I}=\left( a_{i}\right) _{i\in I}
\end{equation*}として定義されます。ただし、\(a_{I}\)の成分である\(a_{i}\)は、配分\(a_{I}\)のもとでプレイヤー\(i\)に割り当てられる商品に相当します。

条件\(\left( a\right) \)は、配分においてそれぞれのプレイヤーに割り当てられる商品は、初期時点において社会的に保有されていることを意味します。条件\(\left( b\right) \)は、配分においてそれぞれの商品は必ず誰かに割り当てられる必要があることを意味します。条件\(\left( c\right) \)は、配分において同一の商品が異なるプレイヤーに割り当てられてはならないことを意味します。\(a_{I}\)が配分である場合、すなわち、\(a_{I}\)が上の条件をすべて満たす場合、それぞれのプレイヤー\(i\)に対して商品\(a_{i}\)を割り当てることが物理的に可能です。そのようなこともあり、配分のことを実現可能な配分（feasible allocation）と呼ぶこともあります。すべての配分からなる集合を、\begin{equation*}A
\end{equation*}で表し、これを配分集合（allocation set）やマッチング集合（set of matchings）などと呼びます。\(a_{I}\in A\)です。

配分どうしを比較する選好関係

それぞれのプレイヤー\(i\in I\)は商品どうしを比較する商品集合\(H\)上の選好関係\(\succsim _{i}\)を持っていますが、非分割財の分配問題において実現可能な結果が配分\(a_{I}\in A\)として表現されることを踏まえると、プレイヤー\(i\)は商品どうしを比較する選好\(\succsim _{i}\)だけでなく、配分どうしを比較する選好を持っていなければ、交換において実現し得る結果どうしを比較できないことになってしまいます。そこで、それぞれのプレイヤー\(i\)は配分どうしを比較する配分集合\(A\)上に定義された選好関係を持っているものとし、これを、\begin{equation*}\succsim _{i}^{A}
\end{equation*}で表記します。ただし、\(\succsim _{i}^{A}\)は\(A\)上に定義された二項関係であり、任意の配分\(a_{I},a_{I}^{\prime }\in A\)に対して、\begin{equation*}a_{I}\succsim _{i}^{A}a_{I}^{\prime }\Leftrightarrow \text{プレイヤー}i\text{は配分}a_{I}\text{を配分}a_{I}^{\prime }\text{以上に好む}
\end{equation*}を満たすものとして定義されます。

プレイヤー\(i\)が配分どうしを比較する選好関係\(\succsim _{i}^{A}\)が与えられたとき、任意の配分\(a_{I},a_{I}^{\prime }\in A\)に対して、\begin{equation*}h\succ _{i}^{A}h^{\prime }\Leftrightarrow h\succsim _{i}^{A}h^{\prime
}\wedge \lnot \left( h^{\prime }\succsim _{i}^{A}h\right)
\end{equation*}を満たすものとして配分集合\(A\)上の新たな二項関係\(\succ _{i}^{A}\)を定義します。また、任意の配分\(a_{I},a_{I}^{\prime }\in A\)に対して、\begin{equation*}h\sim _{i}^{A}h^{\prime }\Leftrightarrow h\succsim _{i}^{A}h^{\prime }\wedge
h^{\prime }\succsim _{i}^{A}h
\end{equation*}を満たすものとして配分集合\(A\)上の新たな二項関係\(\sim _{i}^{A}\)を定義します。

一般に、プレイヤー\(i\)が配分どうしを比較する選好\(\succsim _{i}^{A}\)は、自身が商品どうしを比較する商品集合\(H\)上の選好関係\(\succsim _{i}\)に依存して変化します。なぜなら、例えば、プレイヤーがある商品を低く評価する場合、自身にその商品を割り当てる配分を低く評価するものとみなすのが自然であり、逆に、プレイヤーがある商品を高く評価する場合、自身にその商品を割り当てる配分を高く評価するものとみなすのが自然だからです。このような事情を踏まえると、プレイヤー\(i\)が配分どうしを比較する選好\(\succsim _{i}^{A}\)は、自身が商品どうしを比較する選好\(\succsim _{i}\)に依存して変化するという意味を込めて、これを、\begin{equation*}\succsim _{i}^{A}\left[ \succsim _{i}\right] \end{equation*}と表記します。

ただ、プレイヤー\(i\)が配分どうしを比較する選好\(\succsim _{i}^{A}\)は、自身が商品どうしを比較する選好\(\succsim _{i}\)だけに依存するのではなく、他のプレイヤーたちが商品どうしを比較する選好\(\succsim _{-i}\)に依存するという状況も起こり得ます。なぜなら、例えば、プレイヤー\(i\)は自身が手に入れた商品を事後的に再交換することを見越した上で目の前の交換に臨む場合、仮に他のプレイヤーたちがある商品を低く評価しているならば、プレイヤー\(i\)は自身にその商品を割り当てる配分を低く評価するものとみなすのが自然であり、逆に、他のプレイヤーたちがある商品を高く評価しているならば、プレイヤー\(i\)は自身にその商品を割り当てる配分を高く評価するものとみなすのが自然だからです。このような事情を踏まえると、プレイヤー\(i\)が配分どうしを比較する選好\(\succsim _{i}^{A}\)は、自身が商品どうしを比較する選好\(\succsim _{i}\)だけでなく、他のプレイヤーたちが商品どうしを比較する選好\(\succsim _{-i}\)にも依存して変化するという意味を込めて、これを\(\succsim_{i}^{A}\left[ \succsim _{i},\succsim _{-i}\right] \)すなわち、\begin{equation*}\succsim _{i}^{A}\left[ \succsim _{I}\right] \end{equation*}と表記すべきです。

環境

非分割財の分配問題を表現するモデルの要素は以上ですべてです。つまり、非分割財の分配問題を描写するためには、そこに参加するプレイヤーからなる集合\(I\)、初期時点において社会的に保有され、分配の対象となる商品からなる集合\(H\)、それぞれのプレイヤー\(i\)が商品どうしを比較する選好関係\(\succsim _{i}\)、分配の結果として生じ得る配分からなる集合\(A\)、そして、それぞれのプレイヤー\(i\)が配分どうしを比較する選好関係\(\succsim _{i}\left[ \succsim _{I}\right] \)を特定することになります。以上の要素からなるモデルを、\begin{equation*}\left( I,H,\left\{ \succsim _{i}\right\} _{i\in I},A,\left\{ \succsim
_{i}^{A}\left[ \succsim _{I}\right] \right\} _{i\in I}\right)
\end{equation*}で表記し、これによって非分割財の分配問題の定義とします。このようなモデルを環境（environment）と呼ぶこともあります。

非分割財の分配問題の分析では多くの場合、任意のプレイヤーについて、商品どうしを比較する選好が選好順序であることを仮定します。狭義選好の仮定については、それを仮定する場合とそうでない場合がありますが、後述するように、その違いは分析結果に影響を与えるため注意が必要です。

演習問題