数理経済学と離散最適化の新たな出会い
室田 一雄，田村 明久
州l……l…………‖‖＝‖‖‖‖ml…………llll……………………‖‖‖＝‖川‖州Illll川‖‖‖‖＝川‖‖‖‖‖‖‖‖‖‖………‖‖‖…………………刷‖…………ll…………………lllllll…………………ll…………‖＝‖‖＝川‖‖州争均衡の存在を明らかにした．近年になって，Bikhchan−dani・Mamer（1997），VanderLaan・Tblman・Yang

1． はじめに（1997），Bevia・Quinzii・Silva（1999），Gul・Stac−

数理経済学やゲーム理論と離散最適化との出会いは決Chetti（1999），Yang（2000）などが，効用関数の準線形性

して少なくはない．ゲーム理論で凸ゲームのコアとよばという仮定の下で，不可分財のモデルを扱っている．特れているものと，離散最適化で基多面体とよばれているもに，Gul・Stacchettiでは，効用関数の単調性とKelso・のは，実は同じものである．本稿では，数理経済学と椎散Crawbrd（1982）による租代替性の下で，交換経済での競最適化との新たな出会いについて紹介しよう．この出会争均衡の存在を導いている．同様に効用関数の準線形性

いは，不可分財（非分割材ともいい，自動車や家のようにの下で，Danilov・Koshevoy・室田（2001）では離散凸解

その量が整数値で表現される財）をもつ経済均衡モデルヘ

析の枠組みを用いたモデルが与えられた．この論文の特徴の 離散凸関数 の導入である．維散最適化の立場からは，は，離散最適化ではその重要性が強く意識されている離散離散凸解析 という新しい枠組みの数理経済学への新たな応用である．推散双対性という道具を用いることで，競争均衡における不可分財と価格の関係について見通しを双対性と競争均衡の存在の関係を明確に打ち出したことである．

一方，維散最適化の分野では，マトロイドと劣モジュラ

良くしている．また，競争均衡の計算も乾散最適化アルゴ関数の理論が一つの柱となっている．マトロイドの概念はリズムにより効率的に行なえる．この両分野の出会いをさ

H．Whitneyによって1935年に導入された．マトロイドらに深めたのは，数理経済学における租代替性と離散最適の独立集合（基の部分集合）とマトロイドの階数関数につ化におけるマトロイド性が等価であることの発見である．

いて，交換公理と劣モジュラ性の重要性がWhitneyによ

まずは，数理経済学と離散最適化における関連分野の歴史

りすでに認識されていた．1960年代の終わりには，J．Ed−を振り返ってみよう．

mondsによるポリマトロイド交わり定理という双対定理

数理経済学の分野では，不可分財をもつモデルや競争の発見を契機として，劣モジュラ（集合）関数それ自体の均衡の存在に関する研究が多くなされてきた．Henry研究が盛んになり，劣モジュラ関数と凸関数との類似性が（1970）はすべての不可分財が同一財であるモデルを研漠然とした形で議論された．1980年代はじめになり，集究した． Shapley・Shubik（1972），Shapley・Scarf

合関数の劣モジュラ性と凸性の関係が明確になった．藤重（1974），金子（1982），Quinzii（1984），Gale（1984）は，（1984）は劣モジュラ関数と優モジュラ関数の托nchel型

それぞれの経済主体が一つの財を所有し，高々一つの財し双対定理を，Frank（1982）は劣モジュラ関数と優モジュか消費しないという経済モデルにおいて競争均衡の存在

ラ関数の離散分敗走理を示した．これらはポリマトロイを示している．金子（1982）や金子・山本（1986）は，販

ド交わり定理を書き換えた内容のものであるが，凸解析に売者は同種の不可分財を幾つか所有し，購入者は高々1つおける基本定理との形式的類似性を示した意義は大きい．

の不可分財を購入するという一般化割当市場において競Lov由ヱ（1983）は，集合関数の劣モジュラ性とその線形拡張の凸性とが同値であるという基本的な事実を指摘した．
むろた かずお 京都大学数理解析研究所〒606−8502京都市左京区北白川追分町

