Wednesday, 15 July 2020

A Generalised Hurwicz Criterion

Here's a PDF of this blogpost.

In yesterday's post, I discussed Leonid Hurwicz's Criterion of Realism. This is a decision rule for situations in which your evidence is so sparse and your uncertainty so great that you cannot assign probabilities to the possible states of the world. It requires you to pick a real number $0 \leq \alpha \leq 1$ and then assign to each option or act the weighted average of its worst-case utility and its best-case utility, where $\alpha$ is the weight for the former and $1-\alpha$ is the weight for the latter. That is, given an option defined on a set of possible worlds $W$, let$$H^\alpha(a) := \alpha \max_{w \in W} a(w) + (1-\alpha) \min_{w \in W} a(w)$$The Hurwicz Criterion says: Pick an option that maximises $H^\alpha$.

In that post, I also mentioned Hurwicz's own characterization of a class of preference orderings to which the orderings determined by $H^\alpha$ belong, namely, the class of all preference orderings that are indifferent between two options with the same minimum and maximum utilities. And I pointed out that there is something troubling about it: if you strengthen Hurwicz's Dominance axiom in a natural way, his axioms are no longer consistent. (As I mention in an update at the beginning of that blog, after posting it, Johan Gustafsson sent me a draft paper of his that makes this same point.) To see this, let $W = \{w_1, w_2, w_3\}$, and suppose $a$ and $a'$ are options defined on $W$ with
$$
\begin{array}{r|ccc}
& w_1 & w_2 & w_3\\
\hline
a & m & n & M \\
a' & m & n' & M
\end{array}
$$where $m < n < n' < M$. Then $H^\alpha(a) = H^\alpha(a')$, for any $0 \leq \alpha \leq 1$, but $a'$ weakly dominates $a$---that is, $a(w_i) \leq a'(w_i)$ for all $i = 1, 2, 3$ and $a(w_i) < a'(w_i)$ for some $i = 1, 2, 3$. That is, the Hurwicz Criterion is incompatible with a natural Dominance principle that says that if one option is always at least as good as another and sometimes better than it, it should be strictly preferred. And indeed all of the other rules in the class that Hurwicz characterised suffer from the same problem. Gustafsson uses this to mount an argument against one of Hurwicz's axioms, namely, the one that I called Coarse-Graining Invariance in the previous blogpost.

How to address this? A natural response is to note that the Hurwicz Criterion was too narrow in its view. While it was broader than Wald's Maximin, which was also in the air at the time, and its duel, Maximax, it still only considered best- and worst-case utilities. What of the rest? Of course, Hurwicz thought that his narrow focus was justified by his axioms. But if you are moved by the argument against those axioms that Gustafsson and I favour, that justification evaporates. Thus, I introduce what I'll call the Generalised Hurwicz Criterion as follows, where we are considering only options defined on a finite set of possible states of the world $W = \{w_1, \ldots, w_n\}$:

Generalized Hurwicz Criterion (GHC) Pick $0 \leq \alpha_1, \ldots, \alpha_n \leq 1$ with $\alpha_1 + \ldots + \alpha_n = 1$, and denote this sequence of weights $A$. If $a$ is defined on $W$ and$$a(w_{i_1}) \leq a(w_{i_2}) \leq \ldots \leq a(w_{i_n})$$then let$$H^A(a) = \alpha_1a(w_{i_1}) + \ldots + \alpha_na(w_{i_n})$$Pick an option that maximises $H^A$.

Note: it's important to reassure yourself that $H^A$ is well-defined in this statement. Now, the next thing is to offer a characterization of GHC. Recall, Hurwicz himself didn't actually characterise his Criterion, but rather a larger class of which it was a member. However, John Milnor, at that point just shortly out of his undergraduate degree and embarking on his doctoral work in knot theory, did provide a characterization in his paper 'Games against Nature'. We'll build on that result here to characterise GHC. First, two pieces of notation:
  • If $a$, $a'$ are options, then define $a + a'$ to be the option with $(a + a')(w) = a(w) + a'(w)$, for all $w$ in $W$.
  • If $a$ is an option and $m$ is a real number, then define $ma$ to be the option with $ma(w) = m \times a(w)$, for all $w$ in $W$.
(A1) Structure $\preceq$ is reflexive and transitive.

(A2) Weak Dominance
  1. If $a(w) \leq a'(w)$ for all $w$ in $W$, then $a \preceq a'$.
  2. If $a(w) < a'(w)$ for all $w$ in $W$, then $a \prec a'$.
(A3) Permutation Invariance For any set of worlds $W$ and any options $a, a'$ defined on $W$, if $\pi : W \cong W$ is a permutation of the worlds in $W$ and if $a'(w) = a(\pi(w))$ for all $w$ in $W$, then $a \sim a'$.

(A4) Continuity Suppose $a_1, a_2, \ldots$ is a sequence of options that converges on $a$ in the limit. Then, if $a_i \prec a'$ for all $i = 1, 2, \ldots$, then $a \preceq a'$.

(A5) Linearity If $m > 0$ and $a \sim a'$, then $ma \sim ma'$.

(A6) Summation If $a \sim b$ and $a' \sim b'$, then $a + a' \sim b + b'$.

Theorem Suppose (A1-6). Then there is some sequence $A$ of weights $0 \leq \alpha_1, \ldots, \alpha_n \leq 1$ such that $a \preceq a'$ iff $H^A(a) \leq H^A(a')$.

