数理情報学 小野2 最近の更新履歴 小野 廣隆 (Hirotaka Ono)

数理情報学I

名古屋⼤学⼤学院情報学研究科 数理情報学専攻

⼩野廣隆

ー

⽉ ⽇：⼩野： 多様 最適化問題: 結婚 ー ョ ⁽¹⁾

⽉ ⽇：⼩野： 多様 最適化問題: 結婚 ー ョ ⁽²⁾

⽉ ⽇：柳浦： 組合 最適化: ー 問題 予算問題(1)

⽉ ⽇：柳浦： 組合 最適化: ー 問題 予算問題(2)

⽉ ⽇：胡： 問題解決 最適化 ー

⽉ ⽇： ー ： Probability distributions

⽉ ⽇： ー ： Entropy, information measures, and their use

⽉ ⽇：⻄村 線形代数 確率(1)

⽉ ⽇：⻄村 線形代数 確率(2)

⽉ ⽇：吉信： Cantor 集合論

⽉ ⽇：⽊原： 計算可能性 性(1)

⽉ ⽇：⽊原： 計算可能性 性(2)

⽉ ⽇：松原： 無限集合 い

⽉ ⽇：佐藤： 素因数分解 ⼀意性 意味

成績評価

• _{ー ー or 試験}

– _{ー ：}

• _{組合 最適化・ 論}

• _量⼦情報

– _：

• _{数学基礎論・数理論理}

• _数論

• _評価

– _{全 提出・出席 前提} – _{上位 ー 元 成績}

– _{S さご%以下 ，上位 ー 差 出 い} そ 他 ー 成績 ⾒ 判断

⼩野 研究

• _{ー ョ ・ ー ，}

• _{理論・最適化}

– _最適化

– _近似

– _{固定パ ー}

– _{計算量・計算複雑度} – _{計算困難・近似困難}

– _{的 ー 理論}

– _{ー 分析}

今回・次回 話

• _{⾒合い 最適戦略}

最適停⽌問題

• _{駆 落 い結婚 い}

安定

• _{ー ョ 理論⼊⾨}

駆 落 い結婚 い

駆 落

• _{辞書的な定義：}

– _{恋 あう男⼥ 連 ⽴ そ 他 地 逃} 岩波国語辞典

– _{駆け落ち 愛 合 い 男⼥}

⼀緒 親 許 い事情 あ

親 知 い 同棲⽣活

⼀緒 逃 ^wikipedia

• _{， 許 い事情 互い}

パー ー

い わ 限定

駆 落

1

2

A

B

実 2

⽅ 好1 実 A

⽅ 好B

数理的 化

• _{好 度 順番付}

1

2

A

B

1: B A A: 2 1 2: A B B: 1 2 1: B A A: 2 1 2: A B B: 1 2 1: B A A: 2 1 2: B A B: 1 2 1: B A A: 2 1 2: B A B: 1 2

駆 落起 ！ 駆 落起 い！

駆 落起 ！ 駆 落起 い！

安定 ⼀般的

• _{同数 男⼥ い}

• _{男性 ⼥性 対 選好順序 持}

• _{⼥性 男性 対 選好順序 持}

• _{駆 落 起 い 求 ？}

1: a c b d e a: 2 1 3 4 5 2: c a e b d b: 2 1 4 5 3

3: b a e d c c: 1 2 3 5 4 4: c b d e a d: 3 1 4 2 5

駆 落 ！

キ

• _{駆 落 ⼼配 あ}

• M m _{相⼿： M(m)}

• M w _{相⼿： M(w)}

• m ^w _キ

⇔ (1) M(m) ≠ w M(w) ≠ m

(m w _{い )}

(2) m M(m) w _好 (3) w M(w) m _好

• _{キ い}

安定 呼ぶ

安定結婚 安定

• _{安定結婚問題：}

与え 選好順序 対 ，安定 求

．

• 1962年: Gale, Shapley 提案

– _{発端 ー} 病院配属 1950年以前

– ⻘⽥刈 や複数 病院 仮契約 結ぶ ー 存在 問題

– 1950_{年 双⽅ 希望 出 体制}

• _性質

– _{安定 常 存在}

そ そ ⽐較的簡単 ⾒

Gale-Shapley

• _{う 選好順序 対 安定}

⾒

• _{実⾏中，各男性，⼥性 ー，婚約中} 2_状

態 い 取

• _{最初 全員 ー}

• _以下 ー 男性 い 限 繰 返

1. _{ー 男性 ，現在 い ⼥性}

ー