これらの結果，東京大学大学院情報理工学系研究科（併任）

劣モジュラ関数巴凸関数〒113−8656文京区本郷7−㌻1

劣モジュラ関数の双対性竺凸関数の双対性＋整数性

たむら あきひさ 京都大学数理解析研究所〒606−8502京都市左京区北白川追分町
180（46）という図式が広く受け入れられた．1990年代に入ってか

オペレーションズ・リサーチ© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

ら，A．DressとW．Wenzelにより，貪欲算法の観点から
付値マトロイドの概念が導入された．付値マトロイドの概y念は，マトロイドの交換公理に着目してこれを一般化したものである．

放散凸解析の枠組みは，1980年代の「劣モジュラ関数
巴凸関数」の議論を背景としながら，付値マトロイド理

J

切

u
＝

論の進展を直接の契機として，1996年頃に室田により提案されたパラダイムであり，その名称は【6】で提唱された・

離散凸解析では，交換公理に基づくM凸関数と劣モジュラ性に基づくL凸関数の概念が中心的役割をなし，これら

図1：交換公理（−Mb−EXC）■

は，離散凸解析で扱われるMb凹関数が数理経済学の観点からも良い性質をもっていることを紹介する．

は互いに共役な関係にある．

【7】では，このM凸関数とL凸関数の共役性から競争均衡における財と価格の共役性を導いた．数理経済学と離散最適化のこの出会いはこれに留まらず，さらなる進展をみせた．それは，集合関数においてM凸性のバリエーションであるMb凸性1と租代替性が等価であるという藤重・Y弧g【4】の発見である・この発見をうけて，【1】と【9】は，それぞれ整数格子点上のM凸関数へと議論を拡張した．
競争均衡の存在だけでなく，アルゴリズムの計算量という観点からも，離散最適化は数理経済学に貢献できるのではないかと思われる．

まずは，Mb凹関数の概念について簡単に説明しよう・
詳しい性質やその出典については【7】を参照されたい・￣

般の凹関数Jは，任意の2点∬とyから互いが直線的に同じ距離だけ近付いた2点∬′とy′に対して
J（ェ）＋J（y）≦J（ヱ′）＋J（y′）という不等式が成立することで特徴付けられる．この性質の意図するところを整数格子点上の世界で表現した性質

によりMb凹関数が定義される．ただし，整数格子点上では2点は一般に直線的には近付けない．そこで，「二つあるいは一つの成分を増減することで近付いた2点におけ競争均衡の典型的な計算法は不動点アルゴリズムを用いたものである．金子・山本（1986）においては，不動点アルゴリズムを用いて住宅市場の髄争均衡が数値的に求められている．しかし，不可分財を扱うモデルに対して，
不動点アルゴリズムでは整数値の解が簡単には求まらな

い．Kelso・Crawford（1982）は，工場と労働者という2グループからなる多対1マッチングモデルに対するアルゴリズムを提案している．このアルゴリズムは有限終了は保証されているものの効率的ではない．

る関数値の和が，元の点の関数値の和よりも小さくならないようにできる」として，この意図をくみとる．例えば，
図1の二つの白丸の点ごとyの五成分∬（五）とy（豆＝こついて大小関係∬（盲）＞y（盲）が成立している・五に関して，この2点を格子上で近付ける方法として，壷成分だけの増減で近付けるもの（網掛けの2点）と，他のメ成分の増減も考慮したもの（黒丸の2点）を考える・これらの近付き方のどれかで関数値の和が減少しないようにできるという性質により，Mb凹性を定義する．厳密には，次のように

維散凸解析では，ネットワークフロー問題の代表格である最小費用流問題が，目的関数がM凸性をもつM凸劣モ
ジュラ流問題へと拡張されている．【10】では，このM凸劣モジュラ流問題を用いて，【2，7】でのモデルの戟争均衡
が多項式時間で計算できることを示している・

