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

数理情報学I

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

⼩野廣隆

何 授業？

• 数理情報学専攻教員 ⾃⼰紹介的授業

• 9⼈ 教員 1回 いし2回 授業を担当

す オ ニ 形式 講義

• _{つま ，名⼤情報 数理情報学}

• _{普遍性 あ ，偏 あ}

数理情報学専攻

• 講座構成がH29.4.1現在き 数理情報基礎講座

教授 ：松原洋，吉信康夫，⼩野廣隆 准教授：佐藤潤也

講師 ：⽊原貴⾏

数理情報 論講座

教授 ：森本宏 H30.3.31退職予定 ，柳浦睦憲 准教授：⻄村治道, ン ェ ェー

助教 ：胡艶楠

研究 ー

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

• _数論

• _量⼦情報

• _{組合せ最適化・ 論}

ュー

⽉ ⽇：⼩野： 多様 最適化問題: 結婚 オー ョンま (1)

⽉ ⽇：⼩野： 多様 最適化問題: 結婚 オー ョンま (2)

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

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

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

⽉ ⽇： ェー ： Probability distributions

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

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

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

⽉ ⽇：吉信： Cantor 集合論

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

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

⽉ ⽇：松原： 無限集合 つい

成績評価

• _{ー ご ー or 試験}

– _{ー ：}

• 組合せ最適化・ 論

• 量⼦情報

– _：

• 数学基礎論・数理論理

• 数論

• _評価

– _{全 提出・出席 前提}

– _{上位 ー を元 成績をつけ}

– _{S 10%以下 ，上位 ー 差 出 い}

そ 他 ー 成績を⾒ 判断

⼩野 研究

• _{オペ ー ョン ・ ー ，}

• _{理論・最適化}

– _最適化

– _近似

– _{固定 ー}

– _{計算量・計算複雑度}

– _{計算困難・近似困難}

– _{的 ー 理論}

ー 分析

今回・次回 話

• _{⾒合い け 最適戦略}

最適停⽌問題

• _{失敗 い結婚 つい}

安定 ン

• _{オー ョン理論⼊⾨}

今⽇ 話：

⾒合い け 最適戦略

OMIAI (Formal Blind Date)

• Blind date

– a social appointment or date arranged, usually by a third person, between two people who have not met. (Random House Dictionary)

• OMIAI

– a Japanese style blind date whose success implies their marriage. (defined by me)

Difficulty of OMIAI

• If you once accept a person of OMIAI, need to get married with her/him.

• = abandon the possibility of marriage with a better person.

• But also she/he could be the best person for you.

• Anyway, you need to decide ^{accept or reject in} each OMIAI.

How can we do for series of OMIAIs?

Our OMIAI model and rule

• Assume that you are a perfect lady for everyone (= you are not rejected).

•

• Do OMIAI with ⁿ guys one by one.

• After each OMIAI, answer “yes” or “no”.

• If “yes”, you need to get married with him.

• If “no”, go to the next guy.

• If you answer “^{no” to n-1} guys, you need to get married with ⁿ-th guy.

Example _⾃粛

#5. #6.

#4.

#3.

#2.

#1.

No

No ^No

Yes

Setting

• All the guys are ^ranked from 1 to n. (no tie)

• But, we can know just the tentative rank of the guy in this OMIAI.

• For example, “I have met ^k=5 guys, and the k-th guy is ranked p=3 among the k guys.” …

• Decision: based on this p and k, decide your answer yes or no.

Assumption

• The order of OMIAIs are set at random.

• Simple (stupid) strategy:

Choose a number k (e.g., 3) from 1 to n in advance,

and just say no for #1,2,..,#k-1, and yes for #k.

– Probability of getting married with rank 1 guy = 1/n.

Possible Objectives

• Objective 1: Maximize the probability that you get married with rank 1 guy.

• Objective 2: Minimize the expected rank of the guy whom you get married with.

Best Strategy for Objective 1

• Case: n=20:

– For guys #1 … #7: (Patiently) say No!

– For guys after #7: Say ^Yes if he is the tentatively best.

Example

No No No No No No No

Best among 8? No

Best among 9? No

Best among 10? No

Best among 11? Yes!(Accept) 7

Best Strategy for Objective 1

• Case: n=20:

– For guys #1 … #7: (Patiently) say No!

– For guys after #7: Say Yes if he is the tentatively best.

• ^Theorem:

The probability that you can get married with rank 1 guy

Best Strategy for Objective 1

• For general n: (Strategy 1)

– For guys #1 … #n/e: (Patiently) say No!

– For guys after #n/e: Say Yes if he is the tentatively best.

• ^Theorem:

The probability that you can get married with rank 1 guy is at least 1/e = 36.78%.

How good Strategy 1 for Objective 2

• Theorem:

The expected rank by Strategy 1 is at least n/(2e).

• n= 20 à 3.67

• n= 50 à 9.19

• n= 100 à 18.4

Best Strategy for Objective 2

Strategy 2: (case n=20)

– For guys #1 … #5: (Patiently) say ^No!

– For guys #6…#10: Say ^Yes if he is the tentatively best. – For guys #11.#13: Say ^Yes if he is ranked 1,2 tentatively. – For guys #14.#15: Say ^Yes if he is ranked 1- 3 tentatively – For guys #16: Say ^Yes if he is ranked 1- 4 tentatively.

– For guys #17: Say ^Yes if he is ranked 1- 5 tentatively. – For guys #18: Say ^Yes if he is ranked 1- 7 tentatively. – For guys #19: Say ^Yes if he is ranked 1-10 tentatively. – For guys #20: Yes… No way…

• ^Theorem:

Best Strategy for Objective 2

• For general n (Strategy 2)

– p: the rank of #k among before

– p(n+1)/(k+1) ≤a(k), say Yes. Otherwise No. – � � = �(�)(� + 1)/(� + 1)

– � � − 1 = _.^{- ∑2(.)}_34- ^01-_.1- ^{� + .62 .}_. ^�(�)

• Theorem:

The expected rank is at most 4 even for n=100000.

Summary of OMIAI strategies

• Two objectives

– Maximize the probability that you get married with rank 1 guy

– Minimize the expected rank of the guy whom you get married with.

Objective 1 n=20 n=100 n=10000

Simple 5% 1% 0.01%

Strategy 1 38.42% 36.78% 36.78%

Objective 2 n=20 n=100 n=10000

Simple 9.5 49.5 4999.5

Applications or Variations

• Also known as “secretary problem”,

“sultan's dowry problem”, ….

• One of the Optimal Stopping Problems

• Many other practical examples.

• M. Gardner, “Scientific American” (1960)