最大最小化

最大最小化（粵拼：zeoi3 daai6 zeoi3 siu2 faa3；英文：minimax / minmax）係一種博弈論上講到嘅策略，喺人工智能等嘅領域嗰度都成日提及，可以用嚟教電腦做決策。廣義上嚟講，用最大最小化做決策，旨在想令到某啲「最大數值」有咁細得咁細——當中「最大數值」可以係指對手嘅最大報償，或者係自己嘅「最大後悔值」呀噉。

背景概念[編輯]

表 1：出紅咭定出藍咭好？
	阿 B 出紅	阿 B 出藍
阿 A 出紅	0, 0	0, 0
阿 A 出藍	-100, 100	100, -100

表 2：部老虎機咁著數，賭唔賭？
	贏	輸
賭	+10,000	-1
唔賭	0	0

首先，要理解最大最大化策略（maximax）——「諗吓每個選項嘅最高報償，再揀最高報償值最高嗰個」。想像依家有一場零和博弈，兩位博弈者，佢哋各自手上揸住一張藍色嘅咭同一張紅色嘅咭，而喺每場對局當中，佢哋要同時將一張咭擺上檯面，場遊戲係噉樣玩嘅：

如果 A 君出咗紅咭，無論 B 君出邊張咭都好，兩人打和。
如果 A 君出咗藍咭嘅話...
- 如果 B 君出嘅係紅咭，噉 B 君贏 100 文港紙。
- 如果 B 君出嘅係藍咭，噉 A 君贏 100 文港紙。

場博弈嘅報償矩陣係好似表 1 噉嘅樣。當中 (x, y) 結果表示「A 君贏 x 咁多錢而 B 君贏 y 咁多錢」。假如 A 君跟從最大最大化嘅法則行事，佢會永遠選擇出藍咭：對佢嚟講，出紅咭嘅最大可得係 0，而出藍咭嘅最大可得係 100 文港紙。問題係如果 A 君跟從噉嘅法則行動，B 君可以利用佢嘅單純思考方法—— B 君大可以選擇永遠出紅咭，噉佢就會永遠都贏錢。由此可見，最大最大化有個大缺點：決策者並冇考慮到對手會點樣反應；因此，呢種策略被指本質上係唔理性嘅，只有極天真（例如係細路）或者極肯博嘅決策者先會採取噉嘅策略^[1]^[2]。

用數學符號表述嘅話，maximax 決策法則如下^[3]：

{\underline {v_{i}}}=\max _{a_{i}}\max _{a_{-i}}{v_{i}(a_{i},a_{-i})}

，當中

$i$ 係做緊決策嗰位博弈者嘅「ID 冧把」。
$-i$ 表示 $i$ 以外嘅所有博弈者。
$a_{i}$ 係指由 $i$ 採取嘅行動。
$a_{-i}$ 係指由其他博弈者採取嘅行動。
$v_{i}$ 係 $i$ 嘅價值函數。

跟住，又思考吓最小最大化策略（maximin）——「諗吓每個選項嘅最低報償，再揀最低報償值最高嗰個」^[4]。想像依家阿明去賭場賭錢，佢搵到一部異常咁著數嘅老虎機：賭客贏咗可以賺到 10,000 文港紙咁多，而輸咗就只會損失 1 文（睇表 2 個矩陣），由阿明嘅角度睇^[1]——

「唔賭」嘅最低可得係 0；
「賭」嘅最低可得係 -1（損失 1 文）；

根據最小最大化，阿明理應選擇「唔賭」——但係一般認為，喺呢個情境下阿明係應該「去賭」至最著數。Maximin 嘅決策方法用數學符號表達如下：

{\underline {v_{i}}}=\max _{a_{i}}\min _{a_{-i}}{v_{i}(a_{i},a_{-i})}

相對於最大最大化嘅過度樂觀，最小最大化被認為係悲觀得滯，決策者彷彿假定咗自己永遠只會得到最壞結果，呢種思考法亦畀好多人認為係一種唔理想嘅決策方式^[1]。

後悔模型[編輯]

表 3：好唔好抌錢做研發？
	研發成功	研發失敗
抌錢	r-c	-c
唔抌	0	0

表 4：抌錢做研發嘅「後悔矩陣」
	研發成功	研發失敗
抌錢	0	c
唔抌	r-c	0

「後悔嘅最大最小化」呢種決策方式，被指係有別於太樂觀嘅 maximax 同埋太悲觀嘅 maximin。

Maximax：對每個選項，淨係睇佢嘅報償最高係幾多，揀對自己最有利嗰個。
Maximin：對每個選項，淨係睇佢嘅報償最低係幾多，揀對自己最有利嗰個。

