近畿地区 数理経済学 ジョイント・セミナー (春季)
─『経済学の方法と数理』─ 2014.3.26 於大阪大学

報告概要

A Unified Approach to Optimization Problems via Metzler Functions
増澤 拓也

1. メッツラー関数とは競争均衡が大域的に安定になることが明らかにされたのは、20 世紀における大きな成果である。レオン

メッツラー関数 1 とは、n 次元のベクトルから nチェフの投入算出分析に関する稼働可能性の条件、次元ベクトルへの関数で、添字の i と j とが異な国際貿易理論も主要な応用範囲である。

るとき、関数値の第 i 座標 f i (x) が第 j 変数 xj に二階堂副包「経済のための線型数学」 (1961, 培風

関して単調非減少なものと定義される (図 1)。メッ館)、同「現代経済学の数学的方法」(1960, 岩波書店)

ツラー関数は、単調関数の自然な拡張と捉えることでは、いずれもメッツラー行列に関して多くのペーも可能であり、応用性が広くわかりやすい概念であジを割いている。一方、近年の代表的なミクロ経済る。その典型的な例は、粗代替性をもつ超過需要関学の教科書 Mascollel, Whinstone and Green「 Mi-croeconomic Theory 」 (1995, Oxford Univ Press)

図 1: メッツラー関数
添字入力において、メッツラー行列は 1000 ページ近い大著の出力わずか数ページを占めるにすぎない。
しかし、メッツラー行列への明確な言及は減っても、実際にはメッツラー行列の応用研究は行われて単調非減少いた。1970 年代以降展開されてきた、n 次元から１次元への優モジュラー関数 (劣モジュラー関数) は、微分がメッツラー関数となる関数である。その応用である、優モジュラーゲームにおいて強調されてきた性質は、個別の利得関数がすべて優モジュラー関数であるとき、最適反応関数がメッツラー関数にな数である。粗代替性をもつ超過需要関数にしたがえることにほかならない 2 。

ば、第 i 財の超過需要は、ことなる第 j 財の価格に本報告では、メッツラー関数が簡明な理論を持ち、関し単調に増加する。

応用が十分にあり、優モジュラー関数よりも射程がこのようなメッツラー関数に関する数学理論は、古広いことをしめす。

くから一般均衡分析において役立てられてきた。い2 優モジュラー関数の経済学での展開をリードした諸文献においては、メッツラー行列に関する既存研究への詳しい言及はなく、そmetrica) の研究が元になって、粗代替経済において のつながりは明らかにされてこなかった。Bulow, Geanakoplos,and Klemperer (1985, Journal of Political Economy), Top1 メッツラー関数の名称は、経済学者 L. Metzler (1913-1980)kis ”Supermodularity and Complementarity”(1998, Oxfordにちなんだものであるメッツラー関数の符号を逆転させたものは、 Univ Press) などを参照せよ。また、Milgrom and Shannon
数理最適化の分野で Z 関数と呼ばれている(1994, Econometrica) における粗代替経済への言及も参照せよ。

