Imperfect Transferable Utility Matching について *池上慧 †2021 年 7 月 24 日

1 何を書くか
Galichon (June 2021) に基づいて Imperfect transferable matching のモデルについてその均衡計算のアルゴリズムを理解する。そのために大体以下の内容について書く。

1. Deterministic utility / Transferable utility の基本モデルとしての Becker (1973)• Shapley and Shubik (1971) や Becker (1973) の主張• Dual problem の解釈
2. Stochastic utility / Imperfect transferable utility のモデルとしての Galichon, Kominers and Weber (2019)• ITU でのマッチングを Becker のような見方をするための涙ぐましい努力• Gauss-Seidel による均衡計算• Hedonic model と Gauss-Seidel の収束 (Berry, Gandhi and Haile (2013))
3. 均衡計算• Surge pricing model• Surge pricing の均衡• Galichon, Kominers and Weber (2019) の均衡

2 Becker model
このモデルは Transferable matching (TU) の古典的モデルであり、以降見ていく Imperfect transferable

matching (ITU) の土台となるモデルである。
この世界に個人は存在せず、タイプでしか人を識別できない。女側のタイプを 𝑋 、男側を 𝑌 で表す。各𝑥 ∈ 𝑋 , 𝑦 ∈ 𝑌 に属する個体の数はそれぞれ 𝑛𝑥 , 𝑚 𝑦 であるとする。アンマッチは 0 で表す。 (𝑥, 𝑦 ) のマッチが一つ成立すると social surplus が Φ𝑥𝑦 だけ発生するとする。ここで 𝑥, 𝑦 のみ特定してしまえば生み出す余剰は決定されていることに注意。この時まずマッチメイカー（以下 MM）をソーシャルプランナーとして導入
して以下の社会厚生を最大化する問題を考えてみる。

max
𝜇 ≥0

∑

𝜇𝑥𝑦 Φ𝑥𝑦

(1)

𝑥,𝑦