2．数理経済学におけるMb凹性
数理経清学において，通常は効用関数が凹関数であると定義する．有限集合∬に対してZ∬上の関数び：Z打→
RU（−∞）がMb凹関数であるとは，Ⅳが次の交換公理（−Mb−EXC）を満たすことである・（−Mh−EXC）任意のx，y∈domUとi∈supp＋（x−y）
に対して，あるメ∈supp￣（ェーy）∪（0）が存在して，ぴ（∬）＋U（y）≦ぴ（∬−Xi＋xブ）＋打（y＋xi−Xj）・

ただし，ぴの実効定義域domぴおよびベクトルz ＝いう仮定をおく．不可分財を扱うときには， 離散凹関数を考えるのが自然であろう．ここでの 妊散 とは，整数（z（i）：i∈K）の正の台supp＋（z）と負の台supp●（z）を格子点Z〝上で定義されていることを意味する2・本節でそれぞれ次のように定義する．

domぴ＝（∬∈Z〝岬（∬）≠一∞），
1Mちはエムナチュラルと読む．

2zは整数全体の集合を表し，Z〝は成分の添字典合が〝である
凶次元整数ベクトル全体の集合を表す・

2002年3月号

supp＋（z）＝（豆∈Ⅳlz（豆）＞0），
supp￣（z）＝（盲∈打Iz（五）＜0）・© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（47）181は，財の購入費という資産の減少まで考慮した総合的な効用を表すと考えられる．この総合的な効用を最大化する消費量の全体が，argmaX研一p】である．すなわち，
argmax研一p】＝価格pに対する最適消費量全体と以下では読み替えて頂きたい．

まずは，どんな関数も満たす性質を紹介する．ベクトルyp，9∈R〝に対して，
図2：劣モジュラ性．

X∈argmaxU［−P］，yEargmaxU［−q］

また，豆⊆∬に対して，Xiをxi（五）＝1，Xi（J）＝0（J≠豆）とする・叫一列（ェ）≧研一p】（y），研一9】（y）≧研一9】（ェ）でで定まる単位ベクトルとし，Xoはゼロベクトルとする．

あるから

Mb凹関数は整数格子点上で定義された関数であるが，（9−p，∬−y〉 ＝（研一p】（∬）一明−p】（y））

これを実数点上でも関数値が定義されるように拡張した＋（研一d（y）一明−9】（∬））≧0

ときに，通常の意味での凹関数が得られることが知られている．このような関数を凹拡張可能という．これは， 雄散となる・特に，9＝p＋αXよ（戎∈打，α＞0）とすると

凹関数 とよぶためには最低限必要な性質であろう．

y（豆）≦∬（五）を得る．これは，財盲だけの価格が上昇した

ここからは，効用関数が満たすであろう性質について考ときに財五の消費量が増えることはないという直観的にえる．ある初期保有量から一定量だけ増分したとき，一般も直ちに理解できる事実を意味している．この主張では戎

に効用の増分は初期保有量が増えるほど小さくなる．こ以外の財については触れていないが，次の粗代替性は，他

れは，経験的にも受け入れられる事実であろう．この性質の財の変化について考慮した性質である．

は限界効用逓減性とよばれるが，柾散の場合にはこの性質

租代替性は，元来は（0，1）一起立方体上の関数（集合関は劣モジュラ性と等価となる（【11】参照）．関数Uが劣モ数）に対してKelso・Crawford（1982）によって定義されジュラであるとは，任意の∬，y∈dom【／に対してたものだが，これを整数格子点上の関数に対して書き換えた（−Mb−GSw）とそのバリエーションを二つ紹介する．

U（ェ）一打（∬∧y）≧U（∬Vy）一打（y）

を満たすことである・ここで，ベクトルェVyと∬∧yは（−Mb−GSw）価格ベクトルp∈R〝に対する最適消費量エ∈Z〟について，価格が9≧pへと上昇したと（∬Vy）（五）＝maX（∬（豆），y（戎））（慮∈∬）（∬∧y）（豆）＝min（∬（豆），y（豆））き，条件9（盲）＝p（盲）⇒y（乞）≧エ（戎）を満たす最適消費量y∈Z∬が存在する．

