修士論文 要旨

付値マトロイド交差アルゴリズムの高速化と社会的厚生最大化問題への応用
数理情報学専攻 48226229
指導教員

原 慶伍
谷川 眞一 准教授

したときの「利益」を表すとも捉えられる．

1 はじめにここで，評価関数 vi (i ∈ [m]) が粗代替性と呼ばれる

n 個の不可分財を m 人の購入者に分配し，各購入者性質を満たすとすると，ある分配および価格の組が存在の財の評価値の和で表される社会的厚生関数を最大化して，財が全て分配されて各購入者の効用が最大になっする問題，すなわち社会的厚生最大化問題を考える．各ている状態，すなわちワルラス均衡が存在することが知購入者の財の評価関数が粗代替性という性質を満たすられている．さらに，ワルラス均衡が成立する分配は，とき，社会的厚生最大化問題は付値マトロイド交差問題

社会的厚生関数を最大化することが知られている．

へ帰着可能であることが知られており，Tv-val を評価値

粗代替性を仮定すると，ワルラス均衡は多項式時間でを計算するオラクルの計算時間として，Murota [1] の計算可能である．特に，Murota [1] は付値マトロイド付値マトロイド交差問題アルゴリズムを適用すること交差問題に対する組合せ的アルゴリズムを提案していで O(mn log(m + n) · Tv-val ) 時間で解ける．本論文でるが，室田による離散凸解析の枠組みによって詳細な解は，付値マトロイド交差問題の特殊ケースである重み付析が行われている粗代替性関数の数学的特性により，ワきマトロイド交差問題に対する高速化技法の近年の急ルラス均衡の計算は付値マトロイド交差問題に帰着す速な発展に着目し，Murota [1] の付値マトロイド交差る．具体的には，台集合 V を V = [mn] = {(i, j)|i ∈問題アルゴリズムの高速化および社会的厚生最大化問[m], j ∈ [n]} と定義し，1 つ目の付値マトロイド M1 =題への応用について議論する．具体的には，2022 年に(V, B1 , ω1 ) を [mn] 上の n-一様マトロイド，付値 ω1 をTu [5] によって提案された重み付きマトロイド交差問
題に対するアルゴリズムを，独自に定義するオラクルをS ∈ B1 を X = (X1 , . . . , Xm ) (∀i ∈ [m], Xi ∈ 2[n] )Pと同一視して ω1 (S) =i vi (Xi )，2 つ目の付値マト使用しながら付値マトロイド交差問題へ拡張する．

ロイド M2 = (V, B2 , ω2 ) を ω2 = 0 で定義した分割3マトロイド（ここでは，全ての財 j ∈ [n] について

2 問題設定と先行研究

Cj = {(1, j) . . . , (m, j)} と定義したとき，|S ∩ Ci | ≤ 1

任意の k ∈ Z≥0 について [k] := {1, 2, . . . , k} とし，財の集合と購入者の集合をそれぞれ [m] および [n] で表が成り立つとき，S ⊂ ∪ni=1 Cj は独立集合であると定義する），重みを w = 0 で定めれば良い．

→ R≥0 を持つ．

本研究では，重み付きマトロイド交差問題の最新のXi を購入者 i が所有する財の組合せとし，ベクトルアルゴリズムおよび最速な計算時間を提示する，Tu [5]X = (X1 , . . . , Xn ) でそれぞれの購入者が所有する分の高速化技法を応用する．[5] は，n̂ をマトロイドの台配を全て表す．このとき，X が [n] の分割となってい集合の大きさ，r をマトロイドの階数，および Trank をるとき，X を分配と呼ぶ．分配 X の下での購入者の3/4e
階数オラクルの計算時間として O(n̂r· Trank ) 時間の評価関数の和アルゴリズムを構築し，これは階数オラクルを使用してす．全ての購入者 i は評価関数 vi : 2P[n]i∈[m] vi (Xi ) を，社会的厚生関数と呼ぶ．購入者の人数 m，不可分財の数 n，および各購入者eO(n̂r)
未満の計算時間で厳密解を求める，最初のアルi ∈ [m] の評価関数 vi が与えられているとき，社会的厚ゴリズムである．[5] のアルゴリズムは 2 つのステップ

生関数の最大値およびその最大値を実現する分配 X をからなる．1 つめのステップでは，Shigeno and Iwata計算する問題を社会的厚生最大化問題と呼ぶ．

[4] のアルゴリズムを活用して近似解を計算し，2 つ目

全ての財 j ∈ [n] に対して価格 pj ∈ R≥0 が設定されのステップでは，近年発見されている，平衡二分探索木る状況を考える．全ての財の価格を表す価格ベクトル上での二分探索によりマトロイドの交換関係を効率的を p = (p1 , . . . , pn ) ∈ Rn
≥0 で表す．このとき，各購入に見つける手法を活用して効率化された増加路探索を者 i それぞれの効用を vi (X) −j∈X pj ) で定義する．

適用する．辺に重みのある交換可能性グラフにおいて財の組合せ X を所有する購入者 i の効用は，X を購入全ての辺を陽的に構築せずに最短路木を効率的に計算P

付値マトロイド交差アルゴリズムの高速化と社会的厚生最大化問題への応用 (原 慶伍)

する手法は，[5] 独自の貢献となっている．

れる．