{∑

s.t.

𝑦 𝜇𝑥𝑦 ≤ 𝑛 𝑥 ∀𝑥∑𝑥 𝜇𝑥𝑦 ≤ 𝑚 𝑦 ∀𝑦

* 執筆に際して適切なツッコミをしてくださった岩崎敦先生、奥村恭平さん、冨田燿志さん、松下旦さん、ツイッターに存在するにるそん（@ohtanilson）さんに感謝します。
† ikegami.kei0120@gmail.com

1ここで 𝜇𝑥𝑦 は (𝑥, 𝑦 ) ペアでマッチした数を表す。これは LP で簡単にとける。
次にこの問題の双対問題を導いてみる。まず各制約に対する Lagrange multiplier(LM) を (𝑢 𝑥 , 𝑣 𝑦 ) と書くと Lagrange 緩和問題は以下の通り書ける。

max
𝜇 ≥0

∑

∑

𝜇𝑥𝑦 Φ𝑥𝑦 −

𝑥,𝑦

(
𝑢𝑥

𝑥

∑

)
𝜇𝑥𝑦 − 𝑛𝑥 −

𝑦

∑

(
𝑣𝑦

∑

𝑦

)
𝜇𝑥𝑦 − 𝑚 𝑦𝑥

LM は非負なのでこの緩和問題の解は元の問題の解を上から押さえてくれる。緩和問題の目的関数を整理すると以下の通りかける。

max
𝜇 ≥0

∑(

∑
∑
)
Φ𝑥𝑦 − 𝑢 𝑥 − 𝑣𝑦 𝜇𝑥𝑦 +𝑛𝑥 𝑢𝑥 +
𝑚 𝑦 𝑣𝑦𝑥,𝑦𝑥𝑦

ここで 𝜇𝑥𝑦 ≥ 0 より、一つでも Φ𝑥𝑦 − 𝑢 𝑥 − 𝑣 𝑦 > 0 なるペア (𝑥, 𝑦 ) が存在してしまうとこの問題の解は無限大に発散してしまう。双対問題は元の問題の上限を最小化することを考えるのでこうなってしまってはだめ。ということで制約として Φ𝑥𝑦 ≤ 𝑢 𝑥 + 𝑣 𝑦 が全ての (𝑥, 𝑦 ) について必要となる。よって緩和問題の解を最小化するという問題は以下の通り。

min max𝑢,𝑣 ≥0 𝜇 ≥0

∑(

∑
∑
)
Φ𝑥𝑦 − 𝑢 𝑥 − 𝑣 𝑦 𝜇𝑥𝑦 +𝑛𝑥 𝑢𝑥 +
𝑚 𝑦 𝑣𝑦𝑥,𝑦𝑥𝑦s.t. 𝑢 𝑥 + 𝑣 𝑦 ≥ Φ𝑥𝑦()

もし 𝑢 𝑥 + 𝑣 𝑦 > Φ𝑥𝑦 が解をもたらすなら、その時 𝜇𝑥𝑦 = 0 とすることで Φ𝑥𝑦 − 𝑢 𝑥 − 𝑣 𝑦 𝜇𝑥𝑦 = 0 とするのが内部の最大化問題の解となることから、目的関数の第１項はどうせ 0 になることがわかる。よって 𝜇 に依存する部分を消すことができて以下の双対問題を得る。

min𝑢,𝑣 ≥0∑𝑛𝑥 𝑢𝑥 +𝑥∑𝑚 𝑦 𝑣𝑦(2)𝑦s.t. 𝑢 𝑥 + 𝑣 𝑦 ≥ Φ𝑥𝑦 ∀𝑥, 𝑦
また、この双対問題に対して、LM を 𝜇𝑥𝑦 としてまた双対を取ると 1 が得られることも同様に確認できる。
ここで双対問題は以下のように解釈できる。𝑋 ,𝑌 にそれぞれ補助金を出すことでマッチの結果得られる効用を保証し勝手にマッチしないようにすることを目指す Anti-MM の存在を考える。Anti-MM は 𝑥 ∈ 𝑋 には

𝑢 𝑥 を 𝑦 ∈ 𝑌 には 𝑣 𝑦 を与える。もちろん多額の補助金を出せば、どのペアについてもマッチして得られる余剰よりももともと持っている補助金の合計額が大きくなるのでマッチの発生を防ぐことができるが、Anti-MMはこれを最小の費用で達成することを目指す。そのためには最低限のラインとして全てのペア 𝑥, 𝑦 について

𝑢 𝑥 + 𝑣 𝑦 ≥ Φ𝑥𝑦 が成立していないといけない。でないと、このペアはマッチして生み出した余剰を配分した方が二人とも元々持っている補助金よりも資産を増やすことができてしまうからだ。従って、目的関数である総コスト∑

𝑥 𝑛𝑥 𝑢𝑥 +∑𝑦 𝑚 𝑦 𝑣 𝑦 を 𝑢 𝑥 + 𝑣 𝑦 ≥ Φ𝑥𝑦 の下で最小化するという問題が得られ、これが双対問題である。

この問題をエージェントの立場から考えてみよう。まず双対問題 (2) の制約条件から以下の関係性を得る。

{
𝑢 𝑥 ≥ max𝑦 {Φ𝑥𝑦 − 𝑣 𝑦 }𝑣 𝑦 ≥ max𝑥 {Φ𝑥𝑦 − 𝑢 𝑥 }もし、𝑢 𝑥 > max𝑦 {Φ𝑥𝑦 − 𝑣 𝑦 } が解で成立しているとすると、𝑢 𝑥 を少し下げることで制約を満たしながら目的
関数の値を下げることができてしまう。𝑣 𝑦 についても同様なので、結果として上式はいずれも等式で成立することがわかる。すなわち、双対問題の解を与える (𝑢, 𝑣 ) は以下の関数方程式の解であることがわかる。

{
𝑢 𝑥 = max𝑦 {Φ𝑥𝑦 − 𝑣 𝑦 }𝑣𝑦 = max𝑥 {Φ𝑥𝑦 − 𝑢 𝑥 }(3)

この式は 𝑥 ∈ 𝑋 の立場からすると「Anti-MM から 𝑢 𝑥 だけお金が振り込まれたけど、本当に誰ともマッチしないのがいいのだろうか？」「タイプ 𝑦 とマッチしたら相手が元々持っている 𝑣 𝑦 だけ払わないといけない。

2

その元で自分の手元に残るのは Φ𝑥𝑦 − 𝑣 𝑦 であるから、一番いいマッチ相手は max𝑦 {Φ𝑥𝑦 − 𝑣 𝑦 } の解である 𝑦ということになる。」「しかしその時得られる自分の利得は 𝑢 𝑥 で、元から自分が持っている補助金の額と同じだ。」「ということで確かに誰ともマッチせずに single でいるのがベストだな。」という話である。𝑦 ∈ 𝑌 についても同様の意味を持つ。
つまり (𝑢 𝑥 , 𝑣 𝑦 ) はタイプ 𝑥, 𝑦 それぞれとマッチするために必要な価格であると考えることができる。そして「価格を所与としてエージェントが効用最大化問題を解く」という要素と「需給が一致するように価格が設定される*1 」という二つの要素がマッチング問題を構成しているということを含意している。そして (𝑢 𝑥 , 𝑣 𝑦 )が価格に対応する概念であることに納得すれば、競争均衡の定義と同様に allocation に対応する 𝜇 との三組
み (𝜇, (𝑢, 𝑣 )) が「均衡」の主語であることにも納得がいく。
ようやく均衡を定義できる。主問題と双対問題で合わせて三つの変数 (𝜇, (𝑢, 𝑣 )) がある。ここで主問題の∑slack 変数としてアンマッチの人数を導入することができることに気づく。すなわち 𝜇𝑥0 = 𝑛𝑥 − 𝑦 𝜇𝑥𝑦 と∑
𝜇 0𝑦 = 𝑚 𝑦 − 𝑥 𝜇𝑥𝑦 を定義し、以下では 𝜇 と書いた時にはこいつも含んでいるとする。それぞれの問題の解において (𝜇, (𝑢, 𝑣 )) の間には以下のような関係性が成り立つ。

1. 主問題の制約（population constraint）∑

𝜇 + 𝜇𝑥0 = 𝑛𝑥 ∀𝑥 ∑𝑦 𝑥𝑦
𝑥 𝜇𝑥𝑦 + 𝜇 0𝑦 = 𝑚 𝑦 ∀𝑦𝜇𝑥𝑦 ≥ 0 ∀𝑥, 𝑦
2. 双対問題の制約（stability condition）

𝑢 + 𝑣 𝑦 ≥ Φ𝑥𝑦 ∀𝑥, 𝑦 𝑥
𝑢 𝑥 ≥ 0 ∀𝑥𝑣 𝑦 ≥ 0 ∀𝑥, 𝑦
3. 二つの問題の complementary slackness conditions
𝑢 > 0 ⇒ 𝜇𝑥0 = 0 ∀𝑥
 𝑥
𝑣 𝑦 > 0 ⇒ 𝜇 0𝑦 = 0 ∀𝑦𝜇𝑥𝑦 > 0 ⇒ 𝑢 𝑥 + 𝑣 𝑦 = Φ𝑥𝑦 ∀𝑥, 𝑦
この三つの条件を満たす (𝜇, (𝑢, 𝑣 )) を equilibrium matching と呼ぶ。双対問題の解釈で見た通り、双対問
題の制約は stability condition と解釈することができることに注意する*2 。ここで TU モデルと言いながら各タイプ間でなされる transfer が均衡で実現するもの以外モデルや定義に出てこないことに注意したい。このように transfer をうまくモデルから省くというのが TU モデルの肝であり、それができず transfer を明示的に考える必要があるというのが ITU を考えるのが難しくなる根本的要因である。
この TU モデルは主問題、双対問題ともに目的関数も制約も線形であることから LP solver で簡単に解け
る*3 。そして以上の議論より TU モデルにおいて社会厚生を最大化するマッチングは stability を満たすという意味で均衡であることもわかった。TU においてはこのように welfare theorem に類似した結果が成立するのである。

*1 これはつまり式 (3) において X,Y 両側について効用最大化問題を同時に解かなくてはいけないということ。
*2 文脈に即して書くと、𝑢 𝑥 + 𝑣 𝑦 < Φ𝑥𝑦 の時、条件 3 より 𝜇𝑥𝑦 = 0 だが、このペアはマッチすれば現在の利得 𝑢 𝑥 , 𝑣 𝑦 よりも大きい額を両者ともに得られる。すなわち条件 2 は pair wise stability を表現している。
*3 汎用ソルバーで解ける形に落とし込むのが均衡計算でも部分識別でもトレンドで、落とし込めれば速度面でも最速。by にるそんさん

33 Imperfect Transferable Utility でのマッチングモデル
3.1 Transfer を入れた表現
ITU のモデルに入る前に、Becker のモデルが transfer を明示的にモデル化してもかけることを確認する。
タイプ 𝑥, 𝑦 の間の trasfer を 𝑤𝑥𝑦 と書く。また、𝑥, 𝑦 がマッチした時に 𝑥 が得る効用を 𝛼𝑥𝑦 、𝑦 が得る効用を𝛾𝑥𝑦 とかき、Φ𝑥𝑦 ≡ 𝛼𝑥𝑦 + 𝛾𝑥𝑦 と定義する。この時、𝑋 ,𝑌 が両側で以下の効用最大化を行い、その需給を一致させるような価格帯系 𝑤𝑥𝑦 を求めるという問題を自然に考えることができる。

𝑢 𝑥 ≡ max {𝛼𝑥𝑦 + 𝑤𝑥𝑦 , 0}𝑦𝑣 𝑦 ≡ max {𝛾𝑥𝑦 − 𝑤𝑥𝑦 , 0}𝑥

そして、 (𝜇, 𝑤 ) が equilibrium matching であるとは以下の３つの性質が満たされていることをいうとする。

1. Population constraint∑
𝜇 + 𝜇𝑥0 = 𝑛𝑥 ∀𝑥 ∑𝑦 𝑥𝑦
𝑥 𝜇𝑥𝑦 + 𝜇 0𝑦 = 𝑚 𝑦 ∀𝑦𝜇𝑥𝑦 ≥ 0 ∀𝑥, 𝑦
2. Stability condition𝑢 ≥ 𝛼𝑥𝑦 + 𝑤𝑥𝑦 ∀𝑥, 𝑦 𝑥
𝑣 𝑦 ≥ 𝛾𝑥𝑦 − 𝑤𝑥𝑦 ∀𝑥, 𝑦𝑢 𝑥 , 𝑣 𝑦 ≥ 0 ∀𝑥, 𝑦
3. Complementary slackness condition
𝑢 > 0 ⇒ 𝜇𝑥0 = 0 ∀𝑥
 𝑥
𝑣 𝑦 > 0 ⇒ 𝜇 0𝑦 = 0 ∀𝑦𝜇𝑥𝑦 > 0 ⇒ 𝑢 𝑥 = 𝛼𝑥𝑦 + 𝑤𝑥𝑦 ∧ 𝑣 𝑦 = 𝛾𝑥𝑦 − 𝑤𝑥𝑦 ∀𝑥, 𝑦
元の均衡の定義との違いは主に stability condition であるが、𝑤𝑥𝑦 ∈ [−𝛼𝑥𝑦 , 𝛾𝑥𝑦 ] をパラメータだと思って(𝑢 𝑥 , 𝑣 𝑦 ) の取りうる範囲を考えてみると両者は同じ条件であることがわかる。すなわち、transfer(𝑤𝑥𝑦 ) を明示的に扱うことでより自然な形でマッチングを decentralized problem として理解することができるというわけである。
今、𝑥 が 𝑦 とマッチしてえる効用を 𝑈𝑥𝑦 (𝑤𝑥𝑦 ) 、逆を 𝑉𝑥𝑦 (𝑥𝑦 ) と書くことにする。すなわち先の becker モデ
ルでは 𝑈𝑥𝑦 (𝑤𝑥𝑦 ) = 𝛼𝑥𝑦 + 𝑤𝑥𝑦 ,𝑉𝑥𝑦 (𝑤𝑥𝑦 ) = 𝛾𝑥𝑦 − 𝑤𝑥𝑦 である。ここで自然な拡張として 𝑈𝑥𝑦 (𝑤𝑥𝑦 ) が 𝑤𝑥𝑦 について増加/減少であるが線形ではないケースではどうなるのかを考えたくなる。先に確認確認した通り Becker
モデルではこれらが 𝑤𝑥𝑦 について線形であったが故に 𝑤𝑥𝑦 をキャンセルアウトでき、結果として LP である dual problem (2) とその主問題 (1) に問題を帰着できたため容易に解くことができた。従って、一般の𝑈𝑥𝑦 (𝑤𝑥𝑦 ),𝑉𝑥𝑦 (𝑤𝑥𝑦 ) に拡張したときにこの線形計画への帰着ができなくなるのは必至であり、Becker と同じようには解けなくなる。

3.2 緩和問題としての誤差項付きマッチング問題
今のままでは問題を解けない。仕方ないのである種の緩和問題を代わりに解くことを考える。ITU モデル
における誤差項はこの緩和問題のために付け加えられた要素として理解することができる。
以下では 𝑖 , 𝑗 をそれぞれ 𝑋 ,𝑌 側の個人として表し、𝑥𝑖 , 𝑦 𝑗 を 𝑖 , 𝑗 が属するタイプであるとする。まず properbargaining set (F𝑖 𝑗 ) を導入する。定義を Galichon, Kominers and Weber (2019) から引っ張ってくると
4

Deﬁnition 1 のようである。要するにいつもの bargaining set なのでそう理解すれば良い。さらにタイプ𝑥, 𝑦 に紐付けた bargaining set として F𝑥𝑦 も同じように考えることができる。これらを用いて error term を
以下のようにモデルに組み入れる。

Assumption 1. ∥𝑌 ∥ + 1 次元の分布 𝑃𝑥 と ∥𝑋 ∥ + 1 次元の分布 𝑄 𝑦 を 𝑥, 𝑦 ごとに考える。ここで個人 𝑖 ごとに( )各 𝑦 について 𝜖𝑖 ,𝑦 がこの分布に従って発生しているとする。すなわち 𝜖𝑖 = 𝜖𝑖 ,𝑦 𝑦 ∈𝑌 である。 𝑗 についても同0⊕()
様に 𝜂 𝑗 = 𝜂 𝑥,𝑗 𝑥 ∈𝑋 である。この時、F𝑖 𝑗 = F𝑥𝑖 ,𝑦 𝑗
(𝜖
,𝜂
)
となる
𝑃
,
𝑄
が存在する。
𝑖
,𝑦
𝑥
,𝑗
𝑥
𝑦
𝑗
𝑖
0
この仮定は additive separability と呼ばれる。これは大きく以下の三つのことを含意している。

1. 個人ごとの選好の違いはマッチング相手のタイプに対してのみ存在することを許されている。マッチン
グ相手については同じタイプの違う人を区別することはできない。

2. ひとつのタイプのペア (𝑥, 𝑦 ) について注目するとその中の個々のペアの配分 (𝑢 𝑖 , 𝑣 𝑗 ) はひとつの共通のタイプ speciﬁc な配分 (𝑈𝑥 ,𝑉𝑦 ) から誤差項の分だけ移動したものになる。

3. ひとつのタイプのペア (𝑥, 𝑦 ) の内部で個人の組む相手をどんなふうに入れ替えても全て均衡となる。なぜなら Additive separability の下では error term は誰とくっつくかに依存しておらず、どんな組み方
をしても個人の得る利得に変化はないからである。
このように個人を完全に識別した上でのマッチングから、個人をタイプでしか見れないものとして考える
マッチングへと問題を変化させている。先の Becker のモデルではタイプ 𝑋 は個人を完全に識別するものとなっており、同一の個人がたくさんいるというモデルであった。しかしこの緩和問題でのタイプは不完全な情報しか持っておらず、誤差項も含めてようやくマッチング相手がどんな人か、自分にとってどれだけ良い相手かが決まるモデルとなっている。さらにその誤差項はモデル外の研究者のみならずモデル内のエージェントにも観測できないものとなっている。従ってこのモデルでマッチ相手を探す問題は相手を完全に把握するのではなく相手について不完全な情報しか持ってない中で誤差を許してマッチ相手を選ぶことになる。この意味で元の問題の緩和になっている。
また error term の分布については以下の通り full support であるという仮定をおく。これは以下で見ていく Aggregate equilibrium の定義において重要な役割を果たす。

Assumption 2. 𝑃𝑥 and 𝑄 𝑦 have nonvanishing densities on ℝ |𝑌 |+1 and ℝ |𝑋 |+1 .

3.3 Individual Equilibrium から Aggregate Equilibrium へ
3.3.1 Individual Equilibrium
まず F𝑖 𝑗 への距離関数 𝐷 F𝑖 𝑗 を以下のように定義して今までの均衡の定義を以降使いやすいように書き換えることから始める。

5

図 1 Distance function の様子

Deﬁnition 1. 𝐷 F𝑖 𝑗 (𝑢, 𝑣 ) ≡ min{𝑧 ∈ ℝ | (𝑢 − 𝑧, 𝑣 − 𝑧) ∈ F𝑖 𝑗 }つまりどれだけ並行移動すれば F𝑖 𝑗 に入れるか、という値である。絵でかくと図 1 のような感じ。また、以下の距離関数の重要な性質も簡単に示せる。

Proposition 1. 任意の定数 𝑎 ∈ ℝ について 𝐷 F𝑖 𝑗 (𝑢 + 𝑎, 𝑣 + 𝑎) = 𝐷 F𝑖 𝑗 (𝑢, 𝑣 ) + 𝑎 である。
この距離関数を使うと、先に考えた transfer を明示的に扱った場合の Becker モデルの均衡は以下の三つの条件に書き換えることができる。

1. Population constraint∑
𝜇 + 𝜇𝑥0 = 𝑛𝑥 ∀𝑥 ∑𝑦 𝑥𝑦
𝑥 𝜇𝑥𝑦 + 𝜇 0𝑦 = 𝑚 𝑦 ∀𝑦𝜇𝑥𝑦 ≥ 0 ∀𝑥, 𝑦
2. Stability condition{()
𝐷 F𝑥𝑦 𝑢 𝑥 , 𝑣 𝑦 ≥ 0 ∀𝑥, 𝑦
𝑢 𝑥 , 𝑣 𝑦 ≥ 0 ∀𝑥, 𝑦

3. Complementary slackness condition
𝑢 > 0 ⇒ 𝜇𝑥0 = 0 ∀𝑥
 𝑥
𝑣 𝑦 > 0 ⇒ 𝜇 0𝑦 = 0 ∀𝑦()
𝜇𝑥𝑦 > 0 ⇒ 𝐷 F 𝑢 𝑥 , 𝑣 𝑦 = 0 ∀𝑥, 𝑦
𝑥𝑦


(

)

また error term を入れることで緩和されたマッチング問題に対しても同様の均衡 𝜇𝑖 𝑗 , (𝑢 𝑖 , 𝑣 𝑗 ) を考えることができる。ここで 𝜇𝑖 𝑗 ∈ {0, 1} であることに注意したい。すなわち、この均衡概念はあくまで個人に対して用いられるものであるということ、そして今のモデルでは選好の違いを許しているため同一の個人は一人しか6

いないという二点に注意する必要がある*4 。

1. Population constraint{∑∑

𝑗 𝜇𝑖 𝑗 ≤ 1𝑖 𝜇𝑖 𝑗 ≤ 1

2. Stability condition{()
𝐷 F𝑥𝑖 𝑦 𝑗 𝑢 𝑖 , 𝑣 𝑗 ≥ 0 ∀𝑖 , 𝑗𝑢 𝑖 , 𝑣 𝑗 ≥ 0 ∀𝑥, 𝑦
3. Complementary slackness condition
𝑢 > 0 ⇒ 𝜇𝑖 0 = 0 ∀𝑖
 𝑖𝑣 𝑗 > 0 ⇒ 𝜇 0𝑗 = 0 ∀𝑗()
𝜇𝑖 𝑗 = 1 ⇒ 𝐷 F𝑥 𝑦 𝑢 𝑖 , 𝑣 𝑗 = 0 ∀𝑖 , 𝑗
𝑖 𝑗
この均衡を individual equilibrium と呼ぶ。しかし既に確認した通り、Additive separability の帰結としてタイプ内での組み替えについては複数均衡を許していること、そして error term は econometrician には見えないので実証上使いにくい結果しか出てこないことから、別の均衡概念が欲されるところである。具体的には 𝜇𝑖 𝑗 ではなく観測できるタイプについてのマッチング 𝜇𝑥𝑦 が主語となるような均衡概念があると嬉しい。

3.3.2 Aggregate Equilibrium
ここでは新しい均衡概念として Aggregate Equilibrium を導入していく。以下では 𝐷 F⟩| などで F は省略する。まず、Individual equilibrium の下では以下が成立する。

𝐷 F𝑖 𝑗 (𝑢 𝑖 , 𝑣 𝑗 ) ≥ 0 ∀𝑖 , 𝑗
Additive separability よりこの条件は以下を意味する。
)(
𝐷𝑥𝑖 𝑦 𝑗 𝑢 𝑖 − 𝜖𝑖 𝑦 𝑗 , 𝑣 𝑗 − 𝜂𝑥𝑖 𝑗 ≥ 0 ∀𝑖 , 𝑗
すなわち、タイプについて F𝑥𝑦 のフロンティアに存在しなかったら、個人同士の F𝑖 𝑗 のフロンティアには存在できないということである。
これより、

{
(
)}
min
𝐷𝑥𝑦 𝑢 𝑖 − 𝜖𝑖 𝑦 , 𝑣 𝑗 − 𝜂𝑥 𝑗
𝑖 :𝑥𝑖 =𝑥,𝑗 :𝑦 𝑗 =𝑦)(
≤ 𝐷𝑥𝑦 min {𝑢 𝑖 − 𝜖𝑖 𝑦 }, min {𝑣 𝑗 − 𝜂𝑥 𝑗 }0≤

𝑖 :𝑥𝑖 =𝑥

𝑗 :𝑦 𝑗 =𝑦を得る。これを受けて、タイプの情報のみから決まる決まる効用部分を sytematic utility と呼び、𝑋 ,𝑌 が受け取る利得をそれぞれ 𝑈𝑥𝑦 ,𝑉𝑥𝑦 で書くとして、それらを以下のように定義することを考えてみる。

{
𝑈𝑥𝑦 = min𝑖 :𝑥𝑖 =𝑥 {𝑢 𝑖 − 𝜖𝑖 𝑦 }𝑉𝑥𝑦 = min𝑗 :𝑦 𝑗 =𝑦 {𝑣 𝑗 − 𝜂𝑥 𝑗 }(4)

こう定義すると上で見た通り 𝐷𝑥𝑦 (𝑈𝑥𝑦 ,𝑉𝑥𝑦 ) ≥ 0 が任意のペア (𝑥, 𝑦 ) で保証される。また、𝐷𝑥𝑦 (𝑈𝑥𝑦 ,𝑉𝑥𝑦 ) > 0があるペア (𝑥, 𝑦 ) で成り立つとすると、Additive separability よりある個人のペア 𝑖 , 𝑗 について配分 (𝑢 𝑖 , 𝑣 𝑗 )が F𝑖 𝑗 に入らなくなってしまう。従って 𝐷𝑥𝑦 (𝑈𝑥𝑦 ,𝑉𝑥𝑦 ) = 0 が全てのペア (𝑥, 𝑦 ) で成立する*5 。すなわちこの*4 Becker モデルは同一の個人がたくさんいる状況であったことを思い出す。
*5 full support の仮定より全ての観測できるタイプのペアについて必ずマッチした人々が存在しているため「全てのペア (x,y) について」と主張することができる。

7

ように定義した systematic utility はタイプに関する bargaining set のフロンティアに存在することが保証される。

Individual equilibrium の下で systematic utility に成立するこの性質は「均衡」として望ましい性質である。なぜならば、Additive separability の仮定の下では、𝐷𝑥𝑦 (𝑈𝑥𝑦 ,𝑉𝑥𝑦 ) < 0 の時その中の個人のペア (𝑖 , 𝑗 ) の配分 (𝑢 𝑖 , 𝑣 𝑗 ) も F𝑖 𝑗 (𝑢 𝑖 , 𝑣 𝑗 ) < 0 となってしまい両者にとってより良い配分が存在することになってしまうし、𝐷𝑥𝑦 (𝑈𝑥𝑦 ,𝑉𝑥𝑦 ) > 0 ならば (𝑢 𝑖 , 𝑣 𝑗 ) も実現できない配分になってしまうからである。
また、systematic utility の定義である式 (4) は以下のことを含意する。

𝑈𝑥𝑦 = min {𝑢 𝑖 − 𝜖𝑖 𝑦 } ∀𝑥, 𝑦
𝑖 :𝑥𝑖 =𝑥

⇒ 𝑈𝑥𝑦 ≤ 𝑢 𝑖 − 𝜖𝑖 𝑦 ∀𝑖 : 𝑥𝑖 = 𝑥, ∀𝑥, 𝑦⇔ 𝑢 𝑖 ≥ 𝑈𝑥𝑦 + 𝜖𝑖 𝑦 ∀𝑖 : 𝑥𝑖 = 𝑥, ∀𝑥, 𝑦⇔ 𝑢 𝑖 ≥ max {𝑈𝑥𝑦 + 𝜖𝑖 𝑦 } ∀𝑖 : 𝑥𝑖 = 𝑥, ∀𝑥𝑦

ただし、Additive separability の下ではこの不等式は等号で成立する。従って、Individual equilibrium の下で先のように定義した systematic utility を用いると 𝑋 の問題は以下の離散選択問題として捉えることができるというわけである。

𝑢 𝑖 = max {𝑈𝑥𝑦 + 𝜖𝑖 𝑦 }𝑦

これは 𝑦 ∈ 𝑌 についても同様のことが言える。この「離散選択問題に帰着できる」というのは Becker モデルでも実現した性質であり、「均衡」の性質として欲しいものである。
そして Becker モデルを思い出すと「均衡」の性質としては「需給の一致を達成する価格」という要素が欲しいことに気づく。だが今 𝑈𝑥𝑦 ,𝑉𝑥𝑦 を直接扱っていて transfer に対応するものがないことにも気づく。ただこれはそこまで大きな問題ではなく、𝑈𝑥𝑦 = 𝑈𝑥𝑦 (𝑤𝑥𝑦 ),𝑉𝑥𝑦 = 𝑉𝑥𝑦 (𝑤𝑥𝑦 ) の略称とでも思っておけば良い。「均衡」の定義として allocation と価格のペアを主語にしたい気持ちはあるが、ここでは煩雑にならないように

tarnsfer (𝑤𝑥𝑦 ) を省略して (𝜇𝑥𝑦 , (𝑈𝑥𝑦 ,𝑉𝑥𝑦 )) を主語として「均衡」を定義することにする。すなわち、需給を一致させる 𝑤𝑥𝑦 ではなく、需給を一致させる 𝑤𝑥𝑦 の下で実現される systematic utility のペア (𝑈𝑥𝑦 ,𝑉𝑥𝑦 ) を均衡の主語とする。
さて、では肝心の「需給の一致」はどのように表記できるかを考える。Galichon and Salanie (2021) の結果は「需給の一致」を非常にシンプルに表現してくれるのでそれを使う。ここまでですでに両サイドの離散選択問題としてマッチング問題を表現することについては納得できているため、以下のような generalized

entropy を定義したくなる。
[
]
∑


𝐺 (𝑈 ) ≡ 𝑥 𝑛𝑥 𝔼 max𝑦 {𝑈𝑥𝑦 + 𝜖𝑖 𝑦 }

[
]
∑

𝐻 (𝑉 ) ≡ 𝑦 𝑚 𝑦 𝔼 max𝑥 {𝑉𝑥𝑦 + 𝜂𝑥 𝑗 }
ここで期待値はそれぞれ 𝜖𝑖 ,𝜂 𝑗 についてのものである。Daly-Zachary-Williams 定理からタイプ 𝑥 のタイプ
(𝑈 )𝜕𝐻 (𝑉 )
𝑦 への需要、タイプ 𝑦 のタイプ 𝑥 への需要はそれぞれ 𝜚𝑥𝑦 = 𝜕𝐺
「需給の一致」
𝜕𝑈𝑥𝑦 , 𝜑 𝑥𝑦 = 𝜕𝑉𝑥𝑦 で得られる。

は全てのペア (𝑥, 𝑦 ) についてこの二つが一致していることに他ならない。従って、∇𝐺 (𝑈 ) = ∇𝐻 (𝑉 ) が需給の一致を表現している。
以上で均衡に欲しい要素が individual equilibrium の概念から浮かび上がってきた。これらの性質をAggregate equilibrium の定義として採用する。
Deﬁnition 2. (𝜇𝑥𝑦 , (𝑈𝑥𝑦 ,𝑉𝑥𝑦 )) は以下の性質を満たすとき Aggregate equilibrium であるという。
1. Population constraint
2. Feasibility: 𝐷𝑥𝑦 (𝑈𝑥𝑦 ,𝑉𝑥𝑦 ) = 0 ∀𝑥, 𝑦
3. Market clearing: 𝜇 = ∇𝐺 (𝑈 ) = ∇𝐻 (𝑉 )8

さらに、Galichon and Salanie (2021) に従って 𝐺 , 𝐻 の Legendre 変換を 𝐺 ★ , 𝐻 ★ とすると以下の主張が成り立つ。

Proposition 2. Population constraint を満たす 𝜇𝑥𝑦 を Aggregate equilibrium matching であるようにす
る 𝑈𝑥𝑦 ,𝑉𝑥𝑦 が存在することの同値条件は、

𝐷𝑥𝑦

(

)
𝜕𝐺 ★ (𝜇) 𝜕𝐻 ★ (𝜇)
,
=0
𝜕𝜇𝑥𝑦
𝜕𝜇𝑥𝑦

が全ての 𝑥, 𝑦 で成立することである。
ここで注目すべきは最後の式が 𝜇 についてのみの式になっているところである。すなわち、Aggregate

equilibrium の定義における三つ目の条件は 𝜇 と 𝑈 ,𝑉 を繋ぐ役割を果たしており、Generalized entropy のLegendre 変換はその一般的な表現を与えてくれるということである。逆に言えば、Legendre 変換を経由しなくても 𝜇 と (𝑈 ,𝑉 ) を繋ぐ式が得られていれば、それを二つ目の条件に入れることでマッチング 𝜇 についてのみの式と population constraint のみに還元することができるということである。
また、最後の指揮を 𝜇𝑥𝑦 についてといたものをマッチングファンクションと呼び、通常アンマッチの()

数 𝜇𝑥0 , 𝜇 0𝑦 の関数としてかける。すなわち、𝜇𝑥𝑦 = 𝑀𝑥𝑦 𝜇𝑥0 , 𝜇 0𝑦 である。従って、Prop 2 の含意として、

𝑀𝑥𝑦 (𝜇𝑥0 , 𝜇 0𝑦 ) を population constraint に組み入れて (𝜇𝑥0 , 𝜇 0𝑦 ) についての連立方程式を解けば均衡マッチ
ング 𝜇𝑥𝑦 を計算できる、ということになる。以下ではまずこの事実を Choo and Siow (2006) で確認する。

3.4 具体例としての Choo and Siow（2006）
このモデルは 𝜖𝑖 𝑦 ,𝜂 𝑥 𝑗 が独立に同一の Gumbel 分布に従うとしたモデルである。この時離散選択モデルにつ
𝜇𝑥𝑦

𝜇𝑥𝑦

いての結果から 𝑈𝑥𝑦 = ln 𝜇𝑥0 ,𝑉𝑥𝑦 = ln 𝜇0𝑦 であることが知られている。これが先に述べたような、「Legendre
変換を経由しないで 𝜇 と 𝑈 ,𝑉 を繋ぐ結果」に相当する。Prop 2 から、マッチングファンクションを計算す
るには以下のようにすれば良い。

(

)
𝜇𝑥𝑦
𝜇𝑥𝑦
𝐷𝑥𝑦 ln
, ln
=0
𝜇𝑥0
𝜇 0𝑦
(
)
⇒ ln 𝜇𝑥𝑦 + 𝐷𝑥𝑦 − ln 𝜇𝑥0 , − ln 𝜇 0𝑦 = 0
(
(
))
(
)
⇒ 𝜇𝑥𝑦 = exp −𝐷𝑥𝑦 − ln 𝜇𝑥0 , − ln 𝜇 0𝑦 ≡ 𝑀𝑥𝑦 𝜇𝑥0 , 𝜇 0𝑦
ここで 𝐷𝑥𝑦 (𝑢, 𝑣 ) =𝑢+𝑣 −Φ𝑥𝑦であることが図 2 から容易に確認できる。
2

従ってマッチングファンクションは以下の表現を得る。

)
𝐶𝑆 (
𝑀𝑥𝑦
𝜇𝑥0 , 𝜇 0𝑦 = exp(− ln 𝜇𝑥0 − ln 𝜇 0𝑦 − Φ𝑥𝑦
−
2

)

(

ln 𝜇𝑥0 + ln 𝜇 0𝑦 + Φ𝑥𝑦
= exp
2

)

(
)
Φ𝑥𝑦
√
= 𝜇𝑥0 𝜇 0𝑦 exp2

これを用いて population constraint を表現すると、{∑

𝑐𝑠
𝑦 𝑀𝑥𝑦 (𝜇𝑥0 , 𝜇 0𝑦 ) + 𝜇𝑥0 = 𝑛 𝑥 ∀𝑥𝑐𝑠𝑥 𝑀𝑥𝑦 (𝜇𝑥0 , 𝜇 0𝑦 ) + 𝜇 0𝑦 = 𝑚 𝑦 ∀𝑦∑(5)である。この連立方程式は |𝑋 | + |𝑌 | この未知変数についての |𝑋 | + |𝑌 | 本の式となっているので解ける。これを解くというのが「マッチングモデルを解く」ということである。

4 均衡計算Choo and Siow (2006) か ら 離 れ て 一 般 的 に ITU モ デ ル を 考 え る が 、引 き 続 き Logit error に 話 を絞 る 。す な わ ち 、𝐷𝑥𝑦 の 形 が モ デ ル に 応 じ て 変 わ る だ け で マ ッ チ ン グ フ ァ ン ク シ ョ ン が 𝑀𝑥𝑦 (𝑢, 𝑣 ) =(())
exp −𝐷𝑥𝑦 − ln 𝜇𝑥0 , − ln 𝜇 0𝑦 でかける状況に話を絞る。
9

図 2 Choo and Siow (2006) の F𝑥𝑦 と 𝐷𝑥𝑦 (𝑢, 𝑣 )上の例で見たように、均衡を計算するためには以下の連立方程式を解けば良い。

{∑∑

𝑦 𝑀𝑥𝑦 (𝜇𝑥0 , 𝜇 0𝑦 ) + 𝜇𝑥0 = 𝑛 𝑥 ∀𝑥

𝑥 𝑀𝑥𝑦 (𝜇𝑥0 , 𝜇 0𝑦 ) + 𝜇 0𝑦 = 𝑚 𝑦 ∀𝑦(6)

これには大きく分けて二つの解法がある。一つはこの等式を FOC と見做せる関数を考えて、その多変数関数の最小化問題として解くやり方である。これを Gradient Descent method と呼ぶ。もう一つは連立方程式
を反復法で解く Gauss-Seidel algorithm またの名を Iterative Proportional Fitting Procedure (IPFP) である。経済学的に面白みがあるのは IPFP なのでここではそちらのみ解説する。Gradient descent についてはGalichon and Salanie (2021) を参照。

4.1 Gaus-Seidel (IPFP)
アルゴリズムは以下の通り進む。

1. 初期値を設定する。
2. 他の値を所与として一つの値について方程式を解いてアップデートする。
3. アップデートされた値を所与として順番に一つずつ方程式を解いていく。
4. アップデートされなくなるまでこれを続ける。
先の Choo and Siow (2006) の例で具体的に考える。以下の連立方程式を解く。

∑
𝑦

∑
𝑥

(

)
ln 𝜇𝑥0 + ln 𝜇 0𝑦 + Φ𝑥𝑦exp+ 𝜇𝑥0 = 𝑛𝑥
2
(
exp

)
ln 𝜇𝑥0 + ln 𝜇 0𝑦 + Φ𝑥𝑦+ 𝜇 0𝑦 = 𝑚 𝑦2

手計算ではたとえ他の変数を固定したところで 𝜇𝑥0 , 𝜇 0𝑦 についてこの方程式を解くことは難しいが、実装上はroot ﬁnding をさせればいいので特に問題はなく IPFP は実行できる。*6 また、順次アップデートせずに古い値から新しい値へと全ての変数について一斉にアップデートすることも当然できて、こちらは Jacobi algorithm*6 実は工夫すれば手計算でアップデートの式を得ることができる。詳しくは Galichon (June 2021) の Day 2 を参照。

10

と呼ばれる。これら二つはどちらも coordinate update algorithm と呼ばれる集団に属しており、収束の証
明などは共通である。Gauss-Seidel は新しい情報をすぐ使えるため収束が早そうな一方、Jacobi の方が並列計算しやすいという利点があるので問題に応じてどちらを使うべきかは変わってくる。

4.2 Coordinate update の収束について
Berry, Gandhi and Haile (2013) の結果を使うことに経済学的面白みが直接見えるのは surge pricing のようなケースであって式 (6) を解くということに対してではない気がする。*7 なので

1. Surge pricing の導入
2. Berry, Gandhi and Haile (2013) の結果に基づいて Surge pricing モデルの均衡の唯一性を考える。
3. 上記の証明が coordinate update algorithm を使った構成的証明になっていることの確認
4. Coordinate update algorithm の例：Gale and Shapley (1962) と比較した Adachi (2000)という順番で書いていきます。

4.2.1 Surge pricing
𝑛 個のピックアップポイントがある都市でタクシードライバーとタクシー利用者の需給を一致させる価格設定を計算する問題を考える。𝑧 ∈ {0, · · · , 𝑛 − 1} でピックアップポイントを表す。ドライバーを 𝑖 と書いて、ドライバー 𝑖 がポイント 𝑧 に向かい客から価格 𝑝 𝑧 をもらえるときの利得は以下の通り、systematic utility(𝑢 𝑖 𝑧 (𝑝 𝑧 )) とパラメータ 𝜎 のガンベル分布に従う error term (𝜖𝑖 𝑧 ) の和で表現されるとする。
𝑢 𝑖𝜎𝑧 (𝑝𝑧 ) = 𝑢 𝑖 𝑧 (𝑝𝑧 ) + 𝜖𝑖 𝑧
同様にタクシー利用者を 𝑗 で表記してポイント 𝑧 に向かったときのコストを以下のように表現する。

𝑐 𝑗𝜎𝑧 (𝑝 𝑧 ) = 𝑐 𝑗 𝑧 (𝑝 𝑧 ) + 𝜂 𝑗 𝑧
価格ベクトルを 𝑝 で書くとして、特定のポイント 𝑧 における供給関数と需要関数は以下の通りである。ここでアウトサイドオプションを含んだピックアップポイントの集合を 𝑍 0 と書いている。

𝑆 𝑧𝜎 (𝑝) =

(

∑
𝑖

exp
∑

𝑧 ′ ∈𝑍𝑢𝑖 𝑧 (𝑝𝑧 )
𝜎

exp
0

(

)

𝑢𝑖 𝑧 ′ (𝑝𝑧 ′ )𝜎

𝐷 𝑧𝜎 (𝑝) =

),

(

∑
𝑗

exp
∑

𝑧 ′ ∈𝑍−𝑐 𝑗 𝑧 (𝑝 𝑧 )
𝜎

exp
0

)

( −𝑐 ′ (𝑝 ′ ) )
𝑗𝑧

𝜎

𝑧

これよりポイント 𝑧 における excess supply function を以下の通り定義する。

𝑒 𝑧𝜎 (𝑝) = 𝑆 𝑧𝜎 (𝑝) − 𝐷𝑧𝜎 (𝑝)ここで全てのポイント 𝑧 ∈ 𝑍 について 𝑒 𝑧𝜎 (𝑝) = 0 が成り立つような価格を求めることが均衡をもたらす価格を計算するということに対応する。需給を一致させるように価格調整をするこのモデルを surge pricing モデ
ルと呼ぶことにする。

4.2.2 Surge pricing の均衡の存在
さて全てのポイントで需給を一致させる価格を計算したい。しかし、𝑒 𝜎 (𝑝) : ℝ |𝑍 | → ℝ ∥𝑍 ∥ は 𝑝 について結構複雑な形をしていそうだし気合いで解くのは大変そう。人間ごときにできることはせいぜい一変数についての方程式を解くことぐらいですよ... ということで一変数ずつ順番に方程式を解いていったらうまいこと元の多変数にいての root ﬁnding ができてくれないかな？という気持ちが生えてくる。
*7 Galichon, Kominers and Weber (2019) の Section V、population constraint を無視してる気がするんですが...

11フォーマルに書くと以下のようなアルゴリズムを考える。まず 𝑐𝑢 𝑧 (𝑝 −𝑧 ) : ℝ |𝑍 |−1 → ℝ を以下の等式を満たす関数として定義する。

𝑒 𝑧 (𝑐𝑢 𝑧 (𝑝−𝑧 ), 𝑝 −𝑧 ) = 0
初期値を 𝑝 0 とかいて、𝑡 = 0, 1, · · · について以下のように価格をアップデートしていく。
𝑡
𝑝𝑧𝑡 +1 = 𝑐𝑢 𝑧 (𝑝 −𝑧) ∀𝑧 ∈ 𝑍

これが Jacobi のアルゴリズムである。以下ではこのアルゴリズムの収束を示すことで均衡の存在を構成的(に示す。まず 𝑐𝑢 (𝑝) = 𝑐𝑢 1 (𝑝 −1 ), · · · , 𝑐𝑢 |𝑍 | (𝑝 −|𝑍 | ))′としてあげると均衡である 𝑝 ★ が 𝑐𝑢 の不動点、そしてJacobi のアルゴリズムの収束先であるということがわかる。
★
), ∀𝑧 ∈ 𝑍 ⇔ 𝑝 ★ = 𝑐𝑢 (𝑝 ★ )𝑒 𝜎 (𝑝 ★ ) = 0 ⇔ 𝑝𝑧★ = 𝑐𝑢 𝑧 (𝑝−𝑧ここで何らかの不動点定理から均衡の存在や唯一性を主張したくなるが、𝑢 𝑖 𝑧 , 𝑐 𝑗 𝑧 について特に特定していない現状では 𝑐𝑢 が縮小写像であるとか言ったことを示すのはなかなか大変そうだということに気づく。そこで 𝑢 𝑖 𝑧 , 𝑐 𝑗 𝑧 への制約がなるべく必要なくても均衡の存在を主張できないかということを考えていく。
ゆるい制約として「𝑝 𝑧 が上がればタクシードライバーはポイント 𝑧 をより好ましく思い、利用者はポイン
ト 𝑧 をより嫌だなと思う」という仮定を考える。フォーマルに書けば以下の通り。

Assumption 3.
d𝑐 𝑖 𝑧>0d𝑝𝑧

d𝑢 𝑖 𝑧> 0,d𝑝𝑧

これは excess supply function が以下の Gross substitute を満たすことを保証できる。

Deﬁnition 3 (Gross substitute). 𝑒 𝑧 (𝑝) が 𝑝𝑧 について増加関数、𝑥 ≠ 𝑧 の 𝑝𝑥 について非増加関数
均衡の存在は以下の定理による。

Theorem 1. 全ての 𝑧 ∈ 𝑍 について 𝑒 𝑧 (𝑝) が Gross substitute を満たすとする。この時、
1. どのような 𝑧 と 𝑝−𝑧 についても 𝑒 𝑧 (𝑝 𝑧 , 𝑝 −𝑧 ) = 0 なる 𝑝 𝑧 が存在する。
2. 全ての 𝑧 について 𝑒 𝑧 (𝑝 0 ) ≥ 0 なる初期値 𝑝 0 が存在する。（このような価格を super solution と呼ぶ）の三つが満たされているならば、super solution (𝑝 0 ) から始めた Jacobi のアルゴリズムは収束する。
0 ) ≥ 0 なる 𝑝 0 が存在する。仮定 (1) より全ての 𝑧 ∈ 𝑍 について
Proof. 𝑡 = 0 の時、仮定 (2) より 𝑒 𝑧 (𝑝𝑧0 , 𝑝 −𝑧
( 1 0 )
𝑒 𝑧 𝑝𝑧 , 𝑝 −𝑧 = 0 なる 𝑝𝑧1 が存在する。この時以下の関係性が成立する。

()
00𝑒 𝑧 (𝑝𝑧0 , 𝑝 −𝑧
) ≥ 0 = 𝑒 𝑧 𝑝𝑧1 , 𝑝 −𝑧
この時 Gross substitute であることから 𝑝 𝑧0 ≥ 𝑝 𝑧1 であるとわかる。これが全ての 𝑧 について成立しているので、Gross substitute よりさらに以下の関係性が成立する。

(
)
(
)
1
0
𝑒 𝑧 𝑝𝑧1 , 𝑝 −𝑧
≥ 𝑒 𝑧 𝑝𝑧1 , 𝑝 −𝑧=0つまり 𝑒 𝑧 (𝑝 1 ) ≥ 0 である。以上の議論が順々に成立するので、Jacobi のアルゴリズムで得られる価格列{𝑝 𝑡 }𝑡∞=0 については常に以下の二つの性質が成立することがわかった。
( )1. 任意の 𝑡 に対して 𝑒 𝑝 𝑡 ≥ 0
2. {𝑝 𝑡 }𝑡∞=0 は減少列12ある 𝑧 について 𝑝 𝑧𝑡 → −∞ であるとすると 𝑒 𝑧 (𝑝 𝑡 ) ≥ 0 が常に成立し続けることはできないので、{𝑝 𝑡 }𝑡∞=0

が bounded below な列であることがわかる。以上から {𝑝 𝑡 }𝑡∞=0 は bounded below monotone decreasing★ ) = 0 が成立、つまり均衡価格 𝑝 ★
sequence である。よってこの列は収束し、その収束先 𝑝 ★ では 𝑒 𝑧 (𝑝𝑧★ , 𝑝 −𝑧は存在してかつ Jacobi のアルゴリズムの収束先として計算できることがわかった。

□

ここで初期値を super solution にすることが収束のために大事な要素となっていることに注意する。以下で見ていくように excess supply function が inverse isotone でありさらに全射であれば任意の初期値からの収束を示すことができる*8 。

4.2.3 Surge pricing の均衡の一意性
次に均衡の一意性について考える。このためには Berry, Gandhi and Haile (2013) の結果を使うが、まずはそのモチベーションを確認する。以下ではめんどくさいので 𝑒 𝜎 から 𝜎 をとる。そもそも、均衡の一意性を言いたかったら 𝑒 が injective であれば十分である。すなわち、𝑒 (𝑝) = 𝑒 (𝑝 ′ ) ⇒ 𝑝 = 𝑝 ′ であれば、

𝑒 (𝑝) = 𝑒 (𝑝 ′) = 0 となるとき 𝑝 = 𝑝 ′ であるので均衡はただ一つだと言える。そして injective の十分条件として inverse isotone なる性質を考える。

Deﬁnition 4. 𝑒 is inverse isotone if 𝑒 (𝑝) ≤ 𝑒 (𝑝 ′) ⇒ 𝑝 ≤ 𝑝 ′もし 𝑒 が inverse isotone なら、𝑒 (𝑝) = 𝑒 (𝑝 ′ ) ⇒ 𝑒 (𝑝) ≤ 𝑒 (𝑝 ′ ) ∧ 𝑒 (𝑝) ≥ 𝑒 (𝑝 ′ ) ⇒ 𝑝 ≤ 𝑝 ′ ∧ 𝑝 ≥ 𝑝 ′ ⇒𝑝 = 𝑝 ′ となる。ということで当面の目的は excess supply function (𝑒 (𝑝)) が inverse isotone であることを主張することである。そして Berry, Gandhi and Haile (2013) は以下の二つの性質を満たす 𝑒 は inverse

isotone であることを示した。
1. Gross substitute; 𝑒 𝑧 (𝑝) が 𝑝𝑧 について増加関数、𝑥 ≠ 𝑧 の 𝑝𝑥 について非増加関数∑
2. Law of aggregate supply; 𝑧 ∈𝑍 𝑒 𝑧 (𝑝) が全ての価格 𝑝𝑥 について増加関数
これをもって Berry, Gandhi and Haile (2013) が 𝑢 𝑖 𝑧 , 𝑐 𝑗 𝑧 への制約がなるべく必要なくても均衡の一意性を主張できるフレームワークであると言える*9 。また、Assumption 1,2 の下では surge pricing のモデルで上記二つの性質が成立することも確認できるため、surge pricing の均衡の一意性も確認できた。

4.2.4 Aggregate equilibrium の存在と唯一性の確認
とにかく surge pricing の均衡の存在と一意性が欲しければ、

1. Super solution の存在
2. Gross substitute
3. Law of aggregate supplyの三つがあれば良いということであった。
まず Theorem 1 の証明において価格列が bounded below であることを確認した部分が、𝑒 𝑧 が inverse

isotone の時は sub solution、つまり 𝑒𝑝 ≤ 0 なる価格 𝑝 の存在によっても保証できることが容易に確認できる。従って、先の一つ目の条件 super solution の存在は、より一般的な excess supply function(𝑒 ) については super solution と sub solution の両方が存在することと置き換えられる。
よって、Aggregate equilibrium については、式 (6) において以下の三つを確認すれば良い。

1. Super solution と sub solution の存在*8 詳細は Galichon (June 2021) の mathematical resuls を参照。
*9 これは今回のモデルに限った結果ではなく、Berry inversion 的な場面でも大活躍する結果。具体例もたくさん載っているのでみんな Berry, Gandhi and Haile (2013) を読もう！

13

2. Gross substitute
3. Law of aggregate supply
これらを確認するために以下の notation を導入する。まず 𝑝𝑥 = −𝜇𝑥0 , 𝑝 𝑦 = 𝜇 0𝑦 とし 𝑝 = ({𝑝𝑥 }, {𝑝 𝑦 }) とする。さらに∑𝑄𝑥 (𝑝) = 𝑝𝑥 − 𝑦 ∈𝑌 𝑀𝑥𝑦 (−𝑝𝑥 , 𝑝 𝑦 ) + 𝑛𝑥∑𝑄 𝑦 (𝑝) = 𝑝 𝑦 + 𝑥 ∈𝑋 𝑀𝑥𝑦 (−𝑝𝑥 , 𝑝 𝑦 ) − 𝑚 𝑦とする。こうすると Gross substitute は 𝑄 を微分すれば確認できる。また、aggregate supply は以下の通
りである。

∑
𝑥

𝑄𝑥 (𝑝) +∑𝑄 𝑦 (𝑝) =

𝑦

∑

𝑝𝑥 +

𝑥

∑
𝑦

𝑝𝑦 +

∑
𝑥

𝑛𝑥 −

∑

𝑚𝑦

𝑦

これは 𝑝 について増加関数なので law of aggregate supply を満たす。さらに全ての 𝑧 ∈ 𝑋 ∪ 𝑌 について

𝑝𝑧 = 𝑁 , −𝑁 として 𝑁 を大きくすれば super solution も subsolution も存在することがわかる。よって上記
三つ全ての条件を満たすので logit error の ITU マッチングモデルにおいて Aggregate equilibrium は一意に存在し、coordinate update algorithm で計算することができる。

参考文献
Adachi, Hiroyuki, “On a characterization of stable matchings,” Economics Letters, 2000, 68 (1), 43–49.
Becker, Gary S., “A Theory of Marriage: Part I,” Journal of Political Economy, 1973, 81 (4), 813–846.
Berry, Steven, Amit Gandhi, and Philip Haile, “Connected Substitutes and Invertibility of Demand,”Econometrica, 2013, 81 (5), 2087–2111.
Choo, Eugene and Aloysius Siow, “Who Marries Whom and Why,” Journal of Political Economy, 2006,
114 (1), 175–201.
Gale, D. and L. S. Shapley, “College Admissions and the Stability of Marriage,” The American Mathematical Monthly, 1962, 69 (1), 9–15.
Galichon, Alfred, “’math+econ+code’ masterclass on equilibrium transport and matching models in
economics,” June 2021. https://github.com/math-econ-code/mec_equil.
and Bernard Salanie, “Cupid’s Invisible Hand: Social Surplus and Identiﬁcation in Matching Models,” 2021.
, Scott Duke Kominers, and Simon Weber, “Costly Concessions: An Empirical Framework for
Matching with Imperfectly Transferable Utility,” Journal of Political Economy, 2019, 127 (6), 2875–
2925.
Shapley, Lloyd S. and Martin Shubik, The Assignment Game I: The Core, Santa Monica, CA: RAND
Corporation, 1971.

14