と定義される（図2参照）．劣モジュラ性は，図2の矢印の示す点の変化に対する関数値の変化の大小を意味している・（∬∧y）≦yかつ∬−（∬∧y）＝（∬Vy）−yであるから，劣モジュラ性はまさに離散版の限界効用逓減性である．Mh凹関数は劣モジュラ性をもつことが知られてい価格が上昇したとき，消費者は価格が据え置かれた財を以
前と同数以上欲するというのが，条件（−Mb−GSw）の意
味である．例えば，輸入車の価格が上昇すれば，価格の高い財は安い財に代替されるという理由で，国産車の消費量は増加する．このとき，国産車は輸入車の粗代替財である

る．

次に，Mb凹関数から離れて，価格の変更に対する効用最大化の消費行動の変化に話しを移そう．記述を短くするという．また，輸入車の価格上昇に伴い，消費量が減少する財（例えば輸入車特有の付属品など）は，輸入車の租補ために，関数打：Z〝→Ru（−∞），ベクトルp∈R下に完財であるという．租代替性は，市場が粗代替財から構成対して，されていることを意味している．

（−Mb−GS）価格ベクトルpに村する最適消費量∬にっ研一p】（∬）＝打（ェ）−（p，エ〉，（p，y）＝∑∈〝p（軸（慮）（y∈Z〝），

いて，価格が9−901に変化したとき，次の条件を満

argmax打＝（∬∈Z打岬（∬）≧U（y）（∀y∈Z〝））

たす最適消費量yが存在する：という表記を用いる．pを財集合∬に対する価格ベクト
ル，打を消費者の効用関数とみなしたとき，関数研一p】

182（48）q（五）＝p（豆）＝＝｝ 訂（五）≧エ（i），
90＝0 ＝⇒ ∑i緒y（豆）≦∑i∈〝項）・© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

ただし，q≧p，90≧0であり，1はすべての要素が1

対する租代替性と単改良性の等価性はGul・Stacchetti

であるベクトルとする．

により示され，さらに集合関数に対する単改良性とMb凹性の等価性は，藤重・Yang【4】によって最初に示された・

価格が上昇したとき（9≧pかつ90＝0），価格据え置きの

一般のMb凹関数は上記5つの条件を満たすが，逆にこれ

財は同数以上，かつ財の総数は増加しないことを消費者がらの条件を用いて特徴付けることもできる．

欲することを，（−Mb−GS）は主張している．さらに，すべての価格が一定値低下したとき（9＝pかつ90＞0），消定理1（【9】）関数び：Z〝→RU（−∞）の実効定義域

費者がどの財も価格変更前と比べて同数以上欲すること

domUが有界であるとき，次の主張は等価である．

も主張している．トMb−GS）は，ある種の価格低下まで考（a）ⅣはMb凹関数である．

慮し七いる点で（−Mb−GSw）より強い条件である．

（b）Uは（−Mb−GS）を満たし凹拡張可能である．

（−Mb−SWGS）価格ベクトルpに対する最適消費量xと盲∈∬について次の少なくとも一方が成り立つ：（c）Uは（−MしSI）を満たす．

（a）財盲のみの価格上昇に対して常に￡は最適消費定理2（【1】）関数び‥Z〝→Ruト∞）の実効定義域
dom打が有界であるとき，次の主張は等価である．

量である，（b）次の条件を満たすα≧0と価格p＋αXiに対す（a）ひはMb凹関数である．

る壕適消費量yが存在する：（b）Uは（−Mh−SWGS）を満たし凹拡張可能である．1
y（豆）＝∬（五）−1，y（j）≧エ（メ）（j≠け
集合関数については，上記で紹介した条件はすべて等価一つの財iの価格が上昇したときに，現在の消費量が最適となり，藤重・Yangの主張を補足している．

であり続けるか，あるいは財哀の適当な価格上昇に伴って盲の消費量をちょうど一つ減らし，他の財の消費量は減少

定理3集合関数に対して，（−Mb−EXC），（−Mb−SI），

しない最適消費量が存在することを，（−Mb−SWGS）は意（−Mb−SIw），（−Mb−GSw），（−Mh−GS），（−Mb−SWGS）

味している．（−Mb−SWGS）は【1】で導入された．

は等価な性質である．