3 本研究の貢献

提案アルゴリズムの計算時間は，ℓ = 3/4 としてeO(n̂r3/4 · Tmax-mg ) となる．特に，ワルラス均衡を計算

本研究では，2 つのアルゴリズムを考察した．1 つ目する場合は，ω1 の m 個の関数の和で表されるというのアルゴリズムは Shigeno の博士論文 Shigeno [3] によ

構造を活かして O(m log n + n log n · Tv-val ) 時間の最り構築されているものである．2 つ目のアルゴリズムは大周辺利得オラクルが設計可能であり，全体の計算が前者のアルゴリズムを改良したものであり，本研究の貢e 2 n7/4 + mn11/4 · Tv-val ) 時間で可能であることをO(m献となる．前者のアルゴリズムは後者のアルゴリズム示した．これは [1] の増加路アルゴリズムをそのまま適の基礎をなすため，詳細に考察している．

3e用した場合の O(mn· Tv-val ) 計算時間の改善となる．

3.1 Shigeno [3] のアルゴリズム

また，現段階において社会的厚生最大化問題に対する最Shigeno [3] のアルゴリズムでは 2 つのステップが速なアルゴリズムである Paes Leme and Wong [2] の繰り返させれる．1 つ目のステップでは，ϵ > 0 とeO((mn+ n3 ) · Tv-val ) 時間アルゴリズムと比較すれば，したときの重みの近似分割 w(x) ≤ w ϵ (x) ≤ w(x) +m = o(n1/4 ) の場合は高速化を達成している．

ϵ, w ϵ (x) = w1ϵ (x) + w2ϵ (x) を新しく設定する．そこかPら，ω[w](S) = ω(S) + {w(u)|u ∈ S} (S ⊆ V ) と4 今後の展望

して，S1 ∈ B1 が ω1 [w1ϵ ] 極大，S2 ∈ B2 が ω2 [w2ϵ ]Paes Leme and Wong [2] のアルゴリズムでは交換可極大であることを保ちながら，Shigeno and Iwata [4]能性グラフの辺の本数が高々 O(n2 ) 本にまで削減され，により提案された重みの調整をしながら頂点の交換e 2 ) にまで高速化され各反復の増加路の計算時間が O(nを繰り返す．0 ≤ ℓ < 1 を満たす定数 ℓ をパラメーる．この簡略化された構造において本論文で使用したタとして，これを |S1 ∩ S2 | ≥ r − O(r) となる技法を直接的に適用する場合は，平衡二分探索木の実装近似解を得るまで繰り返す．2 つ目のステップでは，がボトルネックとなるため，さらなる高速化は今後の課

Murota [1] と同様に交換可能性グラフを陽的に構築

題となる．

1−ℓした上でダイクストラ法により増加路を計算し，増加路に沿った S1 , S2 の更新を O(r 1−ℓ ) 回繰り返す．こ

参考文献の 2 つのステップを経た ϵ 近似の改善を ϵ が十分小

[1] K. Murota. Valuated matroid intersection ii: Al-さくなるまで繰り返せば，Tω−val を付値を計算する

gorithms. SIAM Journal on Discrete Mathemat-オラクルとして付値マトロイド交差問題の最適解がics, 9(4):562–576, 1996.

2−ℓeO(n̂r· Trank + (n̂2 rℓ + n̂r2−ℓ ) · Tω−val + n̂ log n̂r1−ℓ )時間で得られる．

3.2[2] R. Paes Leme and S. C.-w. Wong. Computing walrasian equilibria: Fast algorithms and structural

提案アルゴリズム

properties. Mathematical Programming, 179(1-2):

提案するアルゴリズムでは，Shigeno [3] のアルゴリズムにおいて，Tu [5] と同様の手法を使うことにより，343–384, 2020.
[3] M. Shigeno.

A Dual Approximation Approach

最適な頂点の交換関係ないし交換可能性グラフにおけto Matroid Optimization Problems. Phd thesis,る辺の計算を効率化する．

Tokyo Institute of Technology, 1996.

ここでは，「最大周辺利得オラクル」と名付けられる，[4] M. Shigeno and S. Iwata. A dual approximation

付値 ω ，基 S ，集合 U ⊆ V ，頂点 s ∈ S が与えられたと

approach to weighted matroid intersection. Oper-き，arg maxu∈U ω(S, s, u) = ω(S \ {s} ∪ {u}) − ω(S)ations research letters, 18(3):153–156, 1995.

を Tmax-mg 時間で求めるオラクルを仮定する．最大周[5] T.-W. Tu. Subquadratic Weighted Matroid In-

辺利得オラクルを仮定すれば，Shigeno [3] のアルゴリ

tersection Under Rank Oracles. In S. W. Bae

ズムのステップ 1 における頂点の交換の計算時間が再and H. Park, editors, 33rd International Sym-評価できる．また，[5] の技法を応用し，交換可能性グ

posium on Algorithms and Computation (ISAAC

ラフを陽的に構築せずに最大周辺利得オラクルを用い2022), volume 248 of Leibniz International Pro-て最短路木の辺を効率的に探索すれば，ダイクストラ

ceedings in Informatics (LIPIcs), pages 63:1–

法による増加路探索は O(n̂ r · Tmax-mg ) 時間に改善さ

63:14, Dagstuhl, Germany, 2022.

√