# Introduction to Decision Theory

<!--
preference:\prec, \preceq, \succ, \succeq
-->\usepackage{amsthm}
by Colin Cleveland

This is a note from chapter 1 of *An Introductory Course on Mathematical Game Theory* by Julio Gonzalez-Diaz et al. Basic knowledges from microeconomics, topology, such as definition of preference, and compact, are neglected here.

## Ordinal Utility

First of all, let's talk about the decisioin problem.

**[Def] Decision problem:** $(A,\preceq)$, when $A$ is set of alternative and $\preceq$ is weak preference. $u$ is utility function $u:A\to\mathbb R$. That is , is $a,b \in A, a \preceq b,$ then, $u(a) \leq u(b)$.

**[Pro] 1.2.1:** $A$ is countable. Then, $\exists u$ representing $\preceq$.
***(proof)*** We construct $u$ this way: $$h_{i,j} = \begin{cases}
1 & \text{if $a_i \succeq a_j$}\\
0 & \text{otherwise}\end{cases},
u(a_i) = \sum_{j=1}^\infty \frac{1}{2^j} h_{ij}$$

It is easy to prove it is a utility function representing $\preceq$. $\square$

**[Def] Order dense set:** $(A,\preceq)$ is a decision problem. $B \subset A$ is an order dense set if $\forall a_1 \preceq a_2 \in A$, $\exists b\in B$ s.t. $a_1 \preceq b \preceq a_2$.

**[Def] Gap:** $(A,\preceq)$ is a decision problem. $a_1 \prec a_2 \in A$. $(a_1,a_2)$ is a gap if $\forall b \in A$, either $b\preceq a_1$ or $a_2 \preceq b$. $A^*$: set of gap extremes.

**[Lem] 1.2.2:**
>(i) If $B$ is a countable dense order set in $A$, $A^*$ is countable.
(ii) If we have a utility function to represent $\preceq$, $A^*$ is countable.

***(proof)*** WBD.

**[Thm] 1.2.3:**
>$\preceq$ can be reprecented by $u$ iff $\exists B$ which is an order dense set in $A$.
>
***(proof)*** WBD.

## Linear Utility
Assume $x,y,z$ are alternatives of decision problem $(A,\preceq)$. $0\leq t \leq 1$. Now let's discuss the linear utility.

**[Def] Linear utility function $\bar u$:** $\bar u (tx+(1-t) y) = t\bar u(x)+(1-t)\bar u(y)$

**[Def] ($\succeq$) Independent:** $x \succeq y$, then $tx+(1-t)z \succeq ty+(1-t)z$.

**[Def] ($\succeq$) Continuous:** $x \succ y\succ z$, $\exists t$ s.t. $y \sim tx + (1-t)z$.

**[Pro] 1.3.1:** $\preceq$ independent. $s > t \in [0,1]$. $y \succ x \Rightarrow sy + (1-s) x \succ ty + (1-t)x$.
***(proof)*** WBD.

**[Thm] 1.3.3:**
>Assume $\preceq$ is independent and continuous. $\exists \bar u$ linearly reprensents $\preceq$ and $\bar u$ is unique up to positive affine transform. (If $\tilde u$ is linear utility function, $\tilde u = a \bar u + b$ for some $a,b$.)

***(proof)*** WBD

**[Def] set of lotteries over A:** $\triangle A:\{x\in[1,0]^A| a\in A, x(a) > 0, \sum_{a\in A} x(a) = 1\}$. Here $x(a)$ is the probability of getting $a$.
**[Def] Von Neumann and Morgenstern utility function:** This is utility function over $A$, and $u(x) = \sum_{a\in A} x(a)u(a)$.

**[Pro] 1.3.4:** We have a linear utility function for $(\triangle A,\preceq)$ iff there is a Von Neumann and Morgenstern utility function representing $\preceq$.
***(proof omitted)***

###### tags: `Algorithmic Game Theory`