Gul・Stacchetti［5】は，単改良性とよばれる集合関数
に対する性質を提案し，それが租代替性と等価であること

3． モデルを示した．単改良性とそのバリエーションを紹介する．

本稿で扱う経済均衡モデルを説明しよう．経済主体と（−Mh−SIw）x∈domUが価格ベクトルpに対する最

しては生産者と消費者が区別されているとし，生産者の適消費量でないならば，ある豆，J∈（0〉∪∬が存在

集合をエ，消費者の集合をガと表す（エ，ガともに有限集合とする）．財としては，複数個の不可分財と貨幣を考えして研一p】（ェ）＜町っ炬−Xi＋xメ）・

る．ここで，不可分財とは自動車や家のようにその畳が（−Mb−SI）−∞＜Ⅳ卜p】（∬）＜叫−p】（y）ならば，整数値で表現される財であり，貨幣は幾らでも分割できる財とする．不可分財の集合を∬と表し，これも有限集合

研一p】（∬）＜maxmax研一d（ェーXi＋xメ），i∈ざJ∈g￣＋

S＋＝Supp＋（x−y）∪（0），S−＝Supp￣（3：−y）∪†0）．

とする．生産者J∈エの供給量を整数ベクトルを用いて机＝（研（た）‥た∈∬）∈Z〝と表現し，消費者九∈〝の需要量も恥＝（恥（た）：た∈打）∈Z〝と表現する．

条件（−Mh−SIw）は，非最適な任意の消費量xを（i）−つ生産者〜の消費する財豆については飢（りは負の値を耽り，の財を除く，（ii）−つの財を加える，あるいは（iii）この両生産する財メについては研（j）ほ正の値を取るとする．逆方を行なうことで真に改善できること意味する．さらに，に，消費者九の消費する財慮については恥（可は正の値を条件（−Mb−SI）は卜Mh−SIw）よりも強い条件で，消費者取り，労働のような供給する財jについては恥（メ）は負のは任意の消費量エをより良い任意の消費量yに近付けら値を取るとする．生産者と消費者は，与えられた価格ベクれることを主張している．

トルp＝（p（た）‥た∈∬）∈R〝の下で，それぞれ独立集合関数に対しては，（−Mh−GSw）と（−Mb−SIw）は，それぞれ租代替性と単改良性に対応している．集合関数に

2002年3月号に自分の利益や満足度を最大にするように行動して財の生産畳や消費孟を決める．

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（49）183

生産者J∈エは，不可分財をy∈Z〝だけ生産するための費用関数Cl‥Z〟→RU（＋∞）によって記述される．関数値＋00は実行不可能な生産量を意味し，実行可能領域を陽に用いない記述法を採用している（消費者の効用関数でも同様の記述法を用いる）．価格ベクトルp∈R下最大化【九（ェ）＋m
制約条件（p，エ）＋m≦βん（p），m≧0として定式化できるが，dom仇が有界でm完が十分大きいという仮定の下では，m＝βん（p）−（p，∬）と置くことにより，上記の問題は制約なしの最適化問題が与えられたとき，生産者J∈エは，利潤（p，y〉−q（y）を最大化するように生産量飢∈Z〝を定める．（p，y〉は価格ベクトルpに村する生産量yの販売価格を意味する・

生産者J∈エの供給関数g ：R下→2Z片，利潤関数れ：最大化（九（∬）−（p，エ〉に帰着できる．すなわち，消費者ん∈ガの需要関数β九：
R〝→2Z∬はR下→Rは瑚p）＝arg莞欝（柚卜恒））（p∈R〝）抽）＝arg諾欝（如卜C潮）（p∈R〝）
れ（p）＝諾欝（如）−q（y））（p∈R〟）と定義され，勒∈β九（p）かつmん＝β九（p）−（p，∬九）である．需要関数βんを需要対応とよぶこともある．また，集と定義する．このとき，飢∈ぶl（p）が成立している・ここ合β九（p）⊆Z〝を消費者九∈〟の需要集合とよぶ・各消で，∫ （p）＝￠の可能性もあり，その場合には僕給量飢は

費者は，初期保有量と与えられた価格ベクトルに対して，

