1

競争均衡の計算に対する反復オークションの計算量解析---離散凸解析によるアプローチ--塩浦昭義
東北大学 大学院 情報科学研究科
2014/03/25 最適化研究集会 （政策研究大学院大学）
室田一雄氏（東京大），Zaifu Yang 氏（Univ. York, UK）との共同研究

2

１つの財のオークション• Ascending オークション（English オークション）• 価格を徐々に（1単位ずつ）上げる• 購入可能なオークション参加者が1人になったら終了

落札価格
3400

3,300円

10,000円

500円
2,000円

3100

2人

2100

3人

1000

4人

500

5人

3,000円

今日の話：複数の異なる品物のオークション

1人

3

発表の概要
• Ausubel (2006)の複数財に対する Ascending Auction を

離散凸解析の視点から理解• 効用関数 の 粗代替性
＝ Ｍ♮凹性• 間接効用関数＝ L♮凸関数 (共役性)• Lyapunov 関数 の最小化 ＝ L♮凸関数 の最小化
• オークション＝ L♮凸関数最小化アルゴリズム
主結果：• 種々の型のオークションの提案(English, Dutch, English-Dutch, Greedy)• オークションの反復回数解析

4オークションのモデル• 商品の集合• 各商品の個数は1と限定• m 人の参加者(bidder)で商品を分け合う• 参加者の効用関数
商品セットの満足度（単位：お金）

①

②

③

④⑤

5

効用関数の例①②③④⑤• ①を含む商品セットは100，それ以外は０ (single-minded)• 重み和（①：50, ②：70，③：40，④：30，⑤：100） (additive)• 商品セット（①：50, ②：70，③：40，④：30，⑤：100） の中の一番良い商品にのみ依存 (unit-demand){①, ②，③}満足度70, {③, ④, ⑤}満足度100• 商品数依存 (symmetric & concave)（1つ：100, 2つ：180, 3つ：240, ４つ：280，5つ：300）

6

間接効用関数と需要集合• 財の価格ベクトル• 定義：間接効用関数•∈• 定義：需要集合•∈

価格 の下で最も欲しい商品セット全体

例：のとき• Ａさん： ①を含む商品セットは100，それ以外は０
• Ｂさん： 重み和（①：50, ②：70，③：40，④：30，⑤：100）
• Ｃさん：商品数依存（1つ：100, 2つ：180, 3つ：240, ４つ：280，5つ：300）

商品数２または３7競争均衡
価格 の下で最も欲しい商品セット全体• 財の価格ベクトル• 定義：需要集合•∈• 定義：価格ベクトル ∗ と の分割

価格 ∗ の下で皆が最良の商品セットの組は競争均衡∗∗ は均衡価格例：• Ａさん：• Ｂさん：• Ｃさん：
と分割のとき

商品数２または３は競争均衡

8効用関数の粗代替性
粗代替性≒ ある商品が値上がりしたら，他の商品の欲しさが高まる• 定義：効用関数

は粗代替性(gross-substitutes property)を満たす
，,s.t.
∈

9

粗代替性を満たす効用関数の例①②③④⑤• ①を含む商品セットは100，それ以外は０ (single-minded)• 重み和（①：50, ②：70，③：40，④：30，⑤：100） (additive)• 商品セット（①：50, ②：70，③：40，④：30，⑤：100） の中の一番良い商品にのみ依存 (unit-demand){①, ②，③}満足度70, {③, ④, ⑤}満足度100• 商品数依存 (symmetric & concave)（1つ：100, 2つ：180, 3つ：240, ４つ：280，5つ：300）

10

効用関数の粗代替性
粗代替性≒ ある商品が値上がりしたら，他の商品の欲しさが高まる• 定義：効用関数

は粗代替性(gross-substitutes property)を満たす
，,s.t.
∈定理[Kelso-Crawford(1982), et al.]：は粗代替性を満たす  競争均衡が存在定理[藤重-Yang03]：は粗代替性を満たす はM♮凹関数

 離散凸解析

11

反復オークション（Iterative Auction）• 均衡価格（および配分）を求めるためのプロトコル（アルゴリズム）• オークション主催者は繰り返し価格を更新• 参加者は要求された情報を提示．
• ただし，効用関数の情報は陽に公開しない

Step 0. initial prices
Step 1. bidder reports all desired item sets in∗
Step 2. If partition ∗ ∗s.t. ∗ stop ( is equibiruim prices)
Step 3. update . Go to Step 1.
ascending auction:が単調非減少需要大価格を上げる
需要小価格を下げる

12

Lyapunov 関数 (Ausubel 2006)

性質: (i)(ii)(iii)
はは劣モジュラ
は の最小解 は整数最小解をもつ均衡価格の最小解  0 は の劣微分に含まれるの劣微分の劣勾配
∗

供給と需要の差

Ausubel, L. M. (2006): An efficient dynamic auction for heterogeneous commodities.
Amer. Econ. Rev. , 96, 602--629.

13

Lyapunov 関数 (Ausubel 2006)

性質: (i)(ii)(iii)

