\documentclass{llncs}
\usepackage{llncsdoc}

% Use the postscript times font!
\usepackage{times}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{sgame}
\usepackage{color}
\usepackage{comment}
\usepackage{graphicx}
\usepackage{url}

\newcommand{\R}{\mathbb{R}}

\newtheorem{defin}{Definition}
%\newtheorem{example}{Example}
\newtheorem{thm}{Theorem}

\author{Greg Hines and Kate Larson}
\institute{\email{ggdhines@cs.uwaterloo.ca} \\ \email{klarson@cs.uwaterloo.ca}\\Cheriton School of Computer Science \\ University of Waterloo \\ Waterloo, Canada}

\title{Insuring Risk-Averse Agents}
\begin{document}
\maketitle
\begin{abstract}
In this paper we explicitly model risk aversion in multiagent interactions.  We propose an \emph{insurance mechanism} that be can
used by risk-averse agents to mitigate against risky outcomes and to improve their expected utility. Given a game, we show how to
derive Pareto-optimal insurance  policies, and determine whether or not the proposed insurance policy will change the underlying dynamics of the game (\textit{i.e.}, the equilibrium). Experimental results indicate that our approach is both feasible and effective at reducing risk for agents. 
\end{abstract}

\section{Introduction}
In almost every decision people make, risk is a factor.  When negotiating a business contract, there is the risk of either side being unable to fulfill its obligations. When bidding for multiple items in an auction, there is the risk of winning too many or too few items. Even when using the Internet, there is the risk of congestion depending on the routing policy used. In most of these cases people are risk averse. The importance of the influence of risk aversion on peoples' decisions is reflected in the size of the insurance industry, a multi-trillion dollar business,~\cite{Swiss06:World} and the amount of research in economics relating to risk~\cite{Stiglitz01:Nobel}.

There is considerable research in multiagent systems on helping people make better decisions in settings such as those mentioned above. However, this research generally assumes that people are risk neutral~\cite{Conitzer07:AWESOME,Rozenfeld07:Routing,Shoham07:If}. Given the prevalence of risk aversion in the real world, we believe it is important to study how to manage the effects of risk and risk aversion in multiagent systems.

In this paper, we study non-cooperative multiagent systems. Our main contribution is an insurance mechanism that can be used in games to reduce agents' risk and increase their utility. We present a characterization of our mechanism that allows us to easily determine if the mechanism can be applied to any given game. Experimental results show that our mechanism is usable in many different situations and is scalable. The experimental results also examine how much risk aversion matters in different settings. We conclude with a discussion of related work and some promising areas for future work.




\section{The Model and Background}\label{sec:setup}
In this section we introduce our model of risk aversion for multiagent systems, as well as define the key game-theoretic concepts used in this paper. For a more thorough introduction to game theory, we refer the reader to~\cite{Mas-Colell95:Microeconomic}.

%\subsection{Background}\label{sec:background}
\begin{comment}
\begin{defin}
A n-agent \emph{game} is defined as the tuple $G=<N,A=A_1 \times \ldots \times A_n,u_1,\ldots u_n>$ where $N=\{1,\ldots,n\}$ is the set of agents, $A_i$ is the set of possible actions for agent $i$ to take and $u_i:A \rightarrow \R$ is the utility function for agent $i$. A specific action for agent $i$ is $a_i \in A_i$, and a joint action, $a = (a_1,\ldots,a_n) \in A$, denotes a specific action for each agent. We use $a_{-i}$ to denote $(a_1,\ldots,a_{i-1},a_{i+1},\ldots,a_n)$. A strategy $\sigma_i$ for agent $i$ is a probability distribution over $A_i$. Agents are assumed to be utility maximizers.
\end{defin}
\end{comment}

\subsection{A Model of Risk Aversion}\label{sec:riskModel}
In this section we propose a model of risk aversion for a multiagent setting. The approach we take in modeling risk is motivated by models used in experimental economics~\cite{Goeree03:Risk}. If an agent is risk averse, then it dislikes uncertainty. For example, if given a choice between a lottery and a guaranteed payoff, a risk-averse agent will often prefer the guaranteed payoff, \emph{even when the expected payoff from the lottery is higher.} In this paper, we model risk aversion by the concavity of an agent's utility function. Specifically, given an income $I$, if an agent's utility is of the form
\begin{equation}
U = I^r, \label{eq:utilityFunction}
\end{equation}
where $0 < r < 1$ is the \emph{risk-attitude factor}, then the agent is risk averse. This utility function is depicted in Figure \ref{fig:incomeUtility}. For this paper we will assume that income is always greater than or equal to zero; we make this assumption since studies show that humans (and thus the agents designed to represent humans in different interactions) treat loss of income differently from equivalent gain of income~\cite{Tversky92:Advances}.

\begin{figure}[t]
\begin{center}
\includegraphics[scale=0.5]{income_utility}
\end{center}
\caption{A graphical depiction of income versus utility. The dashed line represents the utility of a risk-neutral agent while the solid lines represent the utilities of a risk averse agent for different values of $r$.}\label{fig:incomeUtility}
\end{figure}