定義されないと解釈する．供給関数∫Jを供給対応とよぶ

需要集合に含まれるように消費量を決定する．

こともある．また，集合β （p）⊆Z〝を生産者J∈上の供給集合とよび，各生産者は与えられた価格に対して供給集

消費量恥∈Z〝，生産量机∈Z〝，価格ベクトルp∈
R下から成る組（（恥l九∈ガ），（別IJ∈エ），p）が，条件

︵

ん∈〝

l∈エ

p≧0

（4）

九∈ガに対して非負であり，∑ん∈〝‰＝1が任意のJ∈を満たすとき，競争均衡あるいは均衡とよばれ，そのときエについて成り立つ．よって消費者九の所得は，関数βん：の価格ベクトルは均衡価格ベクトルとよばれる．すなわ

R不一→R

ち，それぞれの経済主体は望むことを実現し，需給ノヤラン

βん（p）＝（釣端）＋m昆＋∑宮細（p）（p∈R∬）l∈⊥スが成り立ち，均衡価格ベクトルは非負となる．

本モデルはArrow−Debreu型モデルとよばれるもので，により表現される．財（恥，mん）∈Z〝×Rに対する消費費用関数と効用関数がそれぞれMb凸関数3とMb凹関数

者ん∈ガの満足度は効用関数払：Z〝×R→RU（−∞）となる場合が次節での主題である．

によって表現されるものとし，さらに，ここでは効用関数

4．競争均衡の存在性の準線形性

軋（∬，m）＝仇（ヱ）＋m（（ェ，m）∈Z∬×R）

前節の不可分財をもつ経済モデルが競争均衡をもつための十分条件について紹介する． 関数打：Z〟 →を仮定する．仇‥Z〟→Ru（−∞）は財の価値の貨幣

Ru（−∞）は，すべての∬，y∈dom打に対して，エ≦への換算を意味する．以降は，亡九を効用関数とよぶことy⇒ 打（∬）≦U（y）を満たすとき単調非減少とよばれる・にする．どの消費者も無限の財を消費することは望まな

Gul・Stacchetti［5］は，効用関数が租代替性と単調非減いであろうから，【先の実効定義域は有界であると仮定し少性をもつ交換経済（エ＝￠の場合）における競争均衡のても不自然ではない．ここではさらに，各消費者九の初期存在を示した．定理3から，次の定理4はこの結果の拡張

保有量における貨幣の量m昆が十分に大きいと仮定する・となる．定理4と5は，【2】の結果より導き出せるが，【7】に消費者九は予算制約の下で自らの効用を最大化するよう

おいて陽に述べられている．

に財の消費量（恥，mh）∈Z〟×Rを決定する．よって，消費者んの行動は最適化問題

柑4（50）

3／がMb凸関数とは，．−／が（−Mh−EXC）を満たすことである．

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

︵

h∈〝

︶

∑恥＝∑境＋∑恥生産者J∈上の利潤訂l（p）は，一定の分配率β抽で消費者

オペレーションズ・リサーチ︶

3

飢∈筑（p）（J∈上），

本モデルでは生産者の利潤は消費者に分配されるとする．

ん∈ガに分配される．ここで，β抽はすべてのJ∈エと2ているとし，その保有量を（境，m昆）∈Z〟×Rと表す・∬九∈β九（p）（九∈g），

1︵

消費者九∈ガは，初期段階で不可分財と貨幣を保有し︶合に含まれるように生産量を決定する．

定理4（【2，7】）交換経済において，各効用関数仇がらに，費用関数や効用関数の実効定義域が有界であるとい

単調非減少なMb凹関数ならば，任意の初期総保有量

う妥当な仮定の下で，経済主体の数I叫＋I上l，財の種類ェ○∈∑dom仇に対して，競争均衡（（恥I九∈叫，p）が数囲および実効定義域のサイズの対数に関する多項式

h∈〝

存在する．

t

時間で髄争均衡が求まる．詳しくはド，10】を参照された
い．

定理5（【2，7】）各費用関数CげMh凸関数で冬効用関

参考文献