2. _{ー 受 ⼥性 ，現在 ー 婚約，}

婚約中 今 婚約者 ー 男性 ⽐較，

好 ほう 選 ，婚約

3. _振 男性 ，そ ⼥性 ⾃分 削除．

Gale-Shapley _実⾏

例

1: a c b d e a: 2 1 3 4 5 2: c a e b d b: 2 1 4 5 3

3: b a e d c c: 1 2 3 5 4 4: c b d e a d: 3 1 4 2 5 5: c d b e a e: 4 3 1 2 5

主張

• _{得 安定}

• _{必 停⽌}

• 後者 簡単 男性 同 ⼥性 2度 ー

い

• _{前者 証明}

• _{以下 動作 明}

(1) _{男性 順 ー}

(2) _{⼥性 相⼿ 変え 時 好 相⼿ え}

証明

• _背理法

– _得 ^M _キ

(m,w) _{あ 仮定}

– m M(m) w _{好 , w M(w)} m _好 – (1) m w _{振 い ．}

→ w m _{好 ⼈ 婚約 い ．}

– (2) ^, _{最終的 , w m 好 ⼈ 婚約} い ．

– _{キ 定義 反 ．}

安定 数

• Gale-Shapley _{，任意 例題}

必 ⼀ 安定 存在

• _{く い 数 存在 う}

？

– _{⼀ 安定 存在 い例 簡}

単 作

• _{定理： n 2 乗 ，} n

例題 ，少 く ^2n-1個 安定

持 存在

最適安定

• _{男性m あ 安定 結 う ⼥性 集合}

W(m)

• Gale-Shapley _{出⼒解 ，各男性m}

W(m) 中 最 選好順序 ⾼い⼥性 結婚 い

• _{男性最適 安定 いう}

• _{男⼥ 役割 ⼊ 替え ，⼥性最適 安定}

得

• _{男性最適 安定 ⼥性最悪 安定}

• _{研修医配属} ，病院側最適，研修医最悪

問題 拡張

• _{安定結婚問題} ⾊々 ⾮現実的 仮定 あ

– _{選好順序 全員 全順序 い}

– _{同順位 許 い い}

– _{絶対 結婚 く い相⼿＝ 空⽩}

許 い

• _{盛 込 場合 ？}

– 同順位 許 場合 → 同順位

– 空⽩ 許 場合 → 不完全

– 両⽅許 場合 → 同順位＆不完全

同順位 安定

• 安定性 定義 考え直 必要あ

– 弱安定性，強安定性，超安定性 – _以下，

• p : q₁ ≥ q_{2 ⼈ p 異性q2以上} q_{1 好}

• p : q₁ > q_{2 ⼈ p 異性q2} q_{1 好}

– _{キ 再定義}

• 1: m M(m) w 好 , w M(w) ^m 好

• 2: m M(m) w 好 , w M(w)以上 m 好

• 3： m M(m)以上 w 好 , w M(w)以上 m 好

• 1 _{キ い ＝ 弱安定性}

• 2 _{キ い ＝ 強安定性}

• 3 _{キ い ＝ 超安定性}

同順位 安定

• _{弱安定性 満}

– _{同順位 適当 順序付 与え}

– 選好順序下 Gale-Shapley 適⽤

弱安定性 満 得

• 強安定性，超安定性 満

– _{必 そ う 持 い例 存在}

– _{あ そ 判定 多項式時間 存在}

• _{強安定性 満 存在 い例}

1: a b c a: (1 2 3) 2: a b c b: 1 2 3

3: a b c c: 1 2 3

不完全 安定

• _{・・・ 場合，結婚 い相⼿ 存在}

数多く存在

– → Hall 結婚定理：G=(V,W,E) い

完全 存在⇔∀S⊆V: |S|≤|N(S)|

• _{キ 再定義}

– _{以下 満 キ}

I. m w M _{い い ，互い 名} 前 あ

II. m M _{独⾝ あ ，M(m)} w _好

不完全 安定

• 定理 (Rural Hospitals Theorem)

– M _{不完全 下 例題I 任意 安定}

．M い ⼈

I _{安定 い ，}

M _{独⾝ ⼈ 安定 独⾝}

あ

• _安定 Gale-Shapley

求

同順位＆不完全

• _{同順位 不完全 許 ・・・}

– _{同 例題 異 弱安定 存在}

う

1: a a: (1 2) 2: (a b) b: 2

– _例題 (1,a),(2,b) (2,a) _{弱 安定} 異

• _{⼤ 安定 ？}