は劣モジュラは の最小解 は整数最小解をもつ

均衡価格

Ascending Auction
Step 0:sufficiently small integral vector (e.g., 0)minimizingusing
Step 1: find
Step 2:
 stop ( is equilibrium)， Go to Step 1
Step 3:110
10Ausubel, L. M. (2006): An efficient dynamic auction for heterogeneous commodities.
Amer. Econ. Rev. , 96, 602--629.

14

離散凸解析

(Murota 1996)

2種類の離散凸性:M♮-convex / L♮-convex
離散ルジャンドル変換による共役性

15

発表の概要
• Ausubel (2006)の複数財に対する Ascending Auction を離散凸解析の視点から理解• 効用関数 の 粗代替性
＝ Ｍ♮凹性• 間接効用関数＝ L♮凸関数 (共役性)• Lyapunov 関数 の最小化 ＝ L♮凸関数 の最小化
• オークション＝ L♮凸関数最小化アルゴリズム
主結果：• 種々の型のオークションの提案(English, Dutch, English-Dutch, Greedy)• オークションの反復回数解析

16♮
M -convex Function

M♮-convex fn:
Def：(Exchange Axiom)(Murota-Shioura 99)

is M♮-convex :(i),or(ii)variant of M-convex (Murota 96)
yｊix

17L♮-convex Function
Prop： Continuous fn

is convex

 mid-point convex：
Def：
is L♮-convex
 discrete mid-point convex：

22

18

離散凸解析によるAscending Auctionの解析
定理[藤重-Yang03]：は粗代替性を満たす はM♮凹関数共役性定理
定理: Lyapunov 関数 --- L♮-convex
Ascending Auction --- L♮-convex 関数最小化の最急降下法• 反復回数の既存のバウンド: Murota (2003), Kolmogorov-Shioura (2009)• 解析の改善  最急降下法の厳密なバウンド定理:∗ trajectory of∗∗--- 均衡への「最短路」

19

Lyapunov 関数 (Ausubel 2006)

性質: (i)(ii)(iii)

は劣モジュラは の最小解 は整数最小解をもつ

均衡価格

Ascending Auction
Step 0:sufficiently small integral vector (e.g., 0)minimizingusing
Step 1: find
Step 2:
 stop ( is equilibrium)， Go to Step 1
Step 3:1
10
10Ausubel, L. M. (2006): An efficient dynamic auction for heterogeneous commodities.
Amer. Econ. Rev. , 96, 602--629.

20

その他のオークションアルゴリズム• Ascending Auction (English)• Descending Auction (Dutch)• Greedy Auction• Two-Phase Auction (English-Dutch)

21

Greedy Auction
Step 0:any integral vector
minimizing
Step 1: find
Step 2:
stop ( is equilibrium)，Go to Step 1
Step 3:
Thm: tight bound∗∗∗∗• merit• any initial vector can be used
• less # of iter.
• demerit• non-monotone w.r.t. prices

∗

∗

22

Two-Phase Auction (English-Dutch)
Ascending
Step 0:any integral vector+ Descending Step A1: findminimizing
Step A2:
 go to Step D1，Go to Step A1
Step A3:
minimizing
Step D1: find
Step D2:
stop ( is equilibrium)，Go to Step D1
Step D3:• merit• any initial vector can be used
• almost monotone w.r.t. prices• demerit• much more iterations than Greedy

Thm: # iters ≦ 3 ✕ (# iters of Greedy)

23

Andersson & Erlanson (2013) との関係
• Andersson, T., Erlanson, A. (2013):

gross subst.
valuationの特殊ケース

Multi-item Vickrey-English-Dutch auctions.
Games Econ. Behav., 81, 116-129• unit-demand auction: 一番良い item 一つだけを選択• iterative auction の反復回数に注目• 既存のアルゴリズム：反復回数大English 型(Demange et al. 1986, Mo et al. 1988)
Dutch 型(Mishra & Parkes 2009)• English-Dutch 型の iter. auction を提案
反復回数の上界値(理論値），数値実験による評価

24

Andersson & Erlanson (2013) との関係：
我々の研究成果• 既存のアルゴリズム：

English 型(Demange et al. 1986)
Dutch 型(Mishra & Parkes 2009)• English-Dutch 型(Andersson & Erlanson 2013)

前出のiter. auctionを特殊化したものに一致

既存：over-demand, under-demand の用語で記述
 Lyapunov fn を使って書き換え可能• 正確な反復回数に関する我々の結果

 English-Dutch型に対する結果(Andersson & Erlanson 2013)

25

発表の概要
• Ausubel (2006)の Ascending Auction を離散凸解析の視点から理解• 効用関数 の 粗代替性
＝ Ｍ♮凹性• 間接効用関数＝ L♮凸関数 (共役性)• Lyapunov 関数 の最小化 ＝ L♮凸関数 の最小化
• オークション＝ L♮凸関数最小化アルゴリズム• 種々の型のオークションの提案(English, Dutch, English-Dutch, Greedy)• オークションの反復回数解析