Lotteries
์กธ์ ์ ์ํด ๋ง์ง๋ง ํ๊ธฐ์ โ๋ฏธ์๊ฒฝ์ ํโ ์์ ์ ๋ฃ๊ฒ ๋์์ต๋๋ค. ๊ฒฝ์ ํ์๋ก ์์ ์ ์ฌ๋ฐ๊ฒ ๋ค์ด์ ๊ฒฝ์ ์ชฝ์ด๋ ๊ถํฉ์ด ์ข์ ์ค ์๊ณ ์ ์ฒญ ํ๋๋ฐ, ์ฌ๊ฑธโฆ ์ด ๊ณผ๋ชฉ์ ์ฌ์ค์ ์ํ๊ณผ ๊ณผ๋ชฉ ์ด์์ต๋๋ค.. ใ ใ ๊ทธ๋๋ ์ด์๋ถ์ ์ํ๊ณผ ๋ณต์์ ๊ณต์ ํ๊ณ ์์ผ๋, ์ด ์์ ๋ ํ๋ด์ ์ ๋ค์ด๋ด ์๋ค! ์ ์ฒด ํฌ์คํธ๋ โ๋ฏธ์๊ฒฝ์ ํโ ์นดํ ๊ณ ๋ฆฌ์์ ํ์ธํ์ค ์ ์์ต๋๋ค.
Lotteries
์ง๊ธ๊น์ง ์ดํด๋ณธ ์ ํธ(Preference), ํจ์ฉ ํจ์(Utility Functions), ์ ํ ํจ์(Choice Functions) ๋ชจ๋ ์ ํ๊ณผ ๊ฒฐ๊ณผ๊ฐ ๊ณ ์ ์ ์ผ๋ก ์ ํด์ง๋ ์ํฉ์ด์์ต๋๋ค.
๋ณต๊ถ(Lotteries)๋ ํ๋ฅ ์ ์ธ ๊ฒฐ๊ณผ๋ฅผ ํฌํจํ๋ ์ ํ์ง ์ ๋๋ค. ์ฌ๋์ด ์ ํ์ ํ๋ฉด, ๋ณด์์ด ํ๋ฅ ์ ์ผ๋ก ๊ฒฐ์ ๋ฉ๋๋ค.
์ด๋ค ๋ณด์์ ์งํฉ์ $Z$๋ผ๊ณ ํ ๋, Lottery $p$๋ $z \in Z$์ ํ๋ฅ $p(z)$๋ฅผ ํ ๋น ํฉ๋๋ค.
๋กํฐ๋ฆฌ์์ ํ๋ฅ ์ด 0๋ณด๋ค ํฐ ๋ณด์์ ์งํฉ์ support $\text{supp}(p)$๋ผ๊ณ ํฉ๋๋ค.
\[\text{supp}(p) = \left\{ z \in Z | p(x) > 0 \right\}\]- $L(Z)$
- set of all lotteries over $Z$
- $[z]$
- the lottery that yields the prize $z$ with probability 1
- Deterministic Lottery, Unity Lottery
๊ทธ๋ฆฌ๊ณ ๋ณต๊ถ โLotteryโ์ ๋ํ ํ๊ธฐ๋ ์๋์ ๊ฐ์ด ํ ์ ์์ต๋๋ค.
each $\alpha_k = p(z_k)$
\[p = \alpha_1 \cdot z_1 \oplus \cdots \oplus \alpha_n \cdot z_n\]Visualize set of lotteries
๋ง์ฝ $Z$๊ฐ ๋ ๊ฐ์ ์ํ $z_1, z_2$๋ก ๊ตฌ์ฑ ๋์ด ์๋ค๊ณ ํ๋ค๊ณ , ๊ฐ ์ํ์ ๋ํ ํ๋ฅ $p_1, p_2$๊ฐ ํ ๋น ๋๋ค๊ณ ํ์.
ํ๋ฅ ์ ํฉ์ ํญ์ 1์ด์ด์ผ ํ๊ธฐ ๋๋ฌธ์ $p_1 + p_2 = 1$์ ๋ง์กฑํ๊ณ , ์ด๋ ์์ ๊ทธ๋ฆผ์ฒ๋ผ ํ๋ฉด ์์ ํํํ ์ ์์ต๋๋ค.
๋ง์ฝ, $Z$๊ฐ 3๊ฐ์ ์ํ์ผ๋ก ๊ตฌ์ฑ ๋์ด ์์๋ค๋ฉด, ๋น์ทํ๊ฒ 3์ฐจ์์ ๊ณต๊ฐ ๋ค์ ๊ทธ๋ฆด ์ ์์ต๋๋ค.
Preference over lotteries
์ด๋ค ์ฌ๋ ์์ ์ฌ๋ฌ ์ข ๋ฅ์ ๋ณต๊ถ์ด ์์ต๋๋ค. ์ฌ๋๋ง๋ค ์ ํธํ๋ ๋ณต๊ถ์ด ๋ค๋ฅผ ํ ์ฃ . ์๋์์๋ ์ฌ๋๋ค์ ๋ณต๊ถ์ ๋ํ ์ ํธ์ ๋ํด ์๊ธฐํด๋ด ๋๋ค.
Pessimist
๋น๊ด์ฃผ์์์ ์์ ์ ๋๋ค. ์ด ์ฌ๋์ ๋ณต๊ถ์ ํ๊ฐํ ๋, ๊ทธ ์์์ ์ผ์ด๋ ์ ์๋ ๊ฒฐ๊ณผ๋ค ์ค โ๊ฐ์ฅ ๋์ ๊ฒฐ๊ณผโ๋ฅผ ๊ธฐ์ค์ผ๋ก ํ๋จ ํฉ๋๋ค.
๊ทธ ๋์ ๊ฒฐ๊ณผ๊ฐ ์๋ฌด๋ฆฌ ์์ ํ๋ฅ ์ ๊ฐ๋๋ผ๋, ๋น๊ด์ฃผ์์๋ ๊ฐ์ฅ ๋์ ๊ฒฐ๊ณผ๋ฅผ ๊ธฐ์ค์ผ๋ก ๊ทธ ๋ณต๊ถ์ ํ๊ฐ ํฉ๋๋ค.
๋น๊ด์ฃผ์์๋ ๊ฐ ๋ณต๊ถ์ ๊ฐ์ฅ ๋์ ๊ฒฐ๊ณผ $w(p)$๋ก ๋์ฒดํด์ ์๊ฐ ํฉ๋๋ค. ๊ทธ๋ฆฌ๊ณ , ๊ทธ ๋์ ๊ฒฐ๊ณผ ์ค์์ ๊ฐ์ฅ ํฐ ํจ์ฉ์ ๊ฐ์ง๋ ๋ณต๊ถ์ ์ ํธ ํฉ๋๋ค.
Good and Bad
์ด ์ฌ๋์ ๋ณต๊ถ์ ์ข์๊ฒ(good)๊ณผ ๋์๊ฒ(bad) ๋ ์ง๋จ์ผ๋ก ๋ถํ ํ์ฌ ์๊ฐ ํฉ๋๋ค.
๊ทธ๋ฆฌ๊ณ , ์ข์๊ฒ์ ํ๋ฅ ๋ชจ๋ ๋ํด $G(p)$๋ก ๋ก๋๋ค.
\[G(p) = \sum_{z\in\text{good}} p(z)\]์ด ์ฌ๋์ ๊ฐ ๋ณต๊ถ์์ ํ๋ฅ $G(p)$๋ฅผ ๊ตฌํ๊ณ , ์ด๊ฒ์ด ๋์ ๋ณต๊ถ์ ์ ํธ ํฉ๋๋ค.
์ด ์ฌ๋์ ์ข์ ๊ฒฐ๊ณผ์ ๊ฐ์น๋ ๋ฌด์ํ๊ณ , ์ข์ ๊ฒฐ๊ณผ๊ฐ ๋์ฌ ํ๋ฅ ๋ง์ ๊ธฐ์ค์ผ๋ก ์ ํ ํฉ๋๋ค.
Minimizing Options
์ด ์ฌ๋์ ์ผ์ด๋ ์ ์๋ ๊ฒฝ์ฐ์ ์๊ฐ ์์ ๊ฑธ ์ ํธ ํฉ๋๋ค. ์ด์ ๋ฅผ ๋ค์ด๋ณด๋, ๊ฐ๋ฅํ ๊ฒฝ์ฐ์ ์๊ฐ ์ ์์๋ก ๋๋นํ๊ธฐ ์ฝ๊ณ ์์ฌ ๋๋ค๊ณ ํ๋ค์. ์ฆ, ๋ถํ์ค์ฑ์ด ์ ์์๋ก ์ ํธํ๋ ์ฌ๋ ์ ๋๋ค.
\[p > q \iff \| \text{supp}(p) \| \ge \| \text{supp}(p) \|\]์ด๋ฐ ๊ฒฝ์ฐ๋ ์ด๋ค ์ํฉ์ ์ค๋นํ๋๊ฒ ์ค์ํ ์ํฉ, ์๋ฅผ ๋ค๋ฉด ์๋ฃ ์์ ์ด๋ ๊ตฐ์ฌ ์์ ์์ ์ด ์ ํธ๊ฐ ์ ์ฉํ ์ ์์ต๋๋ค.
Summary
์์์ ๋ณต๊ถ์ ๋ํ 3๊ฐ์ง์ ์ ํธ ๋ฐฉ์์ ์ดํด๋ณด์์ต๋๋คโฆ๋ง ๋ณต๊ถ์ ๋ํ ์ ํธ๋ ์ ๋ง ๋ค์ํ๊ฒ ์ ์ํ ์ ์์ต๋๋ค.
์์ผ๋ก๋ ์ด๋ฐ ๋ณต๊ถ ์ ํธ๋ค ์ค์์ โ์ข์ ์ฑ์งโ์ ๋ง์กฑํ๋ ํน๋ณํ ๋ณต๊ถ ์ ํธ๋ค๋ง ๊ณจ๋ผ์ ์ข๋ ์ดํด๋ณด๊ณ ์ ํฉ๋๋ค.
Properties
Continuity
์ํ๊ถ 100๋ง์, 70๋ง์, 40๋ง์์ด ์์ต๋๋ค. ๋ง์ฝ 100๋ง์์ด 0.5 ํ๋ฅ , 40๋ง์์ด 0.5 ํ๋ฅ ์ธ ๋ณต๊ถ์ด ์๋ค๋ฉด, ๊ทธ ์ฌ๋์ 70๋ง์๊ณผ ๊ทธ ๋ณต๊ถ์ ๋ฌด์ฐจ๋ณํ๊ฒ ์ ํธ ํ๋ค๊ณ ํฉ๋๋ค.
์์ ๊ฐ์ ์ํฉ์ด ๋ณต๊ถ์ ๋ํ ์ ํธ๊ฐ Continuity๋ฅผ ๋ง์กฑํ๋ค๊ณ ํฉ๋๋ค. ํ์์ ๊ฐ์ถฐ์ ์ ์ด๋ณด๋ฉด,
๋ณต๊ถ์ ๋ํ ๋ณด์ $Z$์ ๋ํด ์๋์ ๊ฐ์ด ์ฐ์์ ์ธ ์ ํธ๊ฐ ์์ต๋๋ค.
\[[a] \succ [b] \succ [c]\]๊ทธ๋ฆฌ๊ณ , $b$์ ๋๋ฑํ ๊ฐ์น๋ก ์ฌ๊ฒจ์ง๋ ์ด๋ค ๋ณต๊ถ์ ๋ง๋ค์ด๋ผ ์ ์๋ค๋ฉด,
\[[b] \sim \alpha \cdot a \oplus (1-\alpha) \cdot c\]โ์ ํธ ๊ด๊ณ๊ฐ ๋ณต๊ถ์ ๋ํด ์ฐ์์ฑ์ ๊ฐ๋๋คโ๊ณ ๋งํฉ๋๋ค.
๋น๊ด์ฃผ์์๊ฐ ๊ฐ๋ ์ ํธ๋ ์ฐ์์ฑ์ ๊ฐ์ง ๋ชปํฉ๋๋ค. ์๋ํ๋ฉด, ๋น๊ด์ฃผ์์๋ $a$์ $c$๋ฅผ ์์ ๋ณต๊ถ์ด ์์ผ๋ฉด ํญ์ ์ ์ข์ ์ ํ์ง $c$๋ฅผ ๊ธฐ์ค์ผ๋ก ํ๋จํ๊ธฐ ๋๋ฌธ์ ๋๋ค.
โGood and Badโ ์ ํธ๋ vacuously ์ฐ์์ด๋ผ๊ณ ํฉ๋๋ค. ๊ทธ ์ด์ ๋ ์ข์ ๊ฒฐ๊ณผ๊ฐ ๋์ฌ ํ๋ฅ ์ ์ดํฉ $G(p)$๋ง ๋ณด๊ณ ํ๋จํ๊ธฐ ๋๋ฌธ์ ๋ณด์์ ๋ํ ์กฐํฉ์ด ์๋ฏธ๊ฐ ์๊ธฐ ๋๋ฌธ์ ๋๋ค. ์ด ์ ํธ์์๋ ์ฐ์์ฑ์ ํ ์คํธํ ์ํฉ ์์ฒด๊ฐ ์๋ค๊ณ ํฉ๋๋ค.
โMinimizing Optionsโ๋ vacuously ์ฐ์์ด๋ผ๊ณ ํฉ๋๋ค. ์๋ํ๋ฉด, $[a] \succ [b] \succ [c]$์ ๊ฐ์ ๋ณด์ ๊ฐ์ ์ ํธ๊ฐ ์์ ์ ์๋์ง ์๊ธฐ ๋๋ฌธ์ ๋๋ค. ๊ทธ๋์ ์ ์ด์ ์ฐ์์ฑ์ ๋ํ ์ ์ฌ๊ฐ ์ฑ๋ฆฝํ์ง ์๊ณ , ์ฐ์์ฑ์ด vacuously ๋ง์กฑํ๋ค๊ณ ๋ด ๋๋ค.
* โvacuously ์ฐ์ํ๋คโ๋ ๊ฒ์ ๊ณตํํ๊ฒ ์ฐ์์ด๋ผ๊ณ ํํํ๋๋ฐ, ์กฐ๊ฑด์ ๋ง์กฑํด์ผ ํ ์ํฉ ์์ฒด๊ฐ ์์ ์กด์ฌํ์ง ์๊ธฐ ๋๋ฌธ์ ์กฐ๊ฑด์ ์๋์ผ๋ก ๋ง์กฑํ๋ค๋ ๊ฒ์ ๋งํฉ๋๋ค.
Compound Lottery
๋ณตํฉ ๋ณต๊ถ, ๋ณต๊ถ ์์ ๋ณต๊ถ. ๋ ๋จ๊ณ ์ด์์ ๋ฌด์์์ฑ์ด ์์ ๋๋ฅผ ๋ชจ๋ธ๋ง ํ๋ ๋ฐฉ๋ฒ ์ ๋๋ค.
๋ณด์์ ๋ํ ์งํฉ $Z$๊ฐ ์๊ณ , ๊ทธ ์์ ์ ์๋ ๋ณต๊ถ $p_1, โฆ, p_k$๊ฐ ์์ต๋๋ค. ์ด๋ค์ $L(Z)$์ ์์ ์ ๋๋ค.
๋ณตํฉ ๋ณต๊ถ์ ์๋์ ๊ฐ์ด ์ ์ ๋ฉ๋๋ค.
\[\alpha_1 p_1 \oplus \alpha_2 p_2 \oplus \cdots \oplus \alpha_k p_k\]์ด๊ฒ์ ๊ฐ ์ฌํ $z \in Z$์ ๋ํ ํ๋ฅ ์ ํ์ด์ฐ๋ฉด ์ด๋ ๊ฒ ๋ฉ๋๋ค.
\[\text{Prob}(z) = \sum_{i=1}^{k} \alpha_k \cdot p_k(z)\]Independence
๋ณต๊ถ์ ๋ถ๋ถ์ ๋ํ ์ผ๊ด์ฑ์ด ๋ณต๊ถ ์ ์ฒด์ ๋ํ ์ผ๊ด์ฑ๊ณผ ์ผ์นํ๋ค๋ ์ฑ์ง ์ ๋๋ค.
๋ณต๊ถ ๋ด์ ํน์ ํญ๋ชฉ์ ๋ค๋ฅธ ๊ฑธ๋ก ๋ฐ๊ฟจ์ ๋, ๋ณต๊ถ ์ ์ฒด์ ๋ํ ์ ํธ๋ ๊ทธ์ ๋ง๊ฒ ์ผ๊ด๋๊ฒ ๋ฐ๋์ด์ผ ํ๋ค๋ ์ฑ์ง ์ ๋๋ค.
์์์ผ๋ก ์ดํดํ๋๊ฒ ์ข๋ ํธํฉ๋๋ค.
๋ ๋ณต๊ถ ์ฌ์ด์ ์๋์ ๊ฐ์ ์ ํธ๊ฐ ์ฑ๋ฆฝ ํฉ๋๋ค.
\[[z_k] \succcurlyeq \beta a \oplus (1-\beta) b\]์ ํธ๊ฐ ๋ณต๊ถ์ ๋ํด ๋ ๋ฆฝ์ฑ์ ๊ฐ๋๋ค๋ฉด, ์๋์ ์ ํธ์ ๋ํ ๋ถ๋ฑ์๋ ์ฑ๋ฆฝ ํฉ๋๋ค.
\[\alpha_1 z_1 \oplus \cdots \oplus \alpha_k z_k \oplus \cdots \oplus a_n z_n \succcurlyeq \alpha_1 z_1 \oplus \cdots \oplus \alpha_k (\beta a \oplus (1-\beta) b) \oplus \cdots \oplus a_n z_n\]๊ทธ๋ฆฌ๊ณ ์ด ๋ช ์ ์ ๋ํ ์ญ๋ ์ฑ๋ฆฝ ํฉ๋๋ค.
Monotonicity
โ๋จ์กฐ์ฑโ์ ์ํ์ ์ ํธ ์ฒด๊ณ์ ๋ณต๊ถ์ ๋ํ ์ ํธ ์ฒด๊ณ๊ฐ ์ผ๊ด์ฑ ์๋๋ก ํ๋ ์ฑ์ง ์ ๋๋ค.
๋ ์ํ $a$, $b$๊ฐ ์์ ๋, ๋ ์ํ ์ฌ์ด์๋ $a \succ b$์ ์ ํธ๊ฐ ์กด์ฌํฉ๋๋ค. ๋ ์ํ์ผ๋ก ๋ง๋ค ์ ์๋ ๋ณต๊ถ ์งํฉ $L(Z)$์ ๋ํด์ ์ฌ๋๋ค์ ๋ณต๊ถ์ ๋ํ ์ ํธ๋ $a$ ์ํ์ด ๋น์ฒจ๋ ํ๋ฅ $\alpha$๊ฐ ๋์์๋ก ์ ํธ ๋ฉ๋๋ค.
ํฉ๋ฆฌ์ ์ธ ์ ํ์ ํ๊ธฐ ์ํด์ , ๋ ์ ํธ๋๋ ์ํ์ธ $a$๊ฐ ๋์ฌ ํ๋ฅ ์ด ๋์์ง ์๋ก ๊ทธ ๋ณต๊ถ์ ๋ ์ ํธํด์ผ ํฉ๋๋ค. ๋ง์ฝ ๊ทธ๊ฑธ ์ข์ํ์ง ์๋๋ค๋ฉด ๋นํฉ๋ฆฌ์ ์ธ ์ ํ์ ํ๋ค๋ ๊ฒ์ด์ฃ . ๋ณต๊ถ์ โ๋จ์กฐ์ฑโ์ ์ ํธ ์ฒด๊ณ๊ฐ ์ผ๊ด์ฑ ์๊ฒ ๊ตฌ์ฑ๋๋ ์ฆ๊ฑฐ๋ก ์ฌ์ฉ ํฉ๋๋ค.
Independence implies Monotonicity
Let $Z$ be a set of prizes.
Assume that $\succcurlyeq$, a preference relation over $L(Z)$, satisfies the independence property.
Let $a$ and $b$ be two prizes with $[a] \succ [b]$, and let $\alpha$ and $\beta$ be two probabilities. Then
\[\begin{gather*} \alpha \succ \beta \\ \iff \\ \alpha \cdot a \oplus (1 - \alpha) b \succ \beta \cdot a \oplus (1 - \beta) b \end{gather*}\]๋ณต๊ถ $p_{\alpha}$๋ฅผ
\[p_{\alpha} = \alpha \cdot a \oplus (1 - \alpha) \cdot b\]๋ผ๊ณ ํฉ์๋ค. ๋ณต๊ถ์ ๋ํ ์ ํธ ๊ด๊ณ๊ฐ ๋ ๋ฆฝ์ฑ์ ๋ง์กฑํ๋ฏ๋ก, ๋ณต๊ถ $p_{\alpha}$์์ $a$๋ฅผ $b$๋ก ๋์ฒดํ ๋ณต๊ถ์ ๋ํด์ ์๋์ ์ ํธ๊ฐ ์ฑ๋ฆฝ ํฉ๋๋ค.
\[p_{\alpha} \succ \alpha \cdot b \oplus (1 - \alpha) \cdot b\]์์ ์ ํธ ๊ด๊ณ๋ ์ฌ์ค ์๋์ ๊ฐ์ต๋๋ค.
\[p_{\alpha} \succ [b]\]์ด ์ ํธ ๊ด๊ณ์์ ์ ํธ์ ๋ ๋ฆฝ์ฑ์ ์ฌ์ฉํด ๋ค์ ์ด๋ฐ ์ ํธ ๊ด๊ณ๋ฅผ ์ป์ ์ ์์ต๋๋ค.
\[\begin{aligned} p_{\alpha} &= (\beta/\alpha) \cdot p_{\alpha} \oplus (1 - \beta/\alpha) \cdot p_{\alpha} \\ &\succ (\beta/\alpha) \cdot p_{\alpha} \oplus (1 - \beta/\alpha) \cdot b \end{aligned}\]์ด์ ์์ ์ ํธ์ ๋ํ ์์ ์ ์ ๋ฆฌํ๋ฉด,
\[\begin{aligned} p_{\alpha} &\succ (\beta/\alpha) \cdot p_{\alpha} \oplus (1 - \beta/\alpha) \cdot b \\ &= \beta \cdot a \oplus (1 - \beta) \cdot b \end{aligned}\]๋ฐ๋ผ์,
\[\alpha \cdot a \oplus (1 - \alpha) \cdot b \succ \beta \cdot a \oplus (1 - \beta) \cdot b\]$\blacksquare$
๋งบ์๋ง
์ด์ด์ง๋ ํฌ์คํธ์์๋ โ๊ธฐ๋ ํจ์ฉ(Expected Utility)โ์ ๋ํด ์ดํด๋ด ๋๋ค.
๊ฒฝ์ ํ์ ์ ํ์ ํ ๋, ๋ง์ ๊ฒ๋ค์ด ๋ถํ์ค์ฑ์ ๊ฐ์ง๊ณ ์์ต๋๋ค. ์ด๋ฒ์ ์ดํด๋ณธ ๋ณต๊ถ(Lotteries)๋ ์ด ๋ถํ์ค์ ๋ชจ๋ธ๋งํ ๊ฒ ์ ๋๋ค. ๊ธฐ๋ ํจ์ฉ์ ๋ถํ์คํจ์ด ์์ ๋, ์ฌ๋๋ค์ ์ ํ์ ๊ธฐ์ค์ด ๋ฉ๋๋ค. ๊ทธ๋ฆฌ๊ณ ์ฌ๋๋ค์ด ๊ธฐ๋ ํจ์ฉ์ ๋ฐ๋ผ ํ๋ํ๋ค๋ ๊ฒ์ ์ ์ ๋ก ๊ฒฝ์ ํ ์ด๋ก ์ด ๋ฐ์ ํ๊ฒ ๋ฉ๋๋ค.