
%%%%%%%%%%%%%%%%%%%%%%% file typeinst.tex %%%%%%%%%%%%%%%%%%%%%%%%%
%
% This is the LaTeX source for the instructions to authors using
% the LaTeX document class 'llncs.cls' for contributions to
% the Lecture Notes in Computer Sciences series.
% http://www.springer.com/lncs       Springer Heidelberg 2006/05/04
%
% It may be used as a template for your own input - copy it
% to a new file with a new name and use it as the basis
% for your article.
%
% NB: the document class 'llncs' has its own and detailed documentation, see
% ftp://ftp.springer.de/data/pubftp/pub/tex/latex/llncs/latex2e/llncsdoc.pdf
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\documentclass[runningheads,a4paper]{llncs}

\usepackage{amssymb}
\setcounter{tocdepth}{3}
\usepackage{graphicx}
\usepackage{amsmath}

\usepackage{url}
\usepackage{comment}

\urldef{\mailsa}\path|a.slinko@auckland.ac.nz|
\newcommand{\keywords}[1]{\par\addvspace\baselineskip
\noindent\keywordname\enspace\ignorespaces#1}

\def\er{{\sc ER}}
%
\def\R{\mathbb{R}}
\newcommand{\PP}{\mathcal{P}}
\def\Z{\mathbb{Z}}
\def\N{\mathbb{N}}
\def\ds{\displaystyle}
\def\oa#1{\overrightarrow{#1}}
\def\row#1#2{{#1}_1,\ldots ,{#1}_{#2}}
\def\brow#1#2{{\bf {#1}}_1,\ldots ,{\bf {#1}}_{#2}}
\def\rrow#1#2{{#1}_0,{#1}_1,\ldots ,{#1}_{#2}}
\def\urow#1#2{{#1}^1,\ldots ,{#1}^{#2}}
\def\irow#1#2{{#1}_1,\ldots ,{#1}_{#2},\ldots}
\def\ubrow#1#2#3{{\bf {#1}}^{#2},\ldots ,{\bf {#1}}^{#3}}
%
\def\lcomb#1#2#3{ {#1}_1{#2}_1+{#1}_2{#2}_2+\cdots +{#1}_{#3}{#2}_{#3}}
\def\blcomb#1#2#3{{#1}_1{\bf {#2}}_1+\cdots +{#1}_{#3}{\bf {#2}}_{#3}}
\def\twovec#1#2{\left(\begin{array}{c}{#1}\\{#2}\end{array}\right)}
\def\threevec#1#2#3{\left[\begin{array}{r}{#1}\\{#2}\\{#3}\end{array}\right]}
%
\def\mod#1{\ \hbox{\rm (mod $#1$)}}
\def\gcd#1#2{\hbox{gcd}\>(#1,#2)}
\def\lcm#1#2{\hbox{lcm}\>(#1,#2)}
\def\card#1{\hbox{card}\>(#1)}
\def\sr#1#2{\stackrel{#1}{#2}}
\def\cc{^{*}}
\def\b#1{\mathbf{#1}}
\def\p{\mathbf{p}}
\def\u{\mathbf{u}}
\def\ip#1#2{\mathbf{#1}\cdot\mathbf{#2}}

\newtheorem{axiom}{Axiom}
\newtheorem{clame}{Claim}

\begin{document}

\mainmatter  % start of an individual contribution

% first the title is needed
\title{Axioms for a Class of Algorithms of Sequential Decision Making}

% a short form should be given in case it is too long for the running head
\titlerunning{Axioms for a Class of Algorithms of Sequential Decision Making}

% the name(s) of the author(s) follow(s) next
%
% NB: Chinese authors should write their first names(s) in front of
% their surnames. This ensures that the names appear correctly in
% the running heads and the author index.
%
\author{Murali Agastya\inst{1}, 
Arkadii Slinko\inst{2}}

\institute{Economics Discipline, %H04  Merewether Building 
University of Sydney NSW 2006 Australia \newline
\email{m.agastya@econ.usyd.edu.au} \and
Department of Mathematics, The University of Auckland, Private Bag 92019, Auckland, New Zealand\newline 
\email{a.slinko@auckland.ac.nz}}
%
%
\authorrunning{Axioms for a Class of Algorithms of Sequential Decision Making}
% (feature abused for this document to repeat the title also on left hand pages)

% the affiliations are given next; don't give your e-mail address
% unless you accept that it will be published
%\institute{Department of Mathematics, The University of Auckland\\
%Private Bag 92019, Auckland, New Zealand\\
%\mailsa\\
%\mailsb\\
%\mailsc\\
%\url{http://www.math.auckland.ac.nz/~slinko}}

%
% NB: a more complex sample for affiliations and the mapping to the
% corresponding authors can be found in the file "llncs.dem"
% (search for the string "\mainmatter" where a contribution starts).
% "llncs.dem" accompanies the document class "llncs.cls".
%

\toctitle{Lecture Notes in Computer Science}
\tocauthor{Authors' Instructions}
\maketitle


\begin{abstract}
%  A Decision Maker or a software agent (DM) must choose at discrete moments from a finite
%  set of actions that result in random rewards.  The environment (which may include several other players) is  complex in that the DM finds it impossible to describe the states and
%  is thus prevented from application of standard Bayesian methods. 
We axiomatically characterise  a class of algorithms for making sequential decisions in situations of complete ignorance.  These algorithms assume that a decision maker (DM) (human or or a software agent) has exogenously defined utilities for prizes and she uses the empirical distribution of prizes to calculate the ``expected utility'' of each action maximising this expected utility at each stage of the decision making process. We show that this class of algorithms is defined by
three simple axioms that  highlight the independence of the given actions, the bounded
  rationality of the agent, and the principle of insufficient reason
  at margin.  %We show that, if rewards are
%  drawn by a stationary stochastic process, the observed behavior of
%  such a DM, in the long run, almost surely cannot be distinguished from anyone who is
%  fully cognizant of the environment.
\keywords{sequential decision making, ex-post rationality, fictitious play, multiset}
\end{abstract}


\section{Introduction}

Consider a Decision Maker (DM) who has to repeatedly choose from a
finite set of actions. Each action results in a random reward, also
drawn from a finite set. The environment is complex in the sense that
the DM is either unable to offer a complete description of the states
of the world or is unable to construct a meaningful prior probability
distribution. Naturally, the well established Bayesian methods of say
\cite{savage54:_found_statis} or \cite{anscombe63} would then be
inapplicable. 

%A history consists of the sequences of rewards, drawn from a finite set $\mathcal{R}$, that are
%obtained over time to each of the actions. We assume that the DM is using an algorithm that, given a history

Our approach is to postulate that the DM has a preference relation
defined directly over the set of actions which is updated over time in
response to the sequences of observed rewards.  Thus, if $\mathcal{A}$
denotes the set of all actions and $H$ the set of all histories, the DM is
completely described by the family $D:= ( \succeq_{h_t}
)_{h_t \in H}$, where $\succeq_{h_t} \subseteq \mathcal{A}
\times \mathcal{A}$ is a well defined preference relation on the
actions following a history $h_t$ at date $t$. A history consists of
the sequences of rewards, drawn from a finite set $\mathcal{R}$, that are
obtained over time to each of the actions.  Later we will impose axioms on $D$ of procedural rationality type.

There is a considerable literature in economics and psychology on a
variety of ``stimulus-response'' models of individual choice behavior.
In these models, the DM does not attempt to learn the environment,
instead she looks at the past experiences and takes her decisions on
the basis of her observations.  Most of this literature
prescribes some boundedly rational rule(s) for updating and the focus
is on analysis of implied adaptive dynamics.  These imputed rules of
updating vary widely.  They range from modifications of fictitious
play and reinforcement learning to imitation of peers etc.  See for
example \cite{borgers04:_exped_monot_learn_rules},
\cite{schlag98:_why_imitat_if_so_how},
\cite{gigerenzer02:_bound_ration} and the references therein.

Our approach outlined above is different. We do not consider any
particular updating rules but impose axioms on the updating
procedure. These axioms impose some structural restrictions and
postulate certain independence and we derive an ex-post utility
representation for such a DM.  This approach may be found in
\cite{easley99:_choic_belief} where they axiomatically characterised replicator dynamics which 
makes \cite{easley99:_choic_belief} the
closest relative of this paper. We note that the Case Based Decision Theory of Gilboa and Schmeidler \cite{G-S_01}, \cite{G-S_03} is not applicable due to the assumption of infinitude of cases and the Archimedean axiom that they impose.

Chapter 2 introduces the model, Chapter 3 defines the ex-post utility representation, Chapter 4 introduces the axioms, Chapter 5 formulates the main theorem and outlines its proof, and finally Section 6 fills all the gaps and completes the proof of the main theorem.

\section{The Model}
\label{sec:model}

A Decision Maker must choose from a finite set of $m$ actions $\mathcal{A} = \left\{ a_1, \ldots, a_m \right\}$, at each moment $t =
0, 1, 2, \ldots$. Every action results in
a reward, drawn from a finite set $\mathcal{R} = \{1,\ldots, n\}$.  The rewards are governed by a stochastic process unknown to the DM. Following her choice at date $t$, the
vector of realised rewards, ${\bf r}_t=(r_1^{(t)},\ldots, r_m^{(t)})$,
where $r_i^{(t)}$ is the reward to action $a_i$ at moment $t$, is
revealed to the DM. Thus the DM observes the rewards for {\em all} actions and not only for the one she has chosen. A \emph{history} at date $t$ is a sequence of vectors of rewards $h_t = \left( \mathbf{r}_0, \ldots, \mathbf{r}_{t -1} \right)$.

The sequential  decisions of the DM are guided by the following principle. Following any history $h_t$, the DM works out a preference relation\footnote{Throughout, by a \emph{preference} \emph{relation} on any set, we mean a binary relation that is a complete, transitive and reflexive
ordering of the elements.} $\succeq_{h_t} $ on the set of actions $\mathcal{A}$.  At
date $t$ she chooses one of the maximal actions with respect to
$\succeq_{h_t}$,  observes the set of outcomes $\mathbf{r}_t$ and calculates  a
new preference relation $\succeq_{h_{t + 1}}$ where $h_{t + 1} =
\left( h_t, \mathbf{r}_t \right)$. At the outset the DM is indifferent between all the actions so she chooses a random one. \par
  
Let $H_t$ denote the set of all  histories at date $t$ and $H = \bigcup_{t \geq 1} H_t$. Thus, the family of preference relations $D:=( \succeq_h )_{h \in H}$ completely
describes the DM.  Our objective is to discuss the behavior of this
learning agent through the imposition of certain axioms that encapsulate the DM's procedural rationality. For a DM  satisfying these axioms we will derive an ex-post utility representation  theorem that is based on the empirical distribution of rewards in any history.\par
%\medskip

Before proceeding any further with the analysis, it
is important to point out two salient features of the above
formulation of the DM.


First, as in \cite{easley99:_choic_belief}, a history describes the
rewards to all the actions in each period, including those that the DM
did not choose. This implicitly assumes that decisions are taken in a
social context where other people are taking other actions and the
rewards for each action are publicly announced. Examples of such
situations are numerous and include investing in a share market and
betting on horses.  Relaxing this assumption of learning in a social
context is a topic of future research.  %Some lines of attack will be
%discussed at the end in  Section~\ref{sec:conclusion}. 

Second, note that the description requires a preference on actions to
be specified after every conceivable history.  This is much in the
spirit of the theoretical developments in virtually all decision
theory.    The presumption
underlying such an abstraction is that any subset of these acts may be
presented to the DM and that a necessary aspect of a theory is that it
is applicable with sufficient generality.  Given the temporal nature
of the problem at hand this assumption may be quite natural.  For, all
conceivable histories may appear by assuming that the underlying
random process generates every ${\bf r} \in \mathcal{R}^m$ with a
positive probability.

  We make a non-triviality assumption on $D$ for the
  rest of this paper.  We assume that the DM is not indifferent 
    between all actions following all histories.
 %
  \begin{comment}
  We assume that there exists some one-period history $h_1 \in
  H_1$ and a pair of actions $a,b$ such that $a\succ_{h_1}b$.
  It is worth emphasizing that this does not entail any loss in
  generality.  Indeed, should this not be the case, the implication in
  conjunction with the listed  axioms is that the DM is indifferent
  between all actions following all histories making any 
  analysis redundant.\par

\end{comment}


  \section{Multisets \& Ex-Post  Utility Maximisation}

%\murali{Introducing all the multiset definitions very early on.}

Here we will introduce the rule (a class of algorithms) that we will eventually axiomatise. 
For this rule, the number of times different rewards accrue to given action
  during a history is important.  To progress further, we will need to
  introduce the idea of a { \em multiset}.  A multiset over an
  underlying set may contain several copies of any given element of
  the latter.  The number of copies of an element is called its {\em multiplicity}.
  Our interest is in multisets over $\mathcal{R}$. Therefore, multiset
  $\mu$ is identified with a vector $\mu = (\mu(1),\ldots,\mu(n)) \in
  \mathbb Z_+^n$, where $\mu (i)$ is the multiplicity of the $i$th
  prize and the {\em cardinality} of this multiset is
  $\sum\limits_{i=1}^n\mu(i)$.  Let $\PP_t[n]$ denote the subset of
  all such multisets of cardinality $t$ whereupon
\begin{equation}
\label{eq:7}
\PP[n]  =  \bigcup_{t=1}^{\infty}\PP_t[n]
\end{equation}
denotes the set of all non-empty multisets over $\mathcal{R}$.
Mostly, we will write ${\PP}_t$ instead of ${\PP}_t[n]$ when the
number of prizes is clear.  The \emph{union} of $\mu, \nu\in \PP$ is
defined as the multiset $\mu \cup \nu$ for which $(\mu \cup
\nu)(i)=\mu(i)+\nu(i)$  for any $i\in {\mathcal R}$.  Observe that
whenever $\mu \in \PP_t$ and $\nu \in \PP_{s}$, then $\mu\cup\nu
\in \PP_{t+s}$.

Given any history $h \in H_t$, let $\mu_i(a,h)$ denote the number of
times the reward $i$ has occured in the history of rewards $h(a)$ corresponding to
action $a$ and  $\mu(a,h)= ( \mu_1(a,h), \ldots, \mu_{n}(a,h))$.

\begin{comment}
\begin{example}
  Suppose that for $t=9$ and $n=5$ the history of rewards for action
  $a$ is
\[
h(a)=(1, 1, 3, 5, 2, 5, 2, 2, 2), \quad \text{ then } \quad 
\mu(a,h)=(2,4,1,0,2).
\]
An alternative self-explanatory notation for this multiset that is often used in mathematics is $\mu(a,h) = \{1^2,2^4,3,5^2\}$.
\end{example}

\end{comment}

For any two vectors $ \mathbf{x} =(\row x n)$, $\mathbf{y} =(\row y n)$
of  $\mathbb{R}^n$, we let $ x\cdot y$ denote their dot product, i.e.
$
 x\cdot y =  \sum_{i=1}^nx_iy_i.
$

Here comes the rule. A DM applying this rule must have exogenously defined utilities of the prizes. Let ${\bf u}=(\brow un)$ be the vector of her utilities, where $u_i$ is the utility of the $i$th prize. At any moment $t$ the DM calculates the total utility of the prices for each given action in the past and chooses the action which performed best in the past and for which the total utility of prizes is at least as high as for any other action. In other words she chooses any action belonging to $\text{argmax}_i( \mu(a_i,h)\cdot {\bf u})$.\par

The problem of the DM is that she does not know the probabilities. In the absence of any knowledge about the environment the most reasonable thing to do is to assume that the process of generating rewards is stationary and to replace the probabilities of the rewards with their empirical frequencies. Due to the assumed stationarity of the process she expects that these frequencies approximate probabilities well (at least in the limit), so in  a way the DM acts as an expected utility maximiser relative to 
the empirical distribution of rewards. This rule is very much in the spirit of the so-called fictitious play\footnote{
  \label{fn:1}Ficitious play was introduced by
  \cite{brown51:_iterat_solut_of_games_by_fictit_play}. See
  \cite{fudenberg98:_theor_of_learn_in_games} for variations of
  fictitious play. %See \cite{hopkins02:_two_compet_model_of_how} for a
%  nice comparison of fictitious play and replicator dynamics.
  }.
  % in the process of which a player assumes that her opponent's mixed strategy is  drawn from some stationary but unknown distribution over the set of pure strategies and tries to calculate this distribution by adjusting the weights for pure strategies on the basis of her observations. 

There is a good reason to allow the DM to use different vectors of utilities at different moments. This will allow the DM, at each moment, to refine her utilities from the previous period to reflect her preferences on larger multisets and longer histories. An obvious consistency condition must however be imposed:
we require that the vector of utilities the DM uses at time $t$ must be also suitable to evaluate actions in all previous moments.

\begin{definition}
  [Ex-Post Utility Representation]
\label{def:representation}
  A sequence $({\bf u}_t)_{t \geq 1}$ of vectors of
$  \mathbb{R}^n_{+}$ is said to be an {\em ex-post  utility representation} of $D=( \succeq_h )_{h \in H}$ if,   for all $t \geq 1$,
  \begin{equation}
  \label{utrep}
  a\succeq_{h}b \; \Leftrightarrow\; \mu(a,h)\cdot {\bf u}_{t} \geq
  \mu(b,h)\cdot {\bf u}_{t}\quad \forall \, a,b \in
  \mathcal{A},\;\;\forall h \in H_s ,
  \end{equation}
  for all $s\le t$.
  The representation is said to be \emph{global} if ${\bf u}_t\equiv {\bf u}$ for some ${\bf u} \in \mathbb{R}^n_{+}$.
  \end{definition}
  
  In what follows, we shall say that the DM is  {\em ex-post rational} if she admits an ex-post utility representation. \par\medskip
  
\begin{comment}
Given a tuple $(a,h)\in \mathcal{A}\times H_t$, we will refer to the 
lottery ${\bf p} = (p_1(a,h),\ldots,p_n(a,h))$ over $\mathcal R$, where
$p_i(a,h)=\mu_i(a,h)/t$ as the \emph{empirical distribution } of
$(a,h)$.
%
We note that the expression $\mu(a,h)\cdot {\bf u}_{t}$ in (\ref{utrep})
can be viewed as the total utility of rewards for the action $a$ at
time $t$. By choosing a maximal action with respect to $\succeq_{h}$
the DM with an ex-post utility representation is choosing an action
maximising this total utility.  We
note also that a comparison of $\mu(a,h)\cdot {\bf u}_t$ and
$\mu(b,h)\cdot {\bf u}_t$ is equivalent to a comparison of
$\p(a,h)\cdot {\bf u}_t$ and $\p(b,h)\cdot {\bf u}_t$.  Then the
maximisation of the utility of an action $a$ following a history
$h\in H_t$ can be viewed as the ex-post ``expected utility''
maximisation relative to the empirical distribution $\p(a,h)$.
\end{comment}

  We emphasise that the object that is of ultimate interest is the
  ranking of the actions following a history.  The utility
  representation of a DM involves assigning non-negative weights to the
  rewards.  However this assignment is not unique. A sequence $({\bf u}_t')_{t \geq 1}$ obtained
  by applying some positive affine transformations ${\bf u}_t'=
  \alpha_t{\bf u}_t+\beta_t $ (with $\alpha_t>0$) to a given utility representation $({\bf u}_t)_{t \geq 1}$ is also a
  utility representation. 

  Therefore, we should adopt a certain normalisation.  By $\Delta
  \subseteq \R^m$ we denote the $m-1$ dimensional unit simplex
  consisting of all non-negative vectors $ \mathbf{x} =(\row x n)$
  such that $x_1+\ldots+x_n=1$.   Due to the non-triviality assumption,
  for any ${\bf u}_t$, not all utilities are equal. Hence we may assume
  that at any ${\bf u}_t=(\row u n)$ in a representation, $\min\{u_i\}=0$.
  We may further normalise the coordinates to sum to one so that every
  $\mathbf{u}_t$ may be assumed to lie in one of the following subsets of the
  unit simplex:
\begin{equation}
\Delta^i = 
\{{\bf u} = (\row u n) \in \Delta \;|\; u_i=0\},
\end{equation}
which is one of the facets\footnote{Facet of a polytope is a face  of the maximal dimension.} of $\Delta$.

\section{Axioms }
\label{sec:axioms}

Next, we turn to the axioms that are necessary and sufficient for $D$
to admit an ex-post utility representation. 
%Given a history $h_t \in H_t$ and an action $a \in {\cal A}$,
% let $h_t ( a)$ be the sequence of rewards corresponding to this action.
The first axiom says that in comparing a pair of actions, the
information regarding the other actions is irrelevant.
Intuitively, this amounts to asserting that the agent believes that she is facing
an environment in which consequences of actions are statistically uncorrelated.

\begin{axiom}
  \label{axm:iia}
  Consider $h_t$, $h_t'$ and actions $a,b\in {\cal A}$ such that $h_t
  \left( a \right) = h_t' \left( a \right)$ and $h_t \left( b
  \right) = h_t' \left( b \right)$. Then $a \succeq_{h_t} b$ if  and only if $a \succeq_{h_t'} b$.
\end{axiom}

Although the agent has the entire history at her disposal, we
postulate that for any action, the algorithm only tracks the number of times
different rewards were realised. 
%Thus, if the empirical distribution
%of rewards corresponding to the two actions $a$ and $b$ is the
%same in a history $h_t$, then the DM is indifferent between them.
This means that the agent believes that she is facing 
an environment generated by a stationary stochastic process.

\begin{axiom}
  \label{axm:mulitset} 
  Consider a history $h_t$ at which for two actions $a$ and $b$ the multisets of prizes are the same, i.e. $\mu(a,h_t)=\mu(b,h_t)$. 
 Then ${a
    \sim_{h_t} b}$.
\end{axiom}

The next axiom describes how the DM learns to revise her preferences
in response to new information.


\begin{axiom}
  \label{axm:ignorance} \label{last-axiom} For any history $h_t$ and
  any $r \in \mathcal R$, if $h_{t+1}=(h_t, {\bf r}_t)$ where
  ${\bf r}_{t}=(r,\ldots,r)$, then  $\succeq_{h_{t+1}}=\,\succeq_{h_{t}}$. 
\end{axiom}


Due to Axiom~\ref{axm:iia}, it implies that  if at some  history $h_t$ the DM 
(weakly) prefers an action $a$ to $b$ and in the current period
both these actions yield the same reward, according to the next axiom,
the DM continues to prefer $a$ to $b$.
We view Axiom~\ref{axm:ignorance} as loosely capturing the ``principle
of insufficient reason at the margin''.


\begin{comment}

\medskip
We emphasise that the DM in this model does not try to predict the
future outcomes but evaluates the actions based on their past
performance.  Yet, even if DM were to engage such prediction,
intuitively, Axiom~1 would be consistent with a belief that the random
environment she faces is one in which the consequences of actions are
statistically uncorrelated.  Likewise Axiom~2 would be consistent with
a belief that the rewards are being generated by a stationary
stochastic process.
\medskip



It is worth pausing to compare the above axioms with those in
\er. In their work, much of the focus is on
the transition of preferences over actions from date $t$ to date
$t+1$, i.e. the more serious axiomatic treatment in their work
concerns assumptions in the spirit of Axiom~\ref{axm:ignorance} above.  It is therefore
not possible to find direct counterparts of Axiom~\ref{axm:iia} and Axiom~\ref{axm:mulitset}  in
their work.  Nonetheless, their Assumption 5.4 (PC-Pairwise
Comparisons), namely that the ``new measure of relative preference
between action $a$ and $b$ is independent of the payoffs to the
other actions'' is precisely in the spirit of Axiom~\ref{axm:iia}.  Likewise,
their Assumption 6.2 (E-Exchangeability) which ``requires that the
time order in which states are observed is unimportant'' corresponds
to Axiom~\ref{axm:mulitset} .


We do not assume that rewards are monetary but if one does so, Axiom 3
would then be weaker than their Monotonicity assumption on the
transition of preferences.  But it is worth reiterating that the key
difference is that here Axiom 3 allows for considerable \emph{path
  dependence} in the revision of preferences.  In other words, it is
entirely possible that there can be a pair of $t$ period histories
$h_t,h_t'$ such that $\succeq_{h_t}=\succeq_{h_t'}$ and yet when
followed by the same reward vector at $h_{t+1}=(h_t,\mathbf{r}_t)$ and
$h_{t+1}'=(h_t',\mathbf{r}_t)$ we have $\succeq_{h_{t+1}}\neq
\succeq_{h_{t+1}'}$.  In their setting, $\succeq_{h_t}=\succeq_{h_t'}$
implies $\succeq_{h_{t+1}}= \succeq_{h_{t+1}'}$ for all
$\mathbf{r}_t$.

\end{comment}


\section{The Main Theorem}
\label{sec:maintheorem}

In this section we will formulate and give an outline of the proof of the main theorem. %which fully characterises a DM satisfying axioms 1--3 as the one which has an ex-post utility representation. 
Recall that $ri(C)$ denotes the relative interior of a convex set $C$.

% Main theorem goes here %

\begin{theorem}[Representation Theorem]
  \label{thm:representation}Suppose $m\ge 3$. The following are equivalent:
  \begin{enumerate}
    \item $D=( \succeq_h )_{h \in H}$ satisfies Axioms 1--~\ref{last-axiom}.
    \item $D$ has an ex-post utility representation. %Moreover, there 
    There exists a unique sequence  of non-empty convex polytopes $(U_t)_{t \geq0}$
such that   $U_t \subseteq \Delta^i$ for some $i$ and
      \begin{enumerate}
      \item  $U_{t+1} \subseteq U_t$ for all $t \geq 1$.
      \item  $\bigcap_{t=1}^\infty U_t$ consists of a single vector.
      \item A sequence $({\bf u}_t)_{t \geq 1}$ of vectors of  $\mathbb{R}_n^{+}$ is a
        utility representation of $D$ if and only if ${\bf u}_t$ is a positive
        affine transformation of some ${\bf u}_t' \in ri(U_t)$.
%
        In particular, any sequence $({\bf u}_t)_{t \geq 1}$ such that
        ${\bf u}_{t }\in ri(U_t)$ is a utility representation of $D$. 
        \item If  $\bigcap_{t=1}^\infty U_t$ is in the interior of every $ U_t$, then the representation is global.
      \end{enumerate}
  \end{enumerate}
\end{theorem}
%\murali{ Remark 1 brought forward from the end of the proof of Theorem 1 to here.  Added Remark 2. Definitions of multisets etc. that appeared here have been taken to Section 2.1. }
\begin{remark}
    We note that despite an expected-utility-like calculation that is implicitly
    involved in Theorem~1, it is important to note that there
    is no connection with the expected utility hypothesis. Our DM is
    only ex-post rational. 
\end{remark}

\begin{comment}
\begin{remark}
  Below, we prove that $\mathcal D$, under Axioms 1-3 is essentially
  equivalent to a partial order over $\mathcal P$ that satisfies
  certain properties.  The rest of the proof of this theorem heavily
  relies on orders on multisets which is taken up in Section~3.  The
  proof is completed by appealing to Lemma 1 that appears toward the
  end of  Section~3.
\end{remark}
\end{comment}

%=====================


\begin{proof}%[Proof of Theorem~\ref{thm:representation}]
\label{sec:sketch-proof-theorem}
It is easy to show that any DM with an ex-post utility representation satisfies the axioms. 
%
Let us show the non-trivial part of the theorem, which is, $1 \Rightarrow 2$.  We begin by
defining, for each $t \geq 1$, a binary relation
$\succeq^{\ast}_{t}$ on $\PP_t=\PP_t[n]$ as follows: for any
${\mu,\nu \in \PP_t}$,

\begin{eqnarray}
  \mu\succeq^{\ast}_{t} \nu & \Longleftrightarrow & \text{ there exists $a,b
    \in \mathcal{A}$ and a history $h_t \in H_t $ }\nonumber\\
  & & \text{such that $\mu=\mu(a,h_t)$ and $\nu=\mu(b,h_t)$ and} \label{eq:preference} \\
    & &  a \succeq_{h_t}b \nonumber
\end{eqnarray}
%
Analogously we define also a strict version $\succ^{\ast}_{t}$ of $\succeq^{\ast}_{t}$.
The latter needs to be proved to be antisymmetric.
For, for a certain pair of multisets $\mu,\nu \in \PP_t$, different choices of histories and actions can result  in both $\mu\succeq\cc_t\nu$ and $\nu\succ_t\cc \mu$ at once.  However, we claim
that:

\begin{clame}
  \label{claim:1}
For  any $a,b,c,d \in \mathcal{A}$ and any two
  histories $h_t,h_{t}' \in H_t $ such that
  $\mu(a,h_{t})=\mu(c,h'_t)$ and
  $\mu(b,h_t)=\mu(d,h_t')$, 
\[a\succeq_{h_t}b\; \Longleftrightarrow \; c \succeq_{h_{t'}}d.\] 
\end{clame}

The above claim ensures that $\succ_t\cc$ is antisymmetric since $\succ_h$ is antisymmetric. It is now also clear that the sequence  $\succeq\cc=(\succeq\cc_t)_{t \geq1}$ inherits the non-triviality assumption in the sense that for some $t$ the relation $\succeq\cc_t$ is not a complete indifference.
Next we claim that
\begin{clame}
  \label{claim:2}
  $\succeq_t\cc$ is a preference ordering on  $\PP_t$.
\end{clame}

Both of the above claims only rely on Axiom~\ref{axm:iia} and
Axiom~\ref{axm:mulitset}.  The proofs of Claim~\ref{claim:1} and Claim~\ref{claim:2}  are 
straightforward but nevertheless relegated to the Appendix.
%\par\medskip
By a repeated application of
Axiom~\ref{axm:ignorance}, we see at once that 

\begin{clame}
  \label{claim:consistent}
  The sequence $\succeq\cc=(\succeq\cc_t)_{t \geq1}$ satisfies the following property: for any $\mu, \nu  \in \mathcal{P}_t$ and any $\xi \in \mathcal{P}_{s}$,
\begin{equation}
\label{cons_of_succeqcc}
    \mu \succeq\cc_t \nu \Longleftrightarrow  \mu \cup \xi \, \succeq\cc_{t + s}
    \, \nu \cup \xi
\end{equation}
  for all $t,s \in\mathbb{Z}_+$. 
\end{clame}

The remainder of the proof will follow from Theorem~\ref{prop:consistent-multisets} proved in the next section and further considerations.
\end{proof}

  The requirement in Theorem 1 that there are at least three actions
  for the agent to choose from cannot be dropped.  To see this we have
  the following counter-example with $m=2$.
\begin{example}
  Pick any utility vector
  ${\bf u} = (\row u n)$ for the rewards and define $ D$ as
  follows:
\smallskip\par
  Following a history $h_t\in H_t$,
  \begin{enumerate}
  \item If $\mu(a_i,h_t)\cdot {\bf u} > \mu (a_j,h_t)\cdot {\bf u}$, the DM
    strictly prefers $a_i$ to $a_{j}$, where $i\neq j$ and $i,j=1,2$.
  \item If $\mu(a_1,h_t)\cdot {\bf u} = \mu (a_2,h_t)\cdot {\bf u}$, then
    \begin{enumerate}
    \item If the corresponding multisets of rewards are the same,
      i.e. $\mu(a_1,h_t)=\mu(a_2,h_t)$, then the actions are indifferent.
    \item Otherwise  $a_1$ is strictly preferred. 
    \end{enumerate}
  \end{enumerate}\smallskip
  It may be readily verified that $\mathcal D$ described above
  satisfies Axioms~1-3 but does not admit  an ex-post utility representation.
\end{example}

\section{Orders on Multisets and Their Utility Representation}

%\subsection{Consistent Orders on Multisets}
%\label{sec:mult-cons-orders}

This section completes the proof of the main theorem.\par\medskip

As we know from Section~\ref{sec:model}, multisets of cardinality $t$ are important for a DM as they are closely related to histories at date $t$. The DM has to be able to compare them for all $t$. At the same time in the context of this paper it does not make much sense to compare multisets of cardinalities of different sizes (it would if we had missing observations). Due to this, our main object in this subsection is a family of orders   ${(\succeq_{t} )_{t \geq 1}}$, where $\succeq_{t}$ is an order on $\PP_t$. In this case we denote by $\succeq$ the partial (but reflexive and transitive) binary relation on $\PP$ whereby for any
$\mu,\nu \in \PP$, where $\mu \succeq\nu$ if both $\mu$ and $\nu$ are
of the same cardinality, say $t$, and $\mu\succeq_t \nu$ and
$\mu\succeq \nu$ is undefined otherwise.%\footnote{Mathematically speaking $\PP$ here is considered as an object {\em graded} by positive integers. In a graded object all operations and relations are defined on its homogeneous components only.} To make the orders  $\succeq_{t}$, for various $t$, related to each other we need to impose some kind of consistency condition on them.

To complete the proof of the main theorem we must study orders on $\PP$ with the property (\ref{cons_of_succeqcc}). Due to their importance we will give them a special name.

\begin{definition}
  [Consistency]
  \label{defn:consistency}
An order  $\succeq={(\succeq_{t} )_{t \geq 1}}$ on $\PP$ is said to be {\em consistent} if it satisfies the condition (\ref{cons_of_succeqcc}) from Claim~3, that is, for any $\mu, \nu  \in \mathcal{P}_t$ and any $\xi \in \mathcal{P}_{s}$,
\begin{equation}
\label{cons_of_succeq}
    \mu \succeq_t \nu \Longleftrightarrow  \mu \cup \xi \, \succeq_{t + s}
    \, \nu \cup \xi.
\end{equation}
\end{definition}
\noindent We note that, due to the twosidedness of the arrow in (\ref{cons_of_succeq}), we have also 
\begin{equation}
\label{cons_of_succ}
    \mu \succ_t \nu \Longleftrightarrow  \mu \cup \xi \, \succ_{t + s}
    \, \nu \cup \xi.
\end{equation}

One consistent linear order that immediately comes to our mind is the
lexicographic order which is an extension of a linear order on
$\mathcal R$. But, of course, this is not the only consistent order. Now we will define a large class of consistent orders on $\PP$ to which the lexicographic order belongs.
\begin{definition}[Local Representability]
  \label{defn:representability-on-multisets}
An order  $\succeq:=(\succeq_t)_{t \geq 1} $ on $\mathcal{P}$ is  locally
  representable  if, for every $t\ge 1$, there
  exist $\mathbf{u}_t \in \mathbb{R}^n$ such that
  \begin{eqnarray}
        \label{VgeqV}
    \mu \succeq_s \nu & \Longleftrightarrow & \mu\cdot \mathbf{u}_t \; \geq \; \nu\cdot \mathbf{u}_t  \qquad \forall \, \mu, \nu \in \PP_s, \quad \forall s \leq t.
  \end{eqnarray}
    A sequence $({\bf u}_t)_{t \geq 1}$ is said to locally represent $\succeq$
  if~(\ref{VgeqV}) holds.
%  
  The order $\succeq$ is said to be globally representable if there exist
  $\mathbf{u} \in \mathbb{R}^n$ such that (\ref{VgeqV}) is satisfied
  for  $\mathbf{u}_t=\mathbf{u}$ for all~$t$.
\end{definition}

The lexicographic order is locally representable but not globally. 
%It is easy to check that any locally representable linear order on $\PP$
%is consistent.   More interestingly, we have the following:

%\newtheorem{proposition}{Proposition}
\begin{theorem}
  \label{prop:consistent-multisets}
An order $\succeq= (\succeq_t)_{t \geq 1}$ on  $\PP$ is consistent if and only if it is locally
  representable.
\end{theorem}

\begin{proof}
If the order is locally representable it is straightforward to verify that it is consistent. Suppose the sequence of vectors $({\bf u}_t)_{t\ge 1}$ represents $\succeq=(\succeq_t)_{t \geq 1 }$. Let $\mu,\nu\in \PP_s$ with $\mu\succeq_s\nu$ and $\eta \in \PP_t$. 
 Then $\mu\cdot {\bf u}_{s+t} \ge \nu\cdot {\bf u}_{s+t}$ since ${\bf u}_{s+t}$ can be used to compare multisets of cardinality $t$ as $t<t+s$. But now 
 \[
(\mu +\eta )\cdot {\bf u}_{s+t} - (\nu +\eta )\cdot {\bf u}_{s+t}=\mu\cdot {\bf u}_{s+t} - \nu\cdot {\bf u}_{s+t}\ge 0
\]
which means $\mu +\eta \succeq_{s+t} \nu +\eta$. 
   
   
To see the  converse, let $\succeq=(\succeq_t)_{t \geq 1 }$ be consistent. An immediate implication of consistency is that for any $\mu_1,\nu_1\in  \PP_t$ and $\mu_2,\nu_2\in \PP_{s}$,

\begin{eqnarray}
\label{eq:3}
\mu_1 \succeq_t \nu_1\ \text{and}\ \mu_2 \succeq _{s} \nu_2 & \Longrightarrow \; 
\mu_1 \cup \mu_2\; \succeq _{t+s}\; \nu_1 \cup \nu_2,
\end{eqnarray}
where we have 
$
\mu_1 \cup \mu_2\; \succ _{t+s}\; \nu_1 \cup \nu_2
$
if and only if either $\mu_1 \succ _t \nu_1$ or $\mu_2 \succ _{s} \nu_2$.
Indeed by consistency, we have 
\[
\mu_1 \cup \mu_2\; \succeq _{t+s}\; \nu_1 \cup \mu_2\; \succeq _{t+s}\; \nu_1 \cup \nu_2.
\]

Now suppose, by way of contradiction, that local representability fails at some $t$ which means that ${\bf u}_t$ is the first vector that cannot be found.  
Note that there are $N={{n+t-1} \choose t}$ multisets of cardinality $t$ in total.
 Let us enumerate all the multisets in
$\mathcal{P}_t$  so that
\begin{equation}
\label{eq:5}
  \mu_{1} \succeq_t \mu_2\succeq_t \cdots\succeq_t\mu_{N-1} \succeq_t\mu_{N}.
\end{equation}

Some of these relations may be equivalencies, the others will be strict inequalities. Let $I=\{i\mid   \mu_{i} \sim_t \mu_{i+1}\}$ and $J=\{j\mid   \mu_{j} \succ_t \mu_{j+1}\}$. 
If $\succeq_t$ is complete indifference, i.e. all inequalities in  (\ref{eq:5}) are equalities,
then it is representable and can be obtained by assigning 1 to all of the utilities. 
Hence at least one ranking in (\ref{eq:5}) is  strict or $J\ne\emptyset $. 

The non-representability of $\succeq_t$ is equivalent to the assertion
that the system of  linear equalities $(\mu_i-\mu_{i+1})\cdot {\bf x}=0$, $i\in I$, and linear inequalities
$(\mu_j-\mu_{j+1})\cdot {\bf x}>0$, $j\in J$,
has no semi-positive solution. \par
%\vspace{1cm}

A standard linear-algebraic argument tells us that inconsistency of
the system above is equivalent to the existence of a nontrivial linear
combination
\begin{equation}
\label{c_iv_i=0}
\sum_{i=1}^{N-1}c_i(\mu_i-\mu_{i+1})=0
\end{equation}
 with non-negative coefficients $c_j$ for $j\in J$ of which at least one is non-zero (see, for example, Theorem~2.9 of \cite{Gale}, page 48). Coefficients $c_i$, for $i\in I$,  can be replaced by their negatives since the equation $(\mu_i-\mu_{i+1})\cdot {\bf x}=0$ can be replaced with $(\mu_{i+1}-\mu_{i})\cdot {\bf x}=0$. Thus we may assume that all coefficients of (\ref{c_iv_i=0}) are non-negative with at least one positive coefficient $c_j$ for $j\in J$. Since the coefficients of vectors $\mu_i-\mu_{i+1}$ are integers, we may choose $\row cn$ to be non-negative rational numbers and ultimately non-negative integers.
\par

The equation (\ref{c_iv_i=0}) can be rewritten as 
\begin{equation}
\label{sum=sum}
\sum_{i=1}^{N-1}c_i\mu_i = \sum_{i=1}^{N-1}c_i \mu_{i+1},
\end{equation}
which can be rewritten as the equality of two unions of multisets:


\begin{equation}
\label{union}
\bigcup_{i=1}^{N-1}\underbrace{\mu_i\cup \ldots\cup
\mu_i}_{c_i}=\bigcup_{i=1}^{N-1}\underbrace{\mu_{i+1}\cup \ldots\cup
\mu_{i+1}}_{c_i}
\end{equation}
which contradicts to $c_j>0$, $\mu_j\succ \mu_{j+1}$ and (\ref{eq:3}). This
contradiction proves the theorem.
\end{proof}



The above equivalence lies at the heart of proof
Theorem~\ref{thm:representation}. Indeed, it already implies, via
Claims 1-3 given in the previous section, that Axioms 1-3 imply the existence of an
ex-post representation for $\mathcal D$.  What remains to be shown is
the characterization of all such representations.  %We omit this here. 

%\begin{comment}

Consistent orders  on $\PP_t$ can be represented geometrically \cite{SS}. 
%
\begin{comment}
We recall a few basic facts about hyperplane arrangements in
$\mathbb{R}^n$% (see {\cite{OT}} for more information about them).  
A \emph{hyperplane arrangement} $A$ is any finite set of hyperplanes.
Given a hyperplane arrangment $A$ and a hyperplane $J$, both 
in $\mathbb{R}^n$, the  set
\[ 
A^J =\{L \cap J \mid L \in A \} 
\]
is called the \emph{induced arrangement of hyperplanes} in $J$. 


A \emph{region} of an arrangement $A$ is a
connected component of the complement $U$ of the union  of the hyperplanes of
$A$, i.e., of the set
\[ U = \mathbb{R}^n \setminus \bigcup_{L \in A} L. \]
Any region of an arrangement is an open set. 
\end{comment}
%
Every point $\mathbf{u} = ( u_1, \ldots, u_n ) \in \mathbb R^{n}$
defines an order $\succeq_{\bf{u}}$ on $\mathcal{P}_t$, which obtains
when we allocate utilities $\row un$ to prizes $i = 1, 2, \ldots, n$,
that is
\begin{equation}
\label{utilities_give_order}
\mu\succeq_{\bf u} \nu \Longleftrightarrow
\sum_{i = 1}^n \mu (i) u_i \ge  \sum_{i = 1}^n \nu (i) u_i. 
\end{equation}
Any order on $\mathcal P_{t}$ that can be expressed as $\succeq_{\bf u}$ for some
$\b u \in \mathbb R^{n}$ is said to be {\em representable}.  We will now 
argue that the  representable linear orders on $\mathcal P_t$
are in one-to-one correspondence with the regions of the following hyperplane arrangment. 

For any pair of multisets
$\mu,\nu\in \PP_t[n]$, we define the hyperplane 
\[
L(\mu, \nu) \; = \; \left\{ \b x \in \mathbb R^{n}\, \mid \, \sum_{i = 1}^n \mu (i) x_i -  \sum_{i = 1}^n \nu (i) x_i=0 \right\}
\]
and consider the hyperplane arrangement
\begin{equation}
A(t,n) = \big\{ L(\mu,\nu) \; \mid \; \mu,\nu \in \mathcal P_t[n]\big\}.
\end{equation}
The set of representable linear orders on $\PP_t[n]$ is in one-to-one correspondence with the regions of $A=A(t,n)$. In fact,  then the linear
orders $\succeq_{\bf{u}}$ and $\succeq_{\bf{v}}$ on $\mathcal{P}_t$
will coincide if and only if $\bf{u}$ and $\bf{v}$ are in the same
region of the hyperplane arrangement $A$.  This immediately follows
from the fact that the order $\mu \succ_{\bf x} \nu$ changes to $\mu
\prec_{\bf x} \nu$ (or the other way around) when ${\bf x}$ crosses
the hyperplane $L(\mu, \nu)$. The closure of every such region is a convex polytope.% \par\medskip


\begin{example}
The 12 regions on the figure below represent all 12 representable
   orders on $\mathcal{P}_2[3]$.
  \begin{center}
   \includegraphics[height=6cm]{pic1.pdf}
  \end{center}
 with the shaded region corresponding to the lexicographic order
 $ 1^2 \succ 12 \succ 13 \succ 2^2 \succ 23 \succ 3^2 . $
\end{example}

Let us note that in (\ref{utilities_give_order}) we can divide all utilities  by $u_1+\ldots+u_n$ and the inequality will still hold. Hence we could from the very beginning consider that all vectors of utilities are in the hyperplane $J$ given by $x_1+\ldots+x_n=1$ and even in the simplex $\Delta$ given by $x_i\ge 0$ for $i=1,2,\ldots, n$.

Thus, every representable linear order on $\mathcal{P}_t$ is associated with one of the regions of the induced hyperplane arrangement $A^J=\{L \cap J \mid L \in A \} $. 

Let us note that due to our non-triviality assumption the vector $\left(\frac{1}{n}, \ldots, \frac{1}{n}\right)$ does not correspond to any order. Consider a utility vector ${\bf u}\in\Delta$ different from $\left(\frac{1}{n}, \ldots, \frac{1}{n}\right)$ lying in one of the regions of $A^J$ whose closure is $V$.
%
We then can normalise  ${\bf u}$ applying a positive affine linear transformation which makes its lowest utility zero. Indeed, suppose that without loss of generality $u_1\ge u_2\ge\ldots\ge u_n\ne \frac{1}{n}$. Then we can solve for $\alpha$ and $\beta$  the system of linear equations $\alpha+n\beta=1$ and $\alpha u_n+\beta=0$ and since the determinant of this system is $1-nu_n\ne 0$ its solution is unique. Then the vector of utilities ${\bf u}'=\alpha{\bf u}+\beta\cdot {\bf 1}$ will lie on the facet $\Delta^n$ of $\Delta$ and we will have $\succeq_{{\bf u}'}=\succeq_{\bf u}$. Hence the polytope $V$ has one face on the boundary of $\Delta$. We denote it $U$. So if the order $\succeq $ on $\PP_t$ is linear the dimension of $U$ will be $n-2$.

 In general, when the order on $\PP_t$ is not linear,  the utility vector $\mathbf{u}$ that  represents this order  must be a solution to the finite system of equations and strict inequalities:
\begin{equation}
\label{eq:10}
\begin{array}{rcl}
(\mu-\nu)\cdot{\bf u} & = & 0 \quad \text{whenever } \mu \sim_{\bf u} \nu,\\
(\mu-\nu)\cdot{\bf u} & > & 0 \quad \text{whenever } \mu \succ_{\bf u} \nu,
\end{array}\qquad \forall \, \mu, \nu \in \mathcal{P}_t.
\end{equation}
Then ${\bf u}$ will lie in one (or several) of the hyperplanes of $A(k,n)$. In that  hyperplane an arrangement of hyperplanes of smaller dimension will be induced by $A(k,n)$ and ${\bf u}$ will belong to a relative interior of a polytope $U$ of  dimension smaller than $n-2$.\par

Let now $\succeq= (\succeq_t)_{t \geq 1}$ be a consistent
order on $\PP$. By Theorem~2 it is locally representable. We have just seen that in such case, for any $t$, there is a convex polytope $U_t$ such that any vector ${\bf u}_t\in ri(U_t)$
represents $\succeq_t$.  Due to consistency any vector ${\bf u}_s\in
ri(U_s)$, for $s>t$ will also represent $\succeq_t$ so
$U_t\supseteq U_s$. Thus we see that our polytopes
are nested. Note that only points in the relative interior of
$U_t$ are suitable points of utilities to rationalise
$\succeq_t$. We have almost proved our main theorem. The only thing which is left to note is that the intersection $\bigcap_{t=1}^\infty
U_t$ has exactly one element. This is immediately implied by
the following

\begin{proposition}
  \label{prop:uniqueness_of_utilities}
Let ${\bf u}\ne {\bf v}$ be two distinct vectors of normalised non-negative utilities. Then there exist a positive integer $t$ and two multisets  $\mu, \nu \in \mathcal{P}_t$ such that $(\mu-\nu)\cdot {\bf u}  >  0$ but $(\mu-\nu)\cdot {\bf v}  <  0$.
\end{proposition}  

\begin{proof}
Since ${\bf u}$ and ${\bf v}$ are normalised we have, in particular, $u_n=v_n=0$.
Since ${\bf u}\ne {\bf v}$, there will be a point ${\bf x}=(\row xn)\in\R^n$ such that ${\bf x}\cdot{\bf u}  >  0$ but ${\bf x}\cdot {\bf v}  <  0$. As rational points are everywhere dense in $\R^n$ we may assume that ${\bf x}$ has rational coordinates. Then multiplying by their common denominator we may assume all coefficients are integers. After that we may change the last coordinate $x_n$ of ${\bf x}$ to $x_n'$ so that to achieve $x_1+x_2+\ldots+x_n'=0$. Now since $u_n=v_n=0$, we will still have ${\bf x}'\cdot{\bf u}  >  0$ and ${\bf x}'\cdot {\bf v}  <  0$ for ${\bf x}'=(x_1,x_2,\ldots,x_n')$. Now ${\bf x}'$ is uniquely represented as ${\bf x}'=\mu-\nu$ for two multisets $\mu$ and $\nu$. Since the sum of coefficients of ${\bf x}'$ was zero, the cardinality of $\mu$ will be equal to the cardinality of $\nu$. Let this common cardinality be $t$. Then $\mu,\nu\in {\PP}_t$ and they are separated by a hyperplane from $A(t,n)$. The proposition is proved.
\end{proof}

\begin{comment}

To enable easy reference later
in the paper, we collect these observations in the form of a Lemma
below.

\begin{lemma}
  \label{lem:convex-polytopes}
  Any consistent order $\succeq = (\succeq_t)_{t\geq1}$ on $\PP$
corresponds to a  sequence  of  convex polytopes $(U_t)_{t \geq0}$ such that
      $U_t \subseteq \Delta^i$ for some $i$ and
\begin{enumerate}
      \item  $U_{t+1} \subseteq U_t$ for all $t \geq 1$ and $\bigcap_{t=1}^\infty U_t$ consists of a single utility vector.
      \item a sequence $({\bf u}_t)_{t \geq 1} $ of vectors of $\mathbb{R}_n^{+}$ is a utility representation of $\succeq$ if and only if ${\bf u}_t$ is an affine transformation of some ${\bf u}_t' \in ri(U_t)$.
      \end{enumerate}
Moreover, $\succeq$ is globally representable iff $\bigcap_{t=1}^\infty U_t$ is contained in the relative interior $ri(U_t)$ for all $t\ge 1$.
    \end{lemma}

\end{comment}

\begin{comment}

For the rest of this section, suppose that there is a stationary
stochastic process $X_t$ that generates the rewards.  From the
probability measure that governs this process, one can compute the
probability that an action $a_i$ receives  the reward $j$ at any
given date.  Denote this probability by $q_{ij}$.  To each action $\row am$, we then have a corresponding lottery $\b q_i=(q_{i1},\ldots,q_{in})$ over the set of rewards. 

Consider, for the moment, a DM that is fully aware of the environment
and satisfies the expected utility hypothesis.  Given vNM utility
vector for the rewards $\b u = (\row u n)$, naturally we shall say
that an action $a_{i\cc}$ is a \emph{best action} for the DM if
\begin{eqnarray}
\label{eq:1}
\ip u q_{i\cc} & \geq & \ip u q_{i}  \quad \text{for all } 1 \leq i \leq m. 
\end{eqnarray}

It is interesting to compare the observed behavior 
of a DM who does not know the environment but satisfies Axioms 1-3
vis-a-vis a DM that knows the environment.  We  show the
following.

\begin{theorem}\label{moredrift}
  Consider a DM that is consistent with Axioms 1-3 and admits a global
  utility representation $\b u$. Suppose the stationary stochastic
  process $X_{t}$ is such that there is a unique best action.  Then,
  with probability one, the DM chooses the best action corresponding
  to $\b u$ at all but finitely many dates.
\end{theorem}

\begin{proof} The proof is based on the Strong Law of Large Numbers and we omit it here.
\end{proof}

\begin{remark}
  \label{rem:genericdrift}
  The best action can be shown to be determined by a finite set of linear inequalities
(\ref{eq:1}).
  For a generic choice of probabilities and global
  utility vectors, the existence of a unique best action is therefore
  assured.  Thus, the existence of a unique best action in
  Theorem~\ref{moredrift} is a weak requirement.
\end{remark}

\end{comment}

\appendix
%\singlespacing
\section*{Appendix}

%\small

{\it Proof of Claim~\ref{claim:1}}.
   Take the hypothesis as given.  If 
the actions $a,b,c,d \in \mathcal{A}$ are distinct, consider
   a history $g_t \in H_t$ such that $g_t ( a ) = h_t ( a
   )$, $g_t ( b ) = h_t ( b )$, $g_t ( c ) = h_t' ( a )$
   and $g_t ( d ) = h_t' ( b )$. Applying Axiom 2, $a
   \sim_{g_t} c$ and $b \sim_{g_t} d$ and therefore, \ $a
   \succeq_{g_t} b \, \Leftrightarrow \, c \succeq_{g_t}
   d$. Apply Axiom 1 to complete the claim.  

Suppose now that $a,b,c,d$ are not all distinct. We will prove that
if $\mu (a,h)=\mu (c,h')$ and  $\mu (b,h)=\mu (b,h')$, then 
\[
a\succeq_{h_t} b \Longleftrightarrow c\succeq_{h'_t} b,
\]
which is the main case.  Let us consider five histories presented in the following table:
\begin{center}
\begin{tabular}{c|ccccc|}
 & $h$ & $h^1$ & $h^2$ & $h^3$ & $h'$ \\
 \hline
$a$ & $h(a)$ & $h(a)$ & $h'(b)$ & $h'(b)$ & $h'(a)$\\ 
$b$ &  $h(b)$ & $h(b)$ & $h(b)$ & $h'(b)$ & $h'(b)$\\ 
$c$ & $ h(c)$ & $h'(c)$ & $h'(c)$ & $h'(c)$ & $h'(c)$\\
 \hline
 \end{tabular}
\end{center}
In what follows we repeatedly use Axiom 1 and Axiom 2 and transitivity of $\succeq_{h^i}$, $i=1,2,3$. Comparing the first two histories,  we deduce that $c \sim_{h^1} a
\succeq_{h^1} b$ and $c \succeq_{h^1} b$. Now comparing $h^1$ and $h^2$  we have $ c \succeq_{h^2} b\sim_{h^2} a$ and $ c \succeq_{h^2} a$. Next, we compare $h^2$ and $h^3$  and it follows that $c\succeq_{h^3} a\sim_{h^2} b$, whence $c\succeq_{h^3} b$. Now comparing the last two histories we obtain $c \succeq_{h'} b$, as required.
%\end{proof}

{\it Proof of Claim~\ref{claim:2}}.
  Given the fact that actions must be ranked for all conceivable
  histories, $\succeq_t\cc$ is a complete ordering of $\PP_t$.  From
  its construction, $\succeq_t\cc$ is also is reflexive.  Again,
  through appealing to Axiom 1 and Axiom 2 repeatedly, it may be
  verified that it is also transitive.  Indeed, choose
  $\mu,\nu,\xi\in \PP_t$ such that $\mu\succeq^\ast_{t} \nu$ and
  $\nu\succeq^\ast_{t} \xi$.  Pick three distinct actions $a,b,c
  \in \mathcal{A}$ and consider a history $h_t \in H_t$ such that
  $\mu(a,h_{t}) = \mu$, $\mu(b,h_t)= \nu$ and $\mu(c,h_t)=\xi$.  By
  definition, $a \succeq _{h_t} b$ and $b \succeq _{h_t} c$ while
  transitivity of $\succeq_{h_t}$ shows that $a\succeq_{h_t}c$.  Hence
  $\mu \succeq\cc_t \xi$.
%\end{proof}


\begin{thebibliography}{11}
%\expandafter\ifx\csname natexlab\endcsname\relax\def\natexlab#1{#1}\fi
%\expandafter\ifx\csname url\endcsname\relax
%  \def\url#1{{\tt #1}}\fi

\bibitem{anscombe63}
Anscombe, F.,  Aumann, R.:
\newblock A definition of subjective probabiliy.
\newblock Annals of Mathematical Statistics 34:\penalty0 199--205, (1963)

\bibitem{borgers04:_exped_monot_learn_rules}
B\"orgers, T., Morales, A.J.,  Sarin, R.
\newblock Expedient and monotone learning rules.
\newblock Econometrica 72\penalty0 (2):\penalty0 383--405 (2004)

\bibitem{brown51:_iterat_solut_of_games_by_fictit_play}
Brown, G.W.:
Iterative solutions of games by fictitious play.
In: Koopmans, T.C. (ed.) Activity Analysis of Production and Allocation,  374-376.
New York: Wiley (1951).

\bibitem{easley99:_choic_belief}
Easley, D.,  Rustichini. A.:
\newblock Choice without beliefs.
\newblock Econometrica 67\penalty0 (5):\penalty0 1157--1184 (1999)

\bibitem{fudenberg98:_theor_of_learn_in_games}
 Fudenberg, D., Levine, D.K.:
The Theory of Learning in Games,
MIT Press (1998)

\bibitem{Gale}
Gale, D.:
\newblock The Theory of Linear Economic Models.
\newblock McGraw-Hill, New-York (1960)

\bibitem{gigerenzer02:_bound_ration} Gigerenzer, G., Selten, R.:
\newblock {Bounded Rationality: The Adaptive Toolbox}.
\newblock MIT Press (2002)

\bibitem{G-S_01} 
Gilboa, I., Schmeidler, D.: A theory of case-based decisions. Cambridge University Press (2001)

\bibitem{G-S_03}
Gilboa, I., Schmeidler, D.:
\newblock {Inductive Inference: An Axiomatic Approach}.
\newblock Econometrica 71\penalty0 (1):\penalty0 1 -- 26 (2003)
%\newblock URL  \url{http://links.jstor.org/sici?sici=0012-9682%28200301%2971%3A1%3C1%3AIIAA
% A%3E2.0.CO%3B2-X}

%\bibitem{gilboa95:_case_based_decis_theor}
%I.~Gilboa and D.~Schmeidler.
%\newblock Case-based decision theory.
%\newblock {\em The Quarterly Journal of Economics} 110\penalty0 (3):\penalty0
%  605--639, 1995.
  
%\bibitem{hopkins02:_two_compet_model_of_how}
%E. Hopkins.
%Two Competing Models of How People Learn in Games,
%\newblock \emph{Econometrica}
%70(6), 2141-2166, 2002.

\bibitem{lettau95:_rules_thumb_dynam_progr}
Lettau, M., Uhlig, H.:
\newblock Rules of thumb and dynamic programming.
\newblock Tilburg University Discussion Paper (1995)

\bibitem{milnor54:_games}
Milnor, J.H.:
\newblock Games against nature.
\newblock In: Davis, C.H, Coombs, R.M.,  R.L. Thrall, R.L (eds),  Decision
Processes,  49--60. John Wiley \& Sons, Inc., (1954)

%\bibitem{robson01:_why_would_natur_give_indiv_utilit_funct}
%A.~J. Robson.
%\newblock Why would nature give individuals utility functions?
%\newblock {\em Journal of Political Economy} 109:\penalty0 900--914, 2001.

\bibitem{savage54:_found_statis}
Savage, L.J.:
\newblock The Foundations of Statistics.
\newblock Harvard University Press, Cambridge, Mass. (1954)

\bibitem{schlag98:_why_imitat_if_so_how}
Schlag, K.H.:
\newblock Why imitate, and if so, how? A boundedly rational approach to
  multi-armed bandits.
\newblock Journal of Economic Theory 78\penalty0 (1):\penalty0 130--156 (1998)

%\bibitem{Selten1} 
%R. Selten and J. Buchta.
%\newblock Experimental Sealed-Bid First Price Auctions with Directly Observed Bid
%Functions. 
%\newblock In D. Budescu, I. Erev, and R. Zwick (eds.), {\em Games and Human Behavior: Essays in the Honor of Amnon Rapoport}. NJ: Lawrenz Associates Mahwah, 1999.

%\bibitem{Selten2}
%R. Selten and R. Stoecker. 
% \newblock End Behavior in Sequences of Finite PrisonersŐ Dilemma Supergames: A
%Learning Theory Approach.
% \newblock Journal of Economic Behavior and Organization. 7, 47--70, 1986.
 
\bibitem{SS} Sertel, M. R., Slinko, A.: Ranking Committees, Words or Multisets,  Economic Theory,  30(2): 265--287 (2007)

\end{thebibliography}

\end{document}

\begin{thebibliography}{4}

\bibitem{jour} Smith, T.F., Waterman, M.S.: Identification of Common Molecular
Subsequences. J. Mol. Biol. 147, 195--197 (1981)

\bibitem{lncschap} May, P., Ehrlich, H.C., Steinke, T.: ZIB Structure Prediction Pipeline:
Composing a Complex Biological Workflow through Web Services. In: Nagel,
W.E., Walter, W.V., Lehner, W. (eds.) Euro-Par 2006. LNCS, vol. 4128,
pp. 1148--1158. Springer, Heidelberg (2006)

\bibitem{book} Foster, I., Kesselman, C.: The Grid: Blueprint for a New Computing
Infrastructure. Morgan Kaufmann, San Francisco (1999)

\bibitem{proceeding1} Czajkowski, K., Fitzgerald, S., Foster, I., Kesselman, C.: Grid
Information Services for Distributed Resource Sharing. In: 10th IEEE
International Symposium on High Performance Distributed Computing, pp.
181--184. IEEE Press, New York (2001)

\bibitem{proceeding2} Foster, I., Kesselman, C., Nick, J., Tuecke, S.: The Physiology of the
Grid: an Open Grid Services Architecture for Distributed Systems
Integration. Technical report, Global Grid Forum (2002)

\bibitem{url} National Center for Biotechnology Information, {\bf u}rl{http://www.ncbi.nlm.nih.gov}

\end{thebibliography}

\end{document}

\section*{Appendix: Springer-Author Discount}

LNCS authors are entitled to a 33.3\% discount off all Springer
publications. Before placing an order, the author should send an email, 
giving full details of his or her Springer publication,
to {\bf u}rl{orders-HD-individuals@springer.com} to obtain a so-called token. This token is a
number, which must be entered when placing an order via the Internet, in
order to obtain the discount.

\section{Checklist of Items to be Sent to Volume Editors}
Here is a checklist of everything the volume editor requires from you:


\begin{itemize}
\settowidth{\leftmargin}{{\Large$\square$}}\advance\leftmargin\labelsep
\itemsep8pt\relax
\renewcommand\labelitemi{{\lower1.5pt\hbox{\Large$\square$}}}

\item The final \LaTeX{} source files
\item A final PDF file
\item A copyright form, signed by one author on behalf of all of the
authors of the paper.
\item A readme giving the name and email address of the
corresponding author.
\end{itemize}
\end{document}