Typically, a model of risk aversion requires a distinction between \emph{income} and \emph{utility}~\cite{Rabin00:Risk}, therefore we generalize the notion of a game to reflect this distinction.
\newpage 
\begin{defin}
Let  $N$ be a set of agents,  $|N|=n$.  An \emph{income-based game} is defined as $G^I=\langle N, A, I_1,\ldots, I_n, u_1,\ldots, u_n\rangle$ where
\begin{itemize}
\item $A_i$ is the set of possible actions for agent $i$, and $A=A_1\times\ldots\times A_n$,
\item $I_i:A\rightarrow \mathbb{R}$ specifies the \emph{income} to agent $i$ given joint action $a\in A$, and
\item $u_i:\mathbb{R}\rightarrow \mathbb{R}$  is the utility function of agent $i$.
\end{itemize}
\end{defin}

We refer to the normal form (or matrix) representation of the income function as the \emph{income matrix} and to the normal form representation of the utility function as the \emph{utility matrix}.   

%For simplicity all of our examples will involve income-based games with 2 agents, each with 2 actions. However, all of our work can easily be generalized to many agents and many actions.

Agents interact by following strategies, that is, by selecting actions to play according to some distribution. We are particularly interested in \emph{correlated strategies}.

\begin{defin}
A correlated strategy $\sigma_A= \{\sigma_A(a) | a \in A\}$ is any probability distribution over $A$. The conditional correlated strategy $\sigma_{A_{-i}}(a_{-i}|a_i)$ is the probability of the joint action $(a_{-i},a_i)$ according to $\sigma_A$ given the action $a_i$ where $a_{-i} = (a_1,\ldots,a_{i-1},a_{i+1},\ldots,a_n)$.
\end{defin}

In an income-based game, agents try to maximize utility, not income. That is, agents are trying to maximize their expected utility, given by
\begin{equation}\label{eq:expectedUtility}
\sum_{a} \sigma_A(a) u_i(I_i(a)).
\end{equation}
%At times, we will consider either $I$ or $\sigma_A$ to be fixed, in which case we will omit it from the parameter set of $U$.

%An expected income set is the set of expected incomes for all joint actions given a correlated strategy.

%To help differentiate between an income-based game and a traditional game, we will refer to the latter as an \emph{utility-based game}.

\begin{comment}
Given a correlated strategy $\sigma_A$, the \emph{expected utility} for agent $i$ is
\begin{equation}
u_i(\sigma_A) = \sum_{a \in A} \sigma_A(a) u_i(a).
\end{equation}
We assume agents are rational, \textit{i.e.}, given $\sigma_{A_{-i}}$, agent $i$ will choose a $\sigma_i$ which maximizes its expected utility.
\end{comment}

In this paper, we are interested in analyzing situations involving equilibrium play. Specifically, we are interested in studying situations where agents are playing a correlated equilibrium. 