Before we continue to the proof, one point to note: as I noted in the previous post and Johan Gustafsson noted in his draft paper, if we strengthen Weak Dominance, Hurwicz's axioms are inconsistent. However, if we strengthen it here, the axioms remain consistent, and they characterise a slightly narrower version of the Generalized Hurwicz Criterion in which all weights must be non-zero.

Proof of Theorem. First, we determine the weights. We do this in $n$ steps. Here, we denote an option by the $n$-tuple of its utility values at the $n$ different worlds. Thus, $a = (a(w_1), \ldots, a(w_n))$.
  • If $\beta_n$ is the supremum of the set$$\{\alpha : (\alpha, \ldots, \alpha) \preceq (0, \ldots, 0, 1)\}$$then let $\alpha_n = \beta_n$;
  • If $\beta_{n-1}$ is the supremum of the set$$\{\alpha : (\alpha, \ldots, \alpha) \preceq (0, \ldots, 0, 1, 1)\}$$then let $\alpha_{n-1} = \beta_{n-1}- \alpha_n$;
  • If $\beta_{n-2}$ is the supremum of the set$$\{\alpha : (\alpha, \ldots, \alpha) \preceq (0, \ldots, 0, 1, 1, 1)\}$$then let $\alpha_{n-2} = \beta_{n-2} - \alpha_n - \alpha_{n-1}$;
  • and so on until...
  • If $\beta_1$ is the supremum of the set$$\{\alpha : (\alpha, \ldots, \alpha) \preceq (1, \ldots, 1, 1)\}$$then let $\alpha_1 = \beta_1 - \alpha_n - \alpha_{n-1} - \ldots - \alpha_2$.
Now, by Weak Dominance, for each $i = 1, \ldots, n$, $0 \leq \beta_i \leq 1$, since $(0, \ldots, 0) \preceq (0, \ldots, 1, \ldots, 1) \preceq (1, \ldots, 1)$. What's more, and again by Weak Dominance, $\beta_i \leq \beta_{i-1}$. Thus, $\alpha_i \geq 0$. What's more, $\beta_1 = 1$, so $\alpha_1 + \ldots + \alpha_n = 1$.

What's more, by Continuity:
\begin{eqnarray*}
(\alpha_n, \ldots, \alpha_n) & \sim & (0, 0, \ldots, 0, 1) \\
(\alpha_n + \alpha_{n-1}, \ldots, \alpha_n + \alpha_{n-1}) & \sim & (0, 0, \ldots, 1, 1) \\
\vdots & \vdots & \vdots \\
(\alpha_n + \ldots + \alpha_2, \ldots, \alpha_n+ \ldots + \alpha_2) & \sim & (0, 1, \ldots, 1, 1) \\
(\alpha_n + \ldots + \alpha_1, \ldots, \alpha_n+ \ldots + \alpha_1) & \sim & (1, 1, \ldots, 1, 1) \\
\end{eqnarray*}

Now, suppose $u_1 \leq \ldots \leq u_n$, and consider the option $(u_1, \ldots, u_n)$. Then, by Linearity:

$(\alpha_n (u_n-u_{n-1}), \ldots, \alpha_n(u_n-u_{n-1})) \sim (0, 0, \ldots, 0, u_n - u_{n-1})$

$((\alpha_n + \alpha_{n-1})(u_{n-1}-u_{n-2}), \ldots, (\alpha_n + \alpha_{n-1})(u_{n-1}-u_{n-2})) \sim$
$(0, 0, \ldots, u_{n-1}-u_{n-2}, u_{n-1}-u_{n-2})$

and so on, until...

$((\alpha_n + \ldots + \alpha_2)(u_2-u_1), \ldots, (\alpha_n+ \ldots + \alpha_2)(u_2-u_1)) \sim$
$(0, u_2-u_1, \ldots, u_2-u_1, u_2-u_1)$

$((\alpha_n + \ldots + \alpha_1)u_1, \ldots, (\alpha_n+ \ldots + \alpha_1)u_1) \sim (u_1, u_1, \ldots, u_1, u_1)$

And so, by Summation:$$(u_1, \ldots, u_n) \sim (\sum_i \alpha_i u_i, \ldots, \sum_i \alpha_i u_i)$$So, if $v_1 \leq \ldots \leq v_n$, and$$\sum_i \alpha_iv_i = \sum_i \alpha_iu_i$$then$$(v_1, \ldots, v_n) \sim (\sum_i \alpha_i v_i, \ldots, \sum_i \alpha_i v_i) \sim (\sum_i \alpha_i u_i, \ldots, \sum_i \alpha_i u_i) \sim (u_1, \ldots, u_n)$$as required. $\Box$

1 comment:

  1. hi, your post is very helpful for me. Finally, I found exactly what i want. If you need information regarding yahoo mail then you can visit our site yahoo mail gratis mail

    ReplyDelete