数【九がMb凹関数であるとする．このとき，すべての財【1】V・Danilov，G・KoshevoyandC・Lang：Grosssub−

を分割可能とした連続モデルにおいて，与えられた初期稔保有量に対する競争均衡が存在するならば，不可分財からStitution，discrete convexity，and submodularity，

成る競争均衡（（和一九∈ガ），（別Iほエ），p）も存在する．こDiscreteApptiedMathematics，tOappear・

こで，連続モデルにおける費用関数はqの凸拡張であり，【2】V・Danilov，G・Koshevoyand K・Murota：Dis−

効用関数は【九の凹拡張であるとする．

●

CreteCOnVeXityandequilibriain economies withindivisiblegoodsandmoney，MathematicalSociaL

競争均衡は一意に定まるとは限らないが，定理5の仮定∫c豆e†lCeβ，41（2001）25ト273．

の下では，競争均衡全体も良い性質をもつ．例えば，任意の競争均衡の生産量・消費量と別の競争均衡の均衡価格【3】S・Fujishige and K．Murota：Notes ollL−／M−

ベクトルの組は再び鏡争均衡となる．まさに，線形計画

COnVeX functions and the separation theorems，

問題とその双対問題のそれぞれの最適解に対する双対性〟α班emα舶cαJPγ叩mmmわ叩，88（2000）129−146．

と同様のことが成立している．これはM凸関数とL凸関【4】S・Fujishigeand Z．Yang：A noteonIくelsoand数の双対性に起因し，均衡価格ベクトル全体はLb凸多面

Crawfbrd体とよばれる良い性質をもつものとなる．なお，凸多面体

sgross substitutescondition，prePrint，（2000）．

P⊆R〟が1b凸多面体【3，8】であるとは，【5］F・GulandE・Stacchetti：Walra5ianequilibriump，9∈P⇒（p−α1）v9，p∧（9＋α1）∈P

Withgrosssubstitutes，JoumaLqfEconomic T7Le−（0≦∀α∈R）

Ory，87（1999）95−124．

を満たすことである．

【6］K．Murota：Discreteconvexanalysis，Mathemati−
CαJProgmmm豆叩，83（1998）313−371．

定理6（【7】）各費用関数qがMb凸関数で各効用関数
亡九がMb凹関数であるとし，初期給保有量∬○に対して競【7】室田一雄‥錐散凸解析（共立出版，2001）．

争均衡が存在すると仮定する．均衡価格ベクトル全体から【8】K・Murota and A．Shioura：Extension of M−

なる集合P＊（ェ○）はLb凸多面体となる．Lb凸多面体は束

COnVeXity and L−COnVeXity to polyhedralconvex構造をもつため，最小均衡価格ベクトルが存在し，P＊（が）が有界ならば最大均衡価格ベクトルも存在する．

■

functions，Advancesin＾ppLiedMathematics，25（2000）352−427．

5．均衡の計算【9】K．MurotaandA．Tamura：Newcharacterizations

各費用関数qがMb凸関数で各効用関数仇がMb凹

OfM−COnVeX functions and their applications to関数である3節のモデルにおいて，競争均衡の存在判定

economicequilibriummodelswithindivisibilities，は，定理5より，連続化したモデルに競争均衡が存在する

β由crefeAp〆ied〟α兢emα出cβ，tOappear．

かを，不動点アルゴリズムなどの非線形アルゴリズムを用【10】K・Murota a．nd A．Tamura：Computation of

いて調べれば良い．しかし，本来は離散的な問題であるのCOnpetitive equilibria．ofindivisible commodities

で離散的なアルゴリズムで解けることが望まれる．幸いな

via M−COnVeX Submodular負ow problem，RIMS

ことに，この間題については最′ト費用流問題を一般化したPreprint1316，KyotoUniversity，（2001）．

M凸劣モジュラ流問題と最短路問題を用いることで，競争均衡における生産宜や消費量および最小均衡価格ベク

トルや最大均衡価格ベクトルも求めることができる．さ2002年3月号【11）D．M．Tbpkis：SupermodularityandComplemen−tarity，（PrincetonUniversityPress，1998）．

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（51）185