後悔最大最小化原則^{[註 1]}源自匈牙利裔美國數學家馮紐曼嘅研究。依家想像一間企業，佢哋要決定「係咪要抌本做研發」，假設研發嘅成本係 c 咁多，假如研發成功，會為間企業帶嚟 r 咁多嘅利潤，而假如研發失敗，間企業唔會得到任何嘅利潤，只會損失抌咗落去做研發嗰筆錢，即係好似表 3 所示^[1]。

跟 maximax 嘅決策者：只要 r > c 就係唔係都要做研發。
跟 maximin 嘅決策者：係唔係都唔肯做研發。

後悔最大最小化原則就複雜少少：首先思考後悔嘅概念，後悔好似經濟學上講嘅機會成本，講緊「如果揀咗呢個選項，會錯過啲乜」—假如想研發嗰樣嘢係掂嘅，但係間企業冇郁手做研發，佢哋會錯失得到 r-c 嘅機會，而假如想研發嗰樣嘢係唔掂嘅，但係間企業郁手做研發，佢會錯失 c 咁多嘅成本。如果將呢套思考畫做一個「後悔矩陣」，會好似表 4 所表示嘅噉^[1]。

後悔最大最小化原則講緊嘅，就係決策者要盡可能減少（最小化）自己嘅「最高後悔值」^{[註 2]}：攞每一個選項嚟睇，決策者要睇下嗰個選項最高可以帶嚟幾高嘅後悔值，然後佢會揀「最高後悔值」最低嗰一個；喺做研發嗰個例子當中，如果 r 數值夠大（r - c > c），間企業會選擇郁手做研發，而如果 r 數值唔夠大（r - c < c），佢哋就唔會郁手做研發。用數學符號嚟表達嘅話，後悔最大最小化原則可以噉嚟表述^[5]^{:p 12}：

{\underline {v_{i}}}=\min _{a_{i}}\max _{a_{-i}}{R(a_{i},a_{-i})}

，

當中 $R$ 就係指後悔值。好似後悔 minimax 噉樣嘅決策方式，被認為係比較理性嘅一種做法。

可以睇睇[編輯]

註釋[編輯]

↑ 取自英文：The Minimax Regret Principle
↑ 後悔 minimax 集中於自身嘅「最高後悔值」，即係話响多人博弈當中，用呢種原則做決策嘅博弈者假定咗對手識做最好嘅決策。

引述[編輯]

↑ ^1.0 ^1.1 ^1.2 ^1.3 ^1.4 （英文）玩嘅策略，史丹福大學，當中有講到 minimax 嘅概念。
↑ Maximax and maximin. Economics Online.
↑ Maschler, Michael; Solan, Eilon; Zamir, Shmuel (2013). Game Theory. Cambridge University Press. pp. 176-180.
↑ Brody, H., & Thompson, J. R. (1981). The maximin strategy in modern obstetrics. The Journal of family practice, 12(6), 977-986，佢哋講咗："a maximin strategy: making the best of the worst possible outcome, regardless of the actual probability of that outcome occurring."
↑ Renou, L., & Schlag, K. H. (2010). Minimax regret and strategic uncertainty (PDF). Journal of Economic Theory, 145(1), 264-286.

再睇[編輯]

（英文） Mishra, A. K., & Tsionas, M. G. (2020). A minimax regret approach to decision making under uncertainty. Journal of Agricultural Economics, 71(3), 698-718.
（英文） Musman, S., & Turner, A. J. (2018). A game-oriented approach to minimizing cybersecurity risk. Safety and Security Studies, 27.
（英文）玩嘅策略，史丹福大學，當中有講到 minimax 嘅概念。
（英文）二人常和遊戲，不列顛百科全書
（英文）演算法解釋得清清楚楚 — minimax 同 alpha-beta 剪枝，YouTube

[5] 取自英文：The Minimax Regret Principle

[6] 後悔 minimax 集中於自身嘅「最高後悔值」，即係話响多人博弈當中，用呢種原則做決策嘅博弈者假定咗對手識做最好嘅決策。

[stanford-1] 1.0 ^1.1 ^1.2 ^1.3 ^1.4 （英文）玩嘅策略，史丹福大學，當中有講到 minimax 嘅概念。

[2] Maximax and maximin. Economics Online.

[3] Maschler, Michael; Solan, Eilon; Zamir, Shmuel (2013). Game Theory. Cambridge University Press. pp. 176-180.

[4] Brody, H., & Thompson, J. R. (1981). The maximin strategy in modern obstetrics. The Journal of family practice, 12(6), 977-986，佢哋講咗："a maximin strategy: making the best of the worst possible outcome, regardless of the actual probability of that outcome occurring."

[7] Renou, L., & Schlag, K. H. (2010). Minimax regret and strategic uncertainty (PDF). Journal of Economic Theory, 145(1), 264-286.

[1]

[2]

[3]

[4]

[註 1]

[註 2]

[5]