– _⾒ , NP困難 [Iwama, et al. 1999]

最⼤ 安定 同順位＆

不完全

• _{計算困難性：}

– P_{困難 近似度 下界} ^≒

P= P

[ a a ]

• _{近似上界：}

– 近似 [ a a a ^] – 近似 [ a a a ^]

– [ a a a ]

• _{そ 後 下 い そう}

安定結婚 応⽤

• _{研修医配属}

– _{， 安定結婚 ー}

研修医配属 採⽤

– _⽇本 2004_{年度 採⽤}

• 募集定員10870⼈ 対 登録者8109⼈，

• 7756_{⼈ 配属先 得 率95.6%}

– 2004_年度

• 募集定員20908⼈ 登録者23965⼈ 者18806⼈

• _{様々 類似問題}

– _{安定 ー 問題}

– Residents/Hospitals _問題

経済学的

• _{安定 ・ 応}

⽤例

• _・

– _{良い 決 ⽅ 決 ⼿法 研究}

– _ー ョ ， ー 理論，社会選択理論 関連

– _{ー ・ ー} ^, _{・ キ}

ー・ ーソ

理論 基礎確⽴ ²⁰⁰⁷年 ー 経済学賞 受賞

そ 他

• _{様々 類似問題}

– _{安定 ー 問題}

– Residents/Hospitals _問題

• 最近 様々 新種 問題

• _{実世界 応⽤}

– _{研修医配属}

• ^{P a a a P a}

• Ca ^{Ca a a a}

• ^{PA P a A a}

• ^{P a a a P a}

ー ョ 理論⼊⾨

ー ョ ？

• _{ー ョ 例}

– Sotheby’s

– _{築地 市場}

– Internet Auction

(Yahoo _{ー ョ ，} 楽天 ー ョ )

– _公共⼊札

– _{他 ？}

1.

2.

ー ョ 結果

Types of Auctions

• We assume…

• Symmetrically,

Seller

item

Buyer #1

Buyer #2

Buyer

#m

Buyer

item Seller #1

Seller #2 item

bidders

Generalization …

• Multiple goods, and the buyers assign different values, …

• Combinations of goods, ….

200 _円 100 _円 300 _円

400 400 400

Bidder

#1

Bidder

#2

Bidder

#3

Models of Auction

• Each bidder has an intrinsic value for the item.

• b1 wants to buy the item if its price is at most 200 Kč. does not to buy otherwise.

Seller

item

b1

b2

b3

200 円

180円 250円

(true value)

Types of Auctions

1. Ascending bid auctions (English auctions) 2. Descending bid auctions (Dutch auctions) 3. First price sealed bid auctions

4. Second price sealed bid auctions (Vickrey auctions)

Non-Interactive Interactive

Why auction?

• Seller wants to sell the item at least x.

• (Max)buyer wants to buy the item at most y.

• Assume y>x. (Otherwise, they do not want to sell or buy)

• y-x : surplus

• If the seller and the buyers know their “values” each other…

→ Auction is not necessary.

lSeller can just sell the item at a price between x and y

The values are known by ….

Assumptions of Auctions

• The true values should be ^private.

• Information of the true values can affect the behavior of the seller or buyers.

• The true values are independent (?)

→ This assumption should be relaxed for more general settings.

Relationships between Auction Formats

• “Descending bid auctions” and

“1^st price sealed bid auctions”

• “Ascending bid auctions” and

“2^nd price sealed bid auctions”

These are almost equivalent.

These are almost equivalent.

“Descending bid auctions” and

“First price sealed bid auctions”

• Descending bid auctions

Seller item

b1

b2

b3

200 円 180円

250 円

310_円 290_円

270_円

250_円

Values

“Descending bid auctions” and

“1

price sealed bid auctions”

• 1^st price sealed bid auctions

Seller item

b1

b2

b3

200 円 180円

250円 Values

200円 180円

250円 250 _円

“Ascending bid auctions” and

“2

price sealed bid auctions”

• Ascending bid auctions

Seller item

b1

b2

b3

200 円 180 円

250 円

151 _円 181 _円

201 _円

Values

201 _円

“Ascending bid auctions” and

“2

price sealed bid auctions”

• 2^nd price sealed bid auctions

Seller item

b1

b2

b3

200 円 180 円

250 円 Values

200 円 180 円

250 円 200 _円

2

price sealed bid auctions

• Theoretically and Practically important

– Strategy-proofed mechanism – Used in eBay

– A generalized version is used in the pricing mechanism of keyword-based advertising