わゆるヒックス条件に関する Metzler (1945 Econo-1

2. 基本的な定式化とアルゴリズム

要十分条件は、任意の迂回ルートよりも距離が短いことである。一般に任意の辺の最短迂回距離は、他添字の集合を {1, 2, . . . , n} とし、各変数 xi の定の辺の距離づけにたいして、単調非減少である。し義域を実数の有界閉集合、ai を実数としたとき、ベたがって、各辺の距離づけに対して、最短迂回距離

クトル (x1 , x2 , . . . , xn ) に関する 条件を与える関数はメッツラー関数である。そして、最f (x , x , . . . , x ) ≥ a or x = 0 for i = 1, 2, . . . , n. 短経路は最大補償問題で特徴づけられ、ベルマン=フォードのアルゴリズムがこれを解く単調アルゴリを考えよう。このとき、条件をみたすベクトルのなズムになる。
i12niiかで、最大元 を求める問題を最大保障問題と呼ぶ。
最大保障問題の最大元は必ず存在し、それは単純な二部マッチングは、企業への労働者の就職など、2つの集団間でのマッチングを問題にするものである。

アルゴリズムで見つけることができる。実際、関数それぞれの現行の相手よりも、互いを高く評価するの定義域が有限の連続した自然数であるとき、そのようなペアが存在するとき、現行のマッチングは不アルゴリズムは次のようになる。

安定であるとされる。企業の選択関数にたいする代単調アルゴリスム

替可能性とよばれる想定は、応募者の集合にたいしMasuzawa (2008 Int. Jour. Game Theory)て非採用者を定める関数がメッツラー関数であることを意味している。安定的なマッチングは、最大保1. xi := max X i for all i ∈ N ;障問題で特徴づけられ、ゲールとシャプレーのアル

2. S := {i|ui (x) < ai and xi > min X i } ;ゴリズムはその単調アルゴリズムになる。

3. if S = ∅, then stop;

単記移譲式の選挙は、票のとりすぎによる同士討ちの可能性を排除する選挙方法である。そこでは、

4. xi := xi − 1 for all i ∈ S;

有権者は候補者に対するランキングを投票し、当選ライン以上に票のとりすぎた候補は、ランキングに5. Jump to 2.

したがって他の候補に票を移譲する。ある候補の票関数 f が超過需要関数であるとき、ai = 0 とおの移譲率をふやすと他の候補の得票が増加するので、けば最大保証問題は競争均衡価格を定義し、単調ア各候補の移譲率から得票への関数はメッツラー関数

ルゴリズムはいわゆるオークションアルゴリズムにである。最終的な票の移譲率をきめるアルゴリズムなっていること、すなわち、ある種の模索過程になっは、単調アルゴリズムである。ていることがみてとれる。実際、最大元の存在定理

懲罰優位関係をもつゲームとは、利得関数がメッは、Kuga (1965 Econometrica) によって初めて考察された、粗代替経済の均衡の存在の別証明を与える。

ツラー関数になるような状況である。利得関数は、全プレーヤーの行動のリストに対して、各プレーヤーの利得を与える関数である。この形式で表されるの

3. 新しい応用例

は、クールノーの寡占市場モデル、公共財の供給モ

本報告では、メッツラー関数の新たな応用を示す。

デルなどがある。このゲームの利得ベクトルがコアに属するか否かを決定する問題は、最大保障問題に最短経路問題は、2 つの地点の最短距離を求める問なる (Masuzawa , 2008, Int.Jour. Game Theory)。

題である。一つのルートが最短経路であることの必2

4. 優モジュラー関数との関係

利得の交換を許さない NTU 提携型の枠組みでは、次のように定義される α-NTU ゲーム V α : 2N →→優モジュラー関数の微分がメッツラー関数になるℜN をとりあげる。という関係はよく知られている。しかし、与えられS

αxxたメッツラー関数のヤコビ行列が対称でないときは、 V (S) := ∪ ∩その関数は優モジュラー関数の微分とはならない (図N \S{aS ∈ ℜS : ai ≤ ui (xS , xN \S )}.

メッツラー関数は、つぎのように定義される強い優2)。

加法性という性質で特徴づけることができる。任意の S, T ∈ 2N \ {∅} と xS∪T ∈ ℜS∪T にたいして、

図 2: 微分とメッツラー関数

xS ∈ V α (S) かつ xT ∈ V α (T )優モジュラー関数ならば xS∪T ∈ V α (S ∪ T ).

二階連続微分可能
微分すなわち、次の事実がなりたつ (図 3 を参照)。

全射
メッツラー関数メッツラー関数

完全積分可能完全積分不可能

連続微分可能連続微分可能

微分

微分

全射

全射

メッツラー行列値

メッツラー行列値

対称

非対称

各行完全積分可能

各行完全積分可能

連続

連続(1) 上半連続でコンパクトな定義域をもつメッツラー関数の α-NTU ゲームは、強い優加法性をもち、各値 V (S) の極大元の集合が有界な NTUゲームになる。

(2) 強い優加法性をもち、各値 V (S) の極大元の集合が有界になる NTU ゲームは、なんらかの上半連続でコンパクトな定義域をもつメッツラー関数の α-NTU ゲームになる。

本報告では、微分にかわって、提携型ゲームの構成という点に注目する。まず、利得の和に注目する

TU 提携型の枠組みでは、戦略型ゲーム uN : X N →ℜN

図 3: 提携型ゲームとメッツラー関数

にたいして、次のように定義される α-TU ゲー

メッツラー関数ム v α : 2N → ℜ をとりあげる。

v α (S) := max min

xS xN \S∑

定義域コンパクト
上半連続

ui (xS , xN \S ).

部分クラスi∈S

このとき、任意の優モジュラー関数は適当なメッツαTU ゲーム

ラー関数 uN : X N → ℜN の α-TU ゲームとし全射て表現される (図 3 左側矢印)。しかし、任意のメッαNTU ゲーム
全射NTU ゲーム
強い優加法性の優モジュラー関数

ツラー関数から構成した α-TU ゲームが、優モジュ極大元が有界ラーになるとは限らないことをしめす。つまり、優モジュラー性は、メッツラー関数を完全に特徴づけることはできない。

(この頁にて了)3