\begin{defin}
A correlated strategy $\sigma^*_A$ is a correlated equilibrium if for every agent $i$ and every $a_i \in A_i$,
\begin{align}\label{eq:correlatedEquilibrium}
& \sum_{a_{-i} \in A_{-i}} \sigma^*_{A_{-i}}(a_{-i}|a_i) u_i(I_i(a_i,a_{-i})) \\ & \ge \sum_{a_{-i} \in A_{-i}} \sigma^*_{A_{-i}}(a_{-i}|a_i) \notag u_i(I_i(a'_i,a_{-i})),
\end{align}
for all $a'_i \in A_i$. %The set of all correlated equilibria in $G$ is $C(G)$.
\end{defin}
We choose correlated equilibria as our solution concept for several reasons. First, it is a generalization of Nash equilibria, and so the techniques we propose in this paper can also be applied when a Nash equilibrium is chosen as the solution concept. Second, correlated equilibria can be ``less risky'' than Nash equilibria in that the correlation can help the agents in reducing the risk of mis-coordinating. Thus, if we can show that our approach is effective when risk is already being mitigated to some extent, then we believe that we can extrapolate our results and argue that our approach is broadly applicable and widely effective.

%We choose correlated equilibria as our solution concept for several reasons. First, it is a generalization of Nash equilibria, and so the techniques we propose in this paper can also be applied when a Nash equilibrium is chosen as the correlating solution concept. Second, correlated equilibria can be ``less risky'' than Nash equilibria in that the correlation can help the agents in reducing the risk of mis-coordinating. Thus, if we can show that our approach is effective when risk is already being mitigated to some extent, then we believe that we can extrapolate our results and argue that our approach is broadly applicable and widely effective.

To illustrate the effects of risk, we consider an example of agents determing routing policies.

\noindent \textbf{Example: } \emph{Consider two agents (Row and Column) on the Internet, each deciding on a routing policy to use. There is a public route available with a bandwidth of 200 kb/sec that is shared evenly if both agents decide to use it. Each agent also has a private route available with a bandwidth of 75 kb/sec. Suppose that both agents' utilities are given by Equation \ref{eq:utilityFunction} with $r=0.5$. Figure \ref{fig:incomeMatrixExample} shows the income (measured in bandwidth) and utility matrices of the game. Note that the unit of income is in kb/sec while utility has no units.}
\begin{figure}[!ht]
\begin{center}
\begin{game}{2}{2}[][]
& L & R \\
T & 75,75 & 75,200 \\
B & 200,75 & 100,100 \\
\end{game}
\begin{game}{2}{2}[][]
& L & R \\
T & 8.7,8.7 & 8.7,14.1 \\
B & 14.1, 8.7& 10,10 \\
\end{game}
\caption{\emph{Income (left) and utility (right) matrices for a routing problem.}}\label{fig:incomeMatrixExample}
\end{center}
\end{figure}
\emph{If agents are playing the correlated strategy $(\sigma_A((B,L)),\sigma_A((T,R))) = (0.5,0.5)$, the expected income for both agents is 137.5 kb/sec and the expected utility is 11.4. However, if the agents are guaranteed a bandwidth of 137.5 kb/sec, their utilities would increase to 11.7.}

\begin{comment}
Figure \ref{fig:utilityMatrixExample} shows the utility matrix for this income-based game using the utility function in Equation \ref{eq:utilityFunction} with a value of $r=0.5$. 
\begin{figure}[!ht]
\begin{center}
\begin{game}{2}{2}[][]
& $p_1$&$p_2$ \\
$p_1$ & 7.1,7.1 & 10,10 \\
$p_2$ & 10,10 & 7.1,7.1 \\
\end{game}
\caption{Utility matrix}\label{fig:utilityMatrixExample}
\end{center}
\end{figure}
%The joint strategy $\sigma$ is a probability distribution over $A$ given by $\prod_i \sigma_i$. 
\end{comment}

\begin{comment}
\begin{example}\label{example2}
Consider an income-based game with the income matrix shown in Figure \ref{fig:incomeMatrixExample2} and, with $r=0.5$, the utility matrix shown in Figure \ref{fig:utilityMatrixExample2}.
\begin{figure}
\begin{center}
\begin{game}{2}{2}[Agent 1][Agent 2]
& L&R \\
T & 30,5 & 0,0 \\
B & 0,0 & 5,30 \\
\end{game}
\caption{Income matrix}\label{fig:incomeMatrixExample2}
\end{center}
\end{figure}

\begin{figure}[!ht]
\begin{center}
\begin{game}{2}{2}[Agent 1][Agent 2]
& L&R \\
T & 5.48,2.24 & 0,0 \\
B & 0,0 & 2.24,5.48 \\
\end{game}
\caption{Utility matrix}\label{fig:utilityMatrixExample2}
\end{center}
\end{figure}
Using the correlated equilibrium $\{\sigma((T,L))_A =0.5,\sigma((B,R))_A =0.5\}$, both agents receive an expected income of 17.5 and an expected utility of 3.86. However, if both agents were guaranteed an actual income of 17.5, they would receive an utility of 4.18. This is a difference of more than 8\%. Note that both agents benefit from the decrease in risk.
\end{example}
\end{comment}

\subsection{Characterization of the Set of Correlated Equilibria}\label{sec:character}
Since correlated equilibria play a central role in our paper, we wish to derive a formal characterization of the set of correlated equilibria in an income-based game. (For simplicity, the rest of the paper will consider games with only two agents each with two actions. Our results can be generalized to an arbitrary number of agents and actions.) Given the income and utility matrices for a general income-based game shown in Figure \ref{fig:utilityMatrixGeneral}, suppose Agent 1 is trying to determine whether or not to follow a given correlated strategy $\sigma_A$ (assuming Agent 2 does as well).

\begin{figure}[!ht]
\begin{center}
\begin{game}{2}{2}[][]
& L&R \\
T & $a$,$b$ & $c$,$d$ \\
B & $e$,$f$ & $g$,$h$ \\
\end{game}
$~~~$
\begin{game}{2}{2}[][]
& L&R \\
T & $a^r$,$b^r$ & $c^r$,$d^r$ \\
B & $e^r$,$f^r$ & $g^r$,$h^r$ \\
\end{game}
\caption{Income matrix (left) and utility matrix (right) for a general game.}\label{fig:utilityMatrixGeneral}
\end{center}
\end{figure}

The expected utility for Agent 1 from playing $T$ when following $\sigma_A$ is
\begin{equation}
a^r \sigma_{A_2}(L|T) + c^r \sigma_{A_2}(R|T),
\end{equation}
and the expected utility for Agent 1 for instead playing $B$ is
\begin{equation}
e^r \sigma_{A_2}(L|T) + g^r \sigma_{A_2}(R|T).
\end{equation}
Therefore, for Agent 1 to be willing to follow $\sigma_A$, we require that
\begin{equation}
a^r \sigma_{A_2}(L|T) + c^r \sigma_{A_2}(R|T) \ge e^r \sigma_{A_2}(L|T) + g^r \sigma_{A_2}(R|T) \notag
\end{equation}
or
\begin{equation}
(a^r-e^r) \sigma_A(TL) + (c^r-g^r) \sigma_A(TR) \ge 0. \label{eq:correlatedEquilibriaConstraint}
\end{equation}
Similar constraints can be created for every possible agent-action combination. The set of all such constraints completely defines the set of correlated equilibria for a game.



\section{An Insurance Policy for Risk-Averse Agents}
In this section we present an insurance policy mechanism for risk-averse multiagent systems. By buying insurance for certain outcomes, risk-averse agents are able to reduce their risk and increase their expected utility. We study the use of such a mechanism in a setting where agents are playing a correlated equilibrium.

The basic idea is for agents to be both buyers and sellers of insurance. For example, Agent $i$ can buy coverage for the joint action $a$ by selling coverage for another joint action, $a'$. If the outcome of the game is $a$, agent $i$ \emph{receives} income from another agent. If the outcome of the game is $a'$, agent $i$ \emph{gives} some of its income to another agent. The unit cost of buying insurance (and the unit revenue from selling insurance) is set by a price vector $p = \{p(a) | a \in A\}$. The price vector is set by some third party; it is reasonable to assume that the correlating device of the correlated equilibrium also sets $p$.

\subsection{Creating the Insurance Policy}
Given a correlated equilibrium $\sigma^*_A$ and a price vector $p$, each agent must determine how much insurance to buy and sell for each joint action $a$, \textit{i.e.}, its demand $d_i(a)$. If $d_{i}(a) > 0$ then agent $i$ wishes to buy insurance coverage for the joint action $a$ and if $d_{i}(a) <0$, agent $i$ wishes to sell insurance coverage for the joint action $a$. Since agents are utility maximizers, the demand for each joint action can be computed by solving the constraint maximization problem:
\begin{align}
\max_{d_i}  \sum_{a \in A} \sigma^*_A(a) u_i(I_{i}(a) + d_{i}(a)),
\end{align}
\begin{align}
\text{s.t. }\sum_{a \in A} p(a) \cdot (I_{i}(a) + d_{i}(a)) = \sum_{a \in A} p(a) \cdot (I_{i}(a)), \label{eq:budget}
\end{align}
where $p(a)$ is the unit price for buying or selling insurance for the joint action $a$. The RHS of Equation \ref{eq:budget} is agent $i$'s budget given $p$, or the maximum amount of insurance it can possibly buy. Thus, agent $i$ is simply trying to determine which insurance to buy ($d(a) >0$) or to sell ($d(a) < 0)$), to maximize its expected utility while being constrained by its budget. For simplicity, let 
\begin{equation}
x_{i}(a) = I_{i}(a) + d_{i}(a).
\end{equation} 
Let
\begin{equation}
R_i(a) = \frac{\partial \sigma_A(a) u_i(x_{i}(a))}{\partial x_{i}(a)} \cdot \frac{1}{p(a)},
\end{equation}
be the ratio of marginal utility compared to cost for buying insurance coverage for the joint action $a$. Agent $i$'s utility is maximized when
\begin{equation}
R_i(a) = R_i(a'),\label{eq:maxUtil}
\end{equation}
for all $a,a' \in A$. If Equation \ref{eq:maxUtil} is not satisfied, for example if $R_i(a) > R_i(a')$, then agent $i$ would increase its utility by buying more coverage for the joint action $a$ and buying less (or selling more) coverage for the joint action $a'$. For our utility function, this gives
\begin{equation}
x_{i}(a) = \sqrt[r-1]{\frac{\sigma(a')}{\sigma(a)}\frac{p(a)}{p(a')}}x_{i}(a'). \label{eq:relationship}
\end{equation}
Equation \ref{eq:relationship} can be substituted into agent $i$'s budget constraint (Equation \ref{eq:budget}) to determine its overall demand.

\noindent\textbf{Example: } \emph{Continuing the example from Section \ref{sec:setup}, suppose the insurance price vector
\begin{equation}
\{p((B,L)) = 1,p((T,R)) = 2\}
\end{equation}
is announced and we wish to determine Row's optimal insurance coverage. In this case, Row's budget will be 350 kb/sec. Assuming $r=0.5$, Equation \ref{eq:relationship} simplifies to
\begin{equation}
x_{Row}((B,L)) = \sqrt{2} x_{Row}((T,R)).
\end{equation}
Substituting this into Equation \ref{eq:budget}, we get
\begin{align}
\sqrt{2} x_{Row}((T,R)) + 2x_{Row}((T,R)) &= 350, \\
x_{Row}((T,R)) &= 102.5.
\end{align}
Similarly, we find $x_{Row}((B,L)) = 150.0$. Therefore, agent Row wishes to purchase insurance coverage of 27.5 kb/sec for the outcome $(T,R)$ by selling 50 kb/sec of insurance coverage for the outcome $(B,L)$.}

%\subsection{Finding a Feasible Insurance Policy}
Since, given $p$, each agent can determine its demand, the next challenge is to find an appropriate $p$. The insurance price vector should be set with several goals in mind. First, the resulting insurance policy should be budget balanced, \textit{i.e.}, no external source of funding is required and the insurance policy does not make a profit. Second, the insurance policy should also be Pareto optimal, \textit{i.e.}, no agent's expected utility can be increased without decreasing another's. 
%social welfare maximizing or \emph{utilitarian}, \textit{i.e.} the sum of the agent's expected utility should be maximized. A relaxation of this goal would be a insurance policy that is Pareto optimal, 
%Alternatives to an utilitarian policy include an \emph{egalitarian policy} which maximizes the minimum expected utility out of all agents and a \emph{republican policy} which maximizes the maximum expected utility of all agents~\cite{Greenwald03:Correlated}.



The insurance policy can be guaranteed to be budget balanced by choosing a $p$ that results in supply equaling demand, \textit{i.e.}, for all $a \in A$
\begin{equation}
\sum_i d_{i}(a) = 0.
\end{equation}
To find which price vectors result in supply equaling demand, note that with our insurance mechanism, agents can only trade coverage and not create it. Therefore, our insurance mechanism is an example of an \emph{exchange market}~\cite{Mas-Colell95:Microeconomic}. Arrow and Debreu proved that for every exchange economy, there exists a price vector which results in supply equaling demand. With respect to our insurance mechanism, Arrow and Debreu's theorem is as follows:
\begin{thm}\label{thm:competitiveEquilibrium}
\cite{Arrow54:Existence} For a given game $G$ and correlated equilibrium $\sigma^*_A$, there exists some price vector $p^*$ such that 
\begin{equation}
\sum_{i} d_{i}(a) = 0,
\end{equation}
for every $a \in A$, assuming that $u_i$ is continuous, strictly concave and strongly monotone.\footnote{A utility function is strongly monotone if $u(y) > u(x)$ if $y \ge x$ and $y \neq x$.} Such an $d$ is known as a competitive equilibrium.
%\footnote{We assume that for each joint action at least one agent receives a positive income. If not, we ignore that particular joint action.}
\end{thm}

%Theorem \ref{thm:competitiveEquilibrium} holds for any utility function that is continuous, strictly convex and strongly monotone. Given the utility function in Equation \ref{eq:utilityFunction}, it is straightforward to check that it satisfies the required properties. 
It is straightforward to check that the utility function in Equation \ref{eq:utilityFunction} satisfies all the required conditions in Theorem \ref{thm:competitiveEquilibrium}. Theorem \ref{thm:competitiveEquilibrium} also requires that agents are \emph{price-takers} -- that is, each agent is unable to influence the price  of the insurance policy.  If an agent's demand (or supply) of insurance for a joint action is only a small fraction of the overall supply (or demand)  then we can reasonably assume that the agent is a price-taker. Thus, our approach will work for games where there are many agents. However, if there are only a few agents, then they may be able to influence prices, and an alternative approach might be necessary. We propose that the price-setter also guarantees that the market will clear: that is, the third party promises to meet any extra demand and buy any extra supply.

Now that we have determined that $p^*$ exists, we would like to know if it results in a Pareto optimal allocation. To do so, we rely on the following result~\cite{Mas-Colell95:Microeconomic}. 
\begin{thm}[First Fund. Thm. of Welfare Economics]
Any competitive equilibrium \newline will always result in a Pareto optimal allocation.
\end{thm}
While for most exchange markets there are multiple $p^*$, with our utility function $p^*$ is unique~\cite{Mas-Colell95:Microeconomic}. Since $p^*$ is unique, this implies that $p^*$ is also social-welfare maximizing.
%Although the uniqueness of $p^*$ is not required for our mechanism, it does make choosing a $p^*$ much simpler.  There are several techniques that can numerically calculate $p^*$ efficiently.\footnote{These approaches can run polynomially with respect to the number of commodities in a market. For our mechanism, the set of commodities is the set of possible joint actions which, in general, is of exponential size with respect to the number of agents.}   Some of the approaches also work generalized versions of our utility function which allow multiple $p^*$. 

At the same time, there is the complication that since the insurance policy will change agents' incomes and utilities, $\sigma^*_A$, the correlated equilibrium in the original game, may not remain an equilibrium once the insurance policy is in place. That is, since agents' utilities will have changed, $\sigma^*_{A_i}$  may no longer be a best response to $\sigma^*_{A_{-i}}$ and agents may wish to play other strategies. In this case, the insurance policy will no longer work since agents may now demand more coverage for certain joint actions or be willing to supply less coverage for other joint actions. Therefore, we are interested in finding a correlated equilibrium that will still be one after the insurance policy is in place. We call such an equilibrium an \emph{insurable equilibrium}. Furthermore, for a given game $G$ we would also like to provide a test to determine if any insurable equilibria exist.

To determine whether $\sigma^*_A$ is an insurable equilibrium, we start by characterizing the set of all Pareto optimal allocations. The set of Pareto optimal allocations of income can be determined by solving the following constraint maximization problem:
\begin{align}
\max_{x_i} u_i(x_i) \\
\text{s.t. } u_{-i}(I-x_i) = \bar{u}
\end{align}
for some fixed utility $\bar{u}$.  This maximization problem can be solved using the Lagrangian method to find the constraint
\begin{align}
\frac{x_{i}(a)}{x_{i}(a')} &= \frac{I(a)}{I(a')}. \label{eq:pareto}
\end{align}
For brevity, we omit the derivation.\footnote{Note that if the agents did not all have the same value for $r$, this characterization would not be possible.} Therefore, the set of Pareto optimal allocations is given by
\begin{equation}
x_{1} = \left\{ I_{a_1} \cdot l,I_{a_2} \cdot l,\ldots\right\},
\end{equation}
\begin{equation}
x_{2} = \left\{ I_{a_1} \cdot (1-l), I_{a_2} \cdot (1-l),\ldots\right\} 
\end{equation}
for $0 \le l \le 1$. The resulting set of \emph{Pareto optimal allocation games} is shown in Table \ref{fig:paretooptimalgame}.
\begin{table}[t]
\begin{center}
\begin{game}{2}{2}[][]
&L&R\\
 T& $(a+b)l$, $(a+b)(1-l)$ & $(c+d)l$,$(c+d)(1-l)$ \\
 B& $(e+f)l$, $(e+f)(1-l)$ & $(g+h)l$,$(g+h)(1-l)$ \\
\end{game}
\caption{The set of Pareto optimal allocation games where $0 \le l \le 1$.} \label{fig:paretooptimalgame}
\end{center}
\end{table}

\begin{comment}
The second challenge for our insurance mechanism is that since the insurance policy will change agents' incomes and utilities, $\sigma^*_A$ may no longer be an equilibrium under the altered game. This means that agents will no longer be willing to play according to $\sigma^*_A$ and $p^*$ will no longer result in a cleared market. 
To determine if $\sigma^*_A$ will remain a correlated equilibrium after the insurance process, we rely on the following characterization of competitive equilibria.
\begin{thm}[First fundamental theorem of welfare economics]
All competitive equilibria result in a Pareto optimal allocation. 
\end{thm}
\end{comment}

Using the same reasoning that we used to find the correlated equilibrium constraint in Equation \ref{eq:correlatedEquilibriaConstraint}, we can find the analogous constraint for the Pareto optimal allocation game:
\begin{align}
&\left\{[(a+b)l]^r - [(e+f)l]^r\right\}\sigma(TL)  \notag \\ &+ \left\{[(c+d)l]^r -[(g+h)l]^r\right\} \sigma(TR) \ge 0. \label{eq:constraint2}
\end{align}
Note that $l^r$ cancels out in Equation \ref{eq:constraint2} leaving the simplified constraint
\begin{align}
\left[(a+b)^r - (e+f)^r\right]&\sigma_A(TL) \notag \\ &+ \left[(c+d)^r -(g+h)^r\right] \sigma_A(TR) \ge 0. \label{eq:sol1}
\end{align}
Since Equation \ref{eq:sol1} does not depend on $l$, this constraint must hold for every Pareto optimal allocation, including the one created by $p^*$. Therefore, to determine if $\sigma^*_A$ is an insurable equilibrium, we simply check whether it satisfies the general set of constraints for correlated equilibria in a Pareto optimal allocation game. By incorporating a convex programming method similar to that of Papadimitriou and Roughgarden~\cite{Papadimitriou08:Computing}, our approach can easily determine whether any insurable equilibria exist for a given income-based game.

\begin{comment}
\subsection{Computational Issues}
Although linear programs can be solved in a polynomial number of iterations, Papadimitriou and Roughgarden showed that when using a linear program to find a correlated equilibrium, each iteration may require exponential time~\cite{Papadimitriou05a:Computing}. On the positive side, Papadimitriou and Roughgarden describe a large set of \emph{succinct games} which allow for a compact representation. Finding a correlated equilibrium in these games can be done in polynomial time.\footnote{Even for these games finding a specific correlated equilibrium, such as the one that maximizes social welfare, is NP-complete.}

To determine in polynomial time if a particular game has any insurable correlated equilibria, both the original game and the Pareto optimal allocation game must be succinct games. It remains an open question which, if any, of the succinct games Papadimitriou and Roughgarden describe also give succinct Pareto optimal allocation games.

Once we have determined that a particular equilibrium is insurable, we need to calculate the resulting insurance policy. The oldest and simplest method for numerically calculating the insurance policy is the t\^{a}tonnement process which may be thought of as a type of gradient descent~\cite{Mas-Colell95:Microeconomic}. While the t\^{a}tonnement process only works in restricted settings, it is applicable for our mechanism. Additionally, when appropriate, the t\^{a}tonnement process has be shown to preform very well compared to sophisticated approaches, such as convex programming~\cite{Codenotti08:Experimental}.
%which can be used in more general settings (\textit{i.e.} when different utility functions are used
\end{comment}

\section{Experimental Evaluation}
In this section we describe the experimental evaluation of our insurance mechanism. In particular, we study the extent of its applicability and the amount that it improves the utility of the participating agents.



\subsection{Experimental Setup}

We conducted our experiments using games with 2 agents with 2 actions per agent, 3 agents with 3 actions per agent, and 4 agents with 4 actions per agent. For each game, the income values were drawn randomly from one of two distributions: the first was the uniform distribution over $[0,10]$, and the second distribution was a bi-modal Gaussian with $N_1(10,3)$ and $N_2(100,3)$. This second distribution was used to generate high-risk games. For all experiments we set the risk-attitude factor $r=0.6$. Experimental evidence suggests that this value often captures humans' risk-attitudes~\cite{Goeree03:Risk}, without being too extreme in either direction.  We repeated each experiment 100 times, and all results reported are averaged over these repetitions. A linear program was used to determine if an equilibrium was insurable. We then used the t\^{a}tonnement process to find the resulting insurance prices~\cite{Mas-Colell95:Microeconomic}.

In each of our experiments, there were three things we studied. First, we were interested in determining what percentage of games actually had insurable equilibria. This measurement allows us to determine the applicability of our approach.
Second, for insurable equilibria,  we were interested in understanding how effective our insurance mechanism was at reducing risk. For an agent to completely remove risk from a game, it must receive the same income for every possible outcome, so for a given game, we define $u_i^{Orig}$ to be the expected utility to agent $i$ in the original (non-insured) game, $u_i^{Ins}$ to be the expected utility in the insured game, and $u_i^{RF}$ to be the expected utility if the game was made to be risk-free.  We define the  \emph{insurance effectiveness}  for agent $i$ ($IE_i$) as
\begin{equation}
IE_i=\frac{u_i^{Ins}-u_i^{Orig}}{u_i^{RF}-u_i^{Orig}} \times 100\%.
\end{equation}
\noindent Finally, we were interested in understanding the underlying cost of risk aversion in terms of utility loss for an agent $i$. We define the \emph{cost of risk aversion} of agent $i$ ($CORA_i$) as
\begin{equation}
CORA_i=\frac{u_i^{RF}-u_i^{Orig}}{u_i^{RF}} \times 100\%.
\end{equation}


\subsection{Results}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{table}[t]
\centering
\begin{tabular}{|c|| c|c|}\hline 
 & \multicolumn{2}{c|}{Distribution} \\ \hline
 Game Size & Uniform & Bi-modal Gaussian \\ \hline
 2 agents, $|A_i|= 2$ & 5\% & 5\% \\ \hline
 3 agents, $|A_i|= 3$ & 95\% & 94\% \\ \hline
 4 agents, $|A_i|= 4$ & 91\% & 100\% \\ \hline
\end{tabular}
\caption{\label{tab:InsurableEq} The percentage of insurable equilibria in randomly-generated games of different sizes, generated by two different distributions.}
\end{table}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Table~\ref{tab:InsurableEq} presents our findings on how often  insurable equilibria exist. We present our findings from games generated from both distributions. In general, we found that for games with more than two agents, insurable equilibria were very common, and over 90\% of all games generated had insurable equilibria. For the randomly generated two-agent, two-action games, we found that insurable equilibria were quite rare, occurring in only 5\% of games. While at first glance this was disappointing, upon further investigation of the two-agent, two-action games, we noticed that most of these games had a single pure-strategy Nash equilibrium.  For such games there is no risk in mis-coordinating, and thus no need for an insurance policy.

 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{table}[t]
 \centering
 \begin{tabular}{|c||c|c|}\hline
 Game Size & IE & CORA \\ \hline\hline
 2 agents, $|A_i|= 2$ & 25\% & 4.5 \% \\ \hline
 3 agents, $|A_i|= 3$ & 72\% & 8.2 \% \\ \hline
 4 agents, $|A_i|= 4$ & 76.8\% & 12 \% \\ \hline 
 \end{tabular}
 \caption{\label{tab:Measurements} Average insurance effectiveness ($IE$) and costs of risk aversion ($CORA$) in games generated using the bi-modal Gaussian distribution. For $IE$, values closer to 100\% show that the insurance mechanism is improving the expected utility for an agent (if $IE=100\%$ then the optimal utility is achieved). For $CORA$, a value of 4.5\%, for example, indicates that risk aversion leads to a 4.5\% decrease in utility, compared to a risk-neutral approach.}
 \end{table}
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
Table~\ref{tab:Measurements} presents our findings for the $IE$ and $CORA$ measurements for different sizes of games, drawn from the bimodal distribution. The results presented are averaged over all games where there was an insurable equilibrium, and over all agents in those games.  We make two important observations. First, as the game increases in size, the impact that risk has (as measured by $CORA$) also increases.  Second, as CORA increases, so does the effectiveness of our insurance mechanism (as measured by $IE$).  
When games were generated using the uniform distribution (results not presented), we observed that there was less overall risk. In particular, the $CORA$ measurement was never greater than 3\% on average, and thus, overall, the insurance effectiveness was also quite low. Given these results, we conclude that when risk is an important factor in a game, our insurance mechanism is highly effective. When there is little risk, however, it provides only minimal advantage. 

\begin{comment}
\section{Discussion}
When we presented the Arrow-Debreu Theorem (Theorem 1) and argued that it implied the existence of an insurance policy, there were two additional conditions which we implicitly assumed were met. In this section, we re-visit the theorem and explicitly discuss these conditions.

The first condition is that for every joint action, at least \emph{one} agent must obtain positive income. This can be met by ignoring all joint actions where this is not the case. Since this simply results in more complex notation, in this paper, we have assumed that this case never occurs.

The second condition is more important and potentially has larger repercussions.  Arrow-Debreu's Theorem assumes that agents are \emph{price-takers} -- that is, each agent is unable to influence the price  of the insurance policy.  If an agent's demand (or supply) of insurance for a joint action is only a small fraction of the overall supply (or demand)  then we can reasonably assume that the agent is a price-taker. Thus, our approach will work for games where there are many agents. However, if there are only a few agents, then they may be able to influence prices, and an alternative approach might be necessary. We propose that the price-setter also guarantees that the market will clear. That is, the third party promises will meet any extra demand and buy any extra supply.

%Alternatives to an utilitarian policy include an \emph{egalitarian policy} which maximizes the minimum expected utility out of all agents and a \emph{republican policy} which maximizes the maximum expected utility of all agents~\cite{Greenwald03:Correlated}.

%While there are alternative models of risk aversion  this model has been shown to be useful at explaining human behaviour in repeated games~\cite{Goeree03:Risk}. While this paper does not specifically deal with repeated games, it is an area we wish to examine in the future.
\end{comment}

\section{Related Work}
The standard insurance model assumes an initial level of wealth with some probability of an accident, \textit{i.e.}, some loss of wealth, represented by a probability density function~\cite{Arrow71:Essays,Raviv79:Design}. Someone interested in buying insurance decides on the type of coverage they want: the maximum coverage, the deductible, the level of coinsurance, \textit{etc.} The insurer then decides on the premium to charge for that particular insurance policy. Research in insurance has examined questions such as determining the optimal policy to buy and the optimal premium to charge~\cite{Arrow71:Essays,Raviv79:Design}. Other work has dealt with the effects of asymmetric information, moral hazards, and adverse selection~\cite{Rothschild76:Equilibrium}. 

Game theory has been used to a limited degree in the study of insurance; for example, in analyzing the actions of insurance companies in competitive markets~\cite{Rothschild76:Equilibrium}. However, this work ignores any strategic interaction between insurance buyers by assuming the insurance companies can supply any and all requested insurance policies with non-negative returns. Arrow and Raviv have both used decision theory in determining the optimal actions of both buyer and seller~\cite{Arrow71:Essays,Raviv79:Design}. Since their work focuses on the actions of an isolated buyer and seller, this is more an application of decision theory than game theory.

The insurance research closest to our work is the study of \emph{reciprocal reinsurance}: the exchange of risk between insurance companies~\cite{Borch74:Mathematical}. Borch considered the problem as an $n$-person coalitional game and was able to solve it for $n=2$. This work made several assumptions that our work does not, such as assuming that the probabilities of the different outcomes are independent and companies have additional outside money to use. The goal is for the two companies, A and B, to reach a deal where A pays B to cover a specific amount of A's risk (or vice-versa). Borch presented this as a bargaining problem, where companies had to find an amount to be paid and the risk to be covered, and suggested the Nash bargaining solution as the desired outcome.

There has been limited work on risk in multiagent systems. Exceptions include work by Lam \textit{et al.}, which proposed an insurance scheme for agents trying to obtain resources~\cite{Lam05:Insurance}. In their work insurance premiums were paid to specific \emph{insurance agents} who, in return, guaranteed that necessary resources were always available. The effects of risk aversion have been studied more often in auction design. Page, for example, studied the problem of optimal auction design with both risk-averse buyers and a risk-averse seller~\cite{Page94:Optimal} while the effects of risk aversion in sequential auctions was studied by Robu and La Poutr\'{e}~\cite{Robu07:Designing}. 

\section{Conclusion}
In this paper we commenced a formal study of risk and risk-aversion in multiagent systems. We presented a mechanism that allows agents to buy and sell \emph{insurance} in order to protect themselves against undesirable outcomes.  We described how to derive Pareto-optimal insurance policies, and provided a characterization of \emph{insurable equilibria} for two-player games. Experimental results indicated that when risk is prevalent in the agents' interactions, our insurance mechanism effectively mitigates the risk and improves the expected utility of all agents.

There are many interesting open challenges related to our insurance mechanism. First, we would like to study our mechanism in a 2-stage game model. This might allow for a more generalized equilibrium model, and also be useful in a repeated game model. The repeated game model could be used to study a non-equilibrium setting; a non-equilibrium model might involve relaxing the balanced-budget requirement and using a \emph{targeted optimality} approach, where we would optimize the insurance mechanism for specific types of agents and games. Studying repeated games may also allow the use of credit and savings to reduce risk, and it would be interesting to compare the advantages of an insurance mechanism against a credit-and-savings mechanism. Secondly, we are interested in trying to apply our insurance mechanism to other models of multiagent systems such as cooperative games and collaborative multiagent systems. Thirdly, we would like to investigate whether other models of risk aversion are more useful. We are specifically interested in how cumulative prospect theory and loss aversion could be used in multiagent systems~\cite{Tversky92:Advances}. It would also be interesting to compare the advantages and disadvantages of the core and competitive equilibrium as different solution concepts. Finally, we would like to implement our insurance mechanism in real life settings. In such settings, agents may be unaware of their own degree of risk aversion or may choose to lie about it. As a result, there would be a need to use preference elicitation and mechanism design.

\bibliographystyle{plain}
\bibliography{references}
\end{document}