[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[freehaven-cvs] alessandro"s reworking
Update of /home/freehaven/cvsroot/doc/fc03
In directory moria.seul.org:/home/arma/work/freehaven/doc/fc03
Modified Files:
econymics.tex
Log Message:
alessandro's reworking
Index: econymics.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/fc03/econymics.tex,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -d -r1.5 -r1.6
--- econymics.tex 13 Sep 2002 19:32:08 -0000 1.5
+++ econymics.tex 13 Sep 2002 19:50:12 -0000 1.6
@@ -16,7 +16,7 @@
%\textheight=10in
%\topmargin=-1.2in
%\oddsidemargin .35in
-%\evensidemargin .35in
+%\evensidemargin .35in
\begin{document}
@@ -69,7 +69,6 @@
-
\newcommand{\workingnote}[1]{} % The version that hides the note.
%\newcommand{\workingnote}[1]{(**#1)} % The version that makes the note visible.
@@ -79,7 +78,7 @@
%\title{Topics in the Economics of Anonymity}
%\title{The Economics of Anonymity}
%\title{On the Economics of Anonymity}
-\author{Alessandro Acquisti\inst{1} \and Roger Dingledine\inst{2} \and Paul Syverson\inst{3}}
+\author{Alessandro Acquisti\inst{1} \and Roger Dingledine\inst{2} \and Paul Syverson\inst{3}}
\institute{SIMS, UC Berkeley
\email{(acquisti@sims.berkeley.edu)}
\and
@@ -115,7 +114,7 @@
\section{Introduction and motivation}
Anonymity in communication over public networks such as the Internet
-%has received a lot of technical attention and
+%has received a lot of technical attention and
is widely (though not
uncontroversially) regarded as both desirable and necessary. People
want to be able to surf the Web, purchase online, send email, etc.\
@@ -204,11 +203,28 @@
part of a given \emph{adversary}, a context within which strategic
agents must operate.
-\section{General view}
+\section{An Economics of Anonymity}
+
+alessandrocomment\{I feel that, possibly, even more
+of the material that you guys had already written could be used for a
+general section - like this one - on top of the Introduction/Motivation
+above. My feeling is that 1) this section could be used to frame the problem
+from an economic perspective (while the Introduction might focus on the
+technical perspective and highlight the *need* for an economic perspective);
+2) this section would ``prepare'' the analytic framework below; 3)\ it would
+also suggest that our work is more general than the specific
+model/application presented one section below, in that such model is a
+preliminary applications of the views we are presenting here.\}
+
+\section{Analytic Framework}
We study the incentives for agents to send messages anonymously through
mix-net like systems.
+alessandrocomment\{I will try to clean up this
+section later on. Currently it is very diffult to read as it is presented as
+an enumeration of items\}
+
\begin{itemize}
\item Agents value their privacy, hence they have an interest in using a
mix-net system. This interest might be related to profits they will make by
@@ -223,15 +239,14 @@
\begin{itemize}
\item sending messages through the system, $a_{s}$,
-
-\item or/and agreeing to receive dummy traffic\footnote{We make here
- the assumption users of the system are interested in sending
- information anonymously; receiving valid traffic from the system
- is not an action of `using the system'. This might not always be
- the case, e.g., for remailer mixes with reply blocks or for
- bidirectional connections as in Crowds or Onion Routing. And, it may
- have costs and/or benefits.} through the system, $a_{r}$;
+\item or/and agreeing to receive dummy traffic\footnote{%
+We make here the assumption users of the system are interested in sending
+information anonymously; receiving valid traffic from the system is not an
+action of `using the system'. This might not always be the case, e.g., for
+remailer mixes with reply blocks or for bidirectional connections as in
+Crowds or Onion Routing. And, it may have costs and/or benefits.} through
+the system, $a_{r}$;
\end{itemize}
\item act as honest nodes, $a_{h}$, which can involve:
@@ -266,242 +281,226 @@
\item The payoffs $U$ for the agents come from:
\begin{itemize}
-\item subjective value of sending messages anonymously. This is
- function of the subjective value of the information successfully
- arriving at its destination, $v_{r}$, the subjective value of the
- information remaining anonymous, $v_{a}$, the perceived level of
- anonymity in the system, $p_{a}$ (i.e., the probability that sender
- and message will remain anonymous)\footnote{Simple probability may
- not be the ultimate best measure of anonymity. For example, it is
- likely that information theoretic metrics as in
- \cite{Serj02,Diaz02} are better. However, probabilities are
- typically simpler and also better than the common ``anonymity set''
- representation of anonymity. Detailed discussion of such issues
- are beyond the scope of this paper.}, the perceived level of
- reliability in the system, $p_{r}$ (i.e., the probability that the
- message will be delivered). The subjective value of the information
- being sent is possibly correlated to potential profits the agent
- expects to make by keeping certain messages anonymous or potential
- losses that the agents expects to avoid by keeping certain messages
- anonymous. The level of anonymity in the system is function of
- traffic (number of agents sending messages in the system, $n_{s}$)
- and mixes (number of agents acting as honest nodes, $n_{h}$;
- however, at parity of traffic, sensitive agents might want fewer
- nodes in order to maintain high anonymity sets). The level of
- reliability in the system is inverse function of the number of
- dishonest nodes in the system, $n_{d}$. However, it must be noted
- that different users might value reliability and anonymity
- differently. In particular, even if agents agree on a metrics for
- reliability and a metrics for anonymity, some might care more about
- anonymity than reliability, some viceversa.
-
-\item benefits of acting as a node (e.g., nodes might be retributed
- for forwarding traffic or for creating dummy traffic), $b_{h}$;
-
-\item benefits of acting as dishonest node (e.g., dishonest node might
- benefit from disrupting the service or might make use of the
- information that passes through them), $b_{d}$;
-
-\item costs of using the system by:
+\item subjective value of sending messages anonymously. This is function
+of the subjective value of the information successfully arriving at its
+destination, $v_{r}$, the subjective value of the information remaining
+anonymous, $v_{a}$, the perceived level of anonymity in the system, $p_{a}$
+(i.e., the probability that sender and message will remain anonymous)%
+\footnote{%
+Simple probability may not be the ultimate best measure of anonymity. For
+example, it is likely that information theoretic metrics as in \cite
+{Serj02,Diaz02} are better. However, probabilities are typically simpler
+and also better than the common ``anonymity set'' representation of
+anonymity. Detailed discussion of such issues are beyond the scope of this
+paper.}, the perceived level of reliability in the system, $p_{r}$ (i.e.,
+the probability that the message will be delivered). The subjective value
+of the information being sent is possibly correlated to potential profits
+the agent expects to make by keeping certain messages anonymous or
+potential losses that the agents expects to avoid by keeping certain
+messages anonymous. The level of anonymity in the system is function of
+traffic (number of agents sending messages in the system, $n_{s}$) and
+mixes (number of agents acting as honest nodes, $n_{h}$; however, at parity
+of traffic, sensitive agents might want fewer nodes in order to maintain
+high anonymity sets). The level of reliability in the system is inverse
+function of the number of dishonest nodes in the system, $n_{d}$. However,
+it must be noted that different users might value reliability and anonymity
+differently. In particular, even if agents agree on a metrics for
+reliability and a metrics for anonymity, some might care more about
+anonymity than reliability, some viceversa.
- \begin{itemize}
- \item sending messages:
+\item benefits of acting as a node (e.g., nodes might be retributed for
+forwarding traffic or for creating dummy traffic), $b_{h}$;
- \begin{itemize}
- \item through the mix-net system, $c_{s}$,
-
- \item or through the conventional, non anonymous system, $c_{n}$;
- \end{itemize}
-
- \item receiving dummy traffic, $c_{r}$;
- \end{itemize}
-
-\item costs of acting as honest node, $c_{h}$ by:
+\item benefits of acting as dishonest node (e.g., dishonest node might
+benefit from disrupting the service or might make use of the information
+that passes through them), $b_{d}$;
- \begin{itemize}
- \item receiving and forwarding traffic,
-
- \item creating dummy traffic,
-
- \item being exit node (which involves potential exposure to
- liabilities or abuses);
- \end{itemize}
-
- (we might note that there might be both fixed and variable costs in
- being a node, the fixed costs related to the investment necessary to
- setup the software, the variables being most likely related to
- traffic passing through the node);
-
-\item costs of acting as dishonest node, $c_{d}$ (e.g., being exposed
- as a dishonest node carries a monetary penalty).
-
-\item In addition to the above costs and benefits, there might be also
- \textit{reputation} costs and benefits from:\
+\item costs of using the system by:
- \begin{itemize}
- \item using the system to send messages (e.g., there can be a
- reputation cost of being exposed as a sender of anonymous messages
- even though the sent messages themselves do remain anonymous),
-
- \item acting as perceivably honest node (e.g., there can be a
- reputation benefit by acting as node),
-
- \item acting as perceivably dishonest node (e.g., there can be a
- reputation cost by being exposed as a dishonest node, and the
- costs here will be also function of the probability of being
- exposed as a bad node);
- \end{itemize}
-
- These reputation costs and benefits might be simply ``internal'' to
- the system (e.g., being perceived as a honest node brings that node
- more traffic, and therefore more possibilities to hide that node's
- messages; similarly, being perceived as a dishonest node might bring
- traffic away from that node), in which case they will not enter
- directly the utility functions of the agents, but will enter
- indirectly through the changes they provoke in the behavior of the
- agents.
- \end{itemize}
-
-\item Agents want to maximize their expected utility, which is some
- function of expected benefits minus expected costs. We can start
- representing the utility\ for a generic agent $i$ in the following
- compact form:
+\begin{itemize}
+\item sending messages:
+
+\begin{itemize}
+\item through the mix-net system, $c_{s}$,
+
+\item or through the conventional, non anonymous system, $c_{n}$;
+\end{itemize}
+
+\item receiving dummy traffic, $c_{r}$;
+\end{itemize}
+
+\item costs of acting as honest node, $c_{h}$ by:
+
+\begin{itemize}
+\item receiving and forwarding traffic,
+
+\item creating dummy traffic,
+
+\item being exit node (which involves potential exposure to liabilities or
+abuses);
+\end{itemize}
+
+(we might note that there might be both fixed and variable costs in being a
+node, the fixed costs related to the investment necessary to setup the
+software, the variables being most likely related to traffic passing
+through the node);
+
+\item costs of acting as dishonest node, $c_{d}$ (e.g., being exposed as a
+dishonest node carries a monetary penalty).
+
+\item In addition to the above costs and benefits, there might be also
+\textit{reputation} costs and benefits from:\
+
+\begin{itemize}
+\item using the system to send messages (e.g., there can be a reputation
+cost of being exposed as a sender of anonymous messages even though the
+sent messages themselves do remain anonymous),
+
+\item acting as perceivably honest node (e.g., there can be a reputation
+benefit by acting as node),
+
+\item acting as perceivably dishonest node (e.g., there can be a
+reputation cost by being exposed as a dishonest node, and the costs here
+will be also function of the probability of being exposed as a bad node);
+\end{itemize}
+
+These reputation costs and benefits might be simply ``internal'' to the
+system (e.g., being perceived as a honest node brings that node more
+traffic, and therefore more possibilities to hide that node's messages;
+similarly, being perceived as a dishonest node might bring traffic away
+from that node), in which case they will not enter directly the utility
+functions of the agents, but will enter indirectly through the changes they
+provoke in the behavior of the agents.
+\end{itemize}
+
+\item Agents want to maximize their expected utility, which is some
+function of expected benefits minus expected costs. We can start
+representing the utility\ for a generic agent $i$ in the following compact
+form:
\begin{equation*}
u_{i}=u\left( \gamma \left( v_{r},p_{r}\right) \partial \left(
-v_{a},p_{a}\right) +b_{d,h}-c_{s,h,d,n,r}\right)
+v_{a},p_{a}\right) +b_{d,h}-c_{s,h,d,n,r}\right)
\end{equation*}
-
\end{itemize}
-where $u$ is for the moment an unspecified functional form. This
-function includes the costs and benefits for all the possible actions
-of the agents, including \textit{non} using the mix-net and sending
-the messages through a non anonymous channel (in which case, for
-example, the probability of remaining anonymous, $p_{a}$, will be
-equal to zero and the only cost in the function will be $c_{n}$). Note
-that $\gamma $ and $\partial \ $represents functions of the
-probability of a message being delivered and a message remaining
-anonymous respectively. These probabilities are weighted with the
+where $u$ is for the moment an unspecified functional form. This function
+includes the costs and benefits for all the possible actions of the agents,
+including \textit{non} using the mix-net and sending the messages through a
+non anonymous channel (in which case, for example, the probability of
+remaining anonymous, $p_{a}$, will be equal to zero and the only cost in the
+function will be $c_{n}$). Note that $\gamma $ and $\partial \ $represents
+functions of the probability of a message being delivered and a message
+remaining anonymous respectively. These probabilities are weighted with the
values $v_{r,a}$ because different $i$s might value anonymity and
reliability differently.
\section{Application}
-The above system is a very general overview of economic issues related
-to the \textit{actual} use of \textit{actual} anonymous systems. As it
-is, such overview is however unmanageable for economic analysis, but
-it can be used as a framework for the study of limited scenarios given
-specific assumptions.
+The above system is a very general overview of economic issues related to
+the \textit{actual} use of \textit{actual} anonymous systems. As it is, such
+overview is however unmanageable for economic analysis, but it can be used
+as a framework for the study of limited scenarios given specific assumptions.
-Hence, a possible starting model based on the latter simplification is
-the following. We consider a set of $n_{s}$ agents interested in
-sending anonymous communications. They come in two types - those with
-high sensitivity to privacy and those with a lower (but not zero)
-sensitivity. There is only one system which can be used to send
-anonymous messages, and one another system to send non anonymous
-messages. Each user has three options: only send her own messages
-through the mix-net, or send her messages but also act as node
-forwarding other users' messages, or send a message without using the
-mix-net. This means that initially we do not consider the strategy of
-choosing to be a bad node or additional honest strategies like
-creating and receiving dummy traffic.
+Hence, a possible starting model based on the latter simplification is the
+following. We consider a set of $n_{s}$ agents interested in sending
+anonymous communications. They come in two types - those with high
+sensitivity to privacy and those with a lower (but not zero) sensitivity.
+There is only one system which can be used to send anonymous messages, and
+one another system to send non anonymous messages. Each user has three
+options: only send her own messages through the mix-net, or send her
+messages but also act as node forwarding other users' messages, or send a
+message without using the mix-net. This means that initially we do not
+consider the strategy of choosing to be a bad node or additional honest
+strategies like creating and receiving dummy traffic.
\subsection{Adversary}
-We do not consider our strategic agents as potentially choosing to be
-bad nodes; nonetheless we do consider that there may be a percentage
-of bad nodes and that agents respond to this possibility. Specifically
-we assume a global passive adversary (GPA) that can observe all
-traffic on all links (between users and nodes, between nodes, and
-between nodes or users and recipients). Additionally, the adversary is
-assumed to include some percentage of mix-nodes. In choosing
-strategies agents will attach a subjective probability to arbitrary
-nodes being compromised, i.e., all nodes not run by the agent are
-assigned the same probability of being compromised by that agent. This
-will be a factor in their assessment of the probability of the
-anonymity of messages they send. For our purposes, it will not matter
-whether the set of compromised nodes is static or dynamic (as in
-\cite{syverson_2000}). In general, we assume that all agents will
-attach the same probability of compromise to all nodes (except for
-nodes that an agent herself owns). A purely passive adversary is
-unrealistic in most settings, e.g., it assumes that hostile users
-never selectively send messages at certain times or routes, and
-neither nodes nor links ever selectively trickle or flood messages
-\cite{trickle02}. Nonetheless, a \emph{global} passive adversary is
-still quite strong, indeed unrealistically so, and a typical starting
-point of anonymity analyses.
-
+We do not consider our strategic agents as potentially choosing to be bad
+nodes; nonetheless we do consider that there may be a percentage of bad
+nodes and that agents respond to this possibility. Specifically we assume a
+global passive adversary (GPA) that can observe all traffic on all links
+(between users and nodes, between nodes, and between nodes or users and
+recipients). Additionally, the adversary is assumed to include some
+percentage of mix-nodes. In choosing strategies agents will attach a
+subjective probability to arbitrary nodes being compromised, i.e., all nodes
+not run by the agent are assigned the same probability of being compromised
+by that agent. This will be a factor in their assessment of the probability
+of the anonymity of messages they send. For our purposes, it will not matter
+whether the set of compromised nodes is static or dynamic (as in \cite
+{syverson_2000}). In general, we assume that all agents will attach the same
+probability of compromise to all nodes (except for nodes that an agent
+herself owns). A purely passive adversary is unrealistic in most settings,
+e.g., it assumes that hostile users never selectively send messages at
+certain times or routes, and neither nodes nor links ever selectively
+trickle or flood messages \cite{trickle02}. Nonetheless, a \emph{global}
+passive adversary is still quite strong, indeed unrealistically so, and a
+typical starting point of anonymity analyses.
-\subsection{(Honest) Strategic Agents}
+\subsection{(Honest) Agents}
-If a user only sends her messages, the cost of using the anonymous
-service is slightly higher than using the non anonymous channel. If a
-user decides to be a node, costs increase with the traffic. The
-traffic depends on the number of users in the system (but, as
-mentioned above, the traffic also affects the level of anonymity).
-Given that there are no actively bad nodes (and assuming that the only
-possible failures are hostile ones), reliability is deterministically
-complete ($p_{r}=1$). Even if all messages are assumed to arrive, they
-may take much longer to arrive through the anonymity system than if
-sent without it. Perception of this can be reflected in the difference
-of $c_s$ and $c_n$. We also assume that all agents know the number of
-agents using the system and the number of them acting as nodes, and
-that each specific agent's actions are observable. Furthermore, we
-assume that the type of an agent is publicly known (i.e. a high
-sensitivity type cannot pretend to be a low type). As already noted,
-we also assume that all agents perceive anonymity the same way.
+If a user only sends her messages, the cost of using the anonymous service
+is slightly higher than using the non anonymous channel. If a user decides
+to be a node, costs increase with the traffic. The traffic depends on the
+number of users in the system (but, as mentioned above, the traffic also
+affects the level of anonymity). Given that there are no actively bad nodes
+(and assuming that the only possible failures are hostile ones), reliability
+is deterministically complete ($p_{r}=1$). Even if all messages are assumed
+to arrive, they may take much longer to arrive through the anonymity system
+than if sent without it. Perception of this can be reflected in the
+difference of $c_s$ and $c_n$. We also assume that all agents know the
+number of agents using the system and the number of them acting as nodes,
+and that each specific agent's actions are observable. Furthermore, we
+assume that the type of an agent is publicly known (i.e. a high sensitivity
+type cannot pretend to be a low type). As already noted, we also assume that
+all agents perceive anonymity the same way.
-These assumptions let us reformulate the framework above in a simpler
-way. Imagine that both agent types use the system because they want
-to avoid potential losses from not being anonymous. The types differ
-in their sensitivity to those losses: high, $v_{H}$, and low, $v_{L}$.
-Then, the utility function above can be written in a simpler form:
+These assumptions let us reformulate the framework above in a simpler way.
+Imagine that both agent types use the system because they want to avoid
+potential losses from not being anonymous. The types differ in their
+sensitivity to those losses: high, $v_{H}$, and low, $v_{L}$. Then, the
+utility function above can be written in a simpler form:
\begin{equation*}
u_{i}=-v_{i}\left( 1-p_{a}\left( n_{s},n_{h},d_{i}\right) \right)
-c_{s}-c_{h}\left( n_{s}\right) -c_{n}
\end{equation*}
-The above function reads in the following way: each agent $i$ tries to
-\textit{minimize} the costs of sending messages and the risk of them
-being tracked. $1-p_{a}\left( n_{s},n_{h},d_{i}\right) $ is the
-probability that the anonymity will be lost given the number of agents
-sending messages, the number of them acting as nodes, and the action
-$d$ of agent $i$ itself. For example, suppose that there are a
-thousand agents sending messages at regular intervals (no more than
-one message per agent is sent to any incoming node at a time), that
-the probability of any node being compromised is $0.1$, and that
-messages pass through three nodes before exiting the network. Assume
-that routes are chosen at random unless the sender owns a node. In
-that case the sender uses his own node as the first one and chooses
-the next two at random. If an agent does not run a node, then the
-probality that he will by identified with certainty as the sender of a
-message that exits the mix network is $.001$. If an agent runs a mix
-node with firing threshold of $50$, then amongst messages leaving the
-mix net a passive adversary can with certainty reduce the anonymity
-set (the set of possible messages that might be the sender's) to no
-less than $50$. And the probability of even doing that is the
-probability that all of the messages from the relevant mix batch pass
-only through bad nodes on the remaining two hops, i.e, $10^{-100}$. If
-we pessimistically equate the probability of guessing a message with
-the probability of identifying it with certainty, then the increase in
-anonymity acheived by running ones own node here is $2 \times
-10^{99}$. This example incorporates alot of simplifying assumptions,
+The above function reads in the following way: each agent $i$ tries to
+\textit{minimize} the costs of sending messages and the risk of them being
+tracked. $1-p_{a}\left( n_{s},n_{h},d_{i}\right) $ is the probability that
+the anonymity will be lost given the number of agents sending messages, the
+number of them acting as nodes, and the action $d$ of agent $i$ itself. For
+example, suppose that there are a thousand agents sending messages at
+regular intervals (no more than one message per agent is sent to any
+incoming node at a time), that the probability of any node being compromised
+is $0.1$, and that messages pass through three nodes before exiting the
+network. Assume that routes are chosen at random unless the sender owns a
+node. In that case the sender uses his own node as the first one and chooses
+the next two at random. If an agent does not run a node, then the probality
+that he will by identified with certainty as the sender of a message that
+exits the mix network is $.001$. If an agent runs a mix node with firing
+threshold of $50$, then amongst messages leaving the mix net a passive
+adversary can with certainty reduce the anonymity set (the set of possible
+messages that might be the sender's) to no less than $50$. And the
+probability of even doing that is the probability that all of the messages
+from the relevant mix batch pass only through bad nodes on the remaining two
+hops, i.e, $10^{-100}$. If we pessimistically equate the probability of
+guessing a message with the probability of identifying it with certainty,
+then the increase in anonymity acheived by running ones own node here is $2
+\times 10^{99}$. This example incorporates alot of simplifying assumptions,
e.g., about patterns of sending messages and adversary passivity.
-Nonetheless, it should be clear that there is a large potential gain
-from running one's own node. $v_{i}$ is the disutility an agent
-derives from its message being exposed; we assume that
-$v_{i}=\left[ v_{L},v_{H}%
-\right] $. $c_{s},c_{h}\left( n_{s}\right) ,c_{n}$ are the costs of
-sending a message through the mix-net system, acting as node when
-there are $n$ agents sending messages, and sending messages through a
-non anonymous system respectively. Given that the strategy space
-discussed in this section is only composed of 3 possible actions (only
-send her own messages through the mix-net, $a_{s}$, or send her
-messages but also act as node forwarding other users' messages,
-$a_{h}$, or send a message without using the mix-net, $a_{n} $), it
-must compare the disutility coming from those three actions:
+Nonetheless, it should be clear that there is a large potential gain from
+running one's own node. $v_{i}$ is the disutility an agent derives from its
+message being exposed; we assume that $v_{i}=\left[ v_{L},v_{H}\right] $. $%
+c_{s},c_{h}\left( n_{s}\right) ,c_{n}$ are the costs of sending a message
+through the mix-net system, acting as node when there are $n$ agents sending
+messages, and sending messages through a non anonymous system respectively.
+Given that the strategy space discussed in this section is only composed of
+3 possible actions (only send her own messages through the mix-net, $a_{s}$,
+or send her messages but also act as node forwarding other users' messages, $%
+a_{h}$, or send a message without using the mix-net, $a_{n} $), it must
+compare the disutility coming from those three actions:
\begin{equation*}
\begin{tabular}{cc}
@@ -514,139 +513,213 @@
\end{tabular}
\end{equation*}
-which means, for example, that when $-v_{H,L}\left( 1-p_{a}\left(
- n_{s},n_{h},d_{i}\right) \right) -c_{s}-c_{h}\left( n_{s}\right)
-<\left[
--v_{H,L}\left( 1-p_{a}\left( n_{s},n_{h}\right) \right) -c_{s},-v_{H,L}-c_{n}%
-\right] $, the agents will choose to become a node in the mix-net.
-Note that we do not allow the agent to choose not to send a message at
-all, which would of course mimize the risk of anonymity compromise.
-Rather, she can only choose amongst the three given actions. Note also
-that since message delivery is guaranteed, a node might always choose
-a longer route to reduce risk. We could assign a higher $c_s$ to
-longer routes to reflect the cost, e.g., of additional delay; however,
-to keep things simple, we assume that all messages pass through the
-mix-net system in fixed length free routes.
+Note that we do not allow the agent to choose not to send a message at all,
+which would of course mimize the risk of anonymity compromise. Rather, she
+can only choose amongst the three given actions. Note also that since
+message delivery is guaranteed, a node might always choose a longer route to
+reduce risk. We could assign a higher $c_{s}$ to longer routes to reflect
+the cost, e.g., of additional delay; however, to keep things simple, we
+assume that all messages pass through the mix-net system in fixed length
+free routes.
-Can this be represented in a game theoretical matrix form? -
-\textit{such as, for example}:
+We consider various versions of this model, in increasing order of realism.
+
+\subsubsection{Myopic Agents}
+
+Myopic agents do not take into consideration the strategic consequences of
+their action. They simply consider the status of the network and, depending
+on the payoffs, adopt a certain strategy. Imagine a $v_{H}$ type that is
+considering to use a mix-net where currently $n_{s}=\bar{n}_{s}$ and $n_{h}=%
+\bar{n}_{h}$, that is, there are already $\bar{n}_{s}$ users and $\bar{n}_{h}
+$ nodes. Then if $-v_{H}\left( 1-p_{a}\left( \bar{n}_{s},\left( \bar{n}%
+_{h}+1\right) ,d\right) \right) -c_{s}-c_{h}\left( \bar{n}_{s}\right)
+<-v_{H,L}\left( 1-p_{a}\left( \bar{n}_{s},\bar{n}_{h}\right) \right) -c_{s}$
+and $-v_{H}\left( 1-p_{a}\left( \bar{n}_{s},\left( \bar{n}_{h}+1\right)
+,d\right) \right) -c_{s}-c_{h}\left( \bar{n}_{s}\right) <-v_{H}-c_{n}$ then
+the high type will choose to become a node in the mix-net.
+
+\subsubsection{Strategic Agents: Simple Case}
+
+Consider now the interaction between two agents. One is an high type. The
+other could be and high or a low type. Initially we study the case where
+each agent knows the other agent's type, but we then extend this case to
+study what happens when there is uncertainty about the other agents' types.
+The interactions we have in mix-net systems obviously involve a much larger
+number of players, but the following analysis can give us a taste of the
+issues to be considered when strategic agents are interacting. Following
+Palfrey and Rosenthal (1989, ``Underestimated Probabilities that Others Free
+Ride:\ An Experimental Test'', mimeo, California Institute of Technology and
+Carnegie-Mellon University) we can set up a payoff matrix to study these
+cases.
\begin{equation*}
\begin{tabular}{cccc}
-Player 1/All other players & $a_{s}$ & $a_{h}$ & $a_{n}$ \\
-$a_{s}$ & payoff player 1, payoff other player & ... & ... \\
+H type/L type & $a_{s}$ & $a_{h}$ & $a_{n}$ \\
+$a_{s}$ & [...to be completed] & ... & ... \\
+$a_{h}$ & ... & ... & ... \\
+$a_{n}$ & $-v_{H}-c_{n},-v_{L}\left( 1-p_{a}\left( n_{s},n_{h}\right)
+\right) -c_{s}$ & $-v_{H}-c_{n},-v_{L}\left( 1-p_{a}\left(
+n_{s},n_{h},d_{i}\right) \right) -c_{s}-c_{h}\left( n_{s}\right) $ & $%
+-v_{L}-c_{n},-v_{L}-c_{n}$%
+\end{tabular}
+\end{equation*}
+
+\begin{equation*}
+\begin{tabular}{cccc}
+H type/H type & $a_{s}$ & $a_{h}$ & $a_{n}$ \\
+$a_{s}$ & ... & ... & ... \\
$a_{h}$ & ... & ... & ... \\
$a_{n}$ & ... & ... & ...
\end{tabular}
\end{equation*}
-The problem in representing the above problem is that each agent is
-playing with a large, but not infinite number of other players.
-Fudenberg and Levine \cite{fudenberg88} have a model where each player
-plays a set of identical player each of which is ``infinitesimal'',
-i.e. its actions cannot affect the payoff of the first player - and it
-is already a very complicated model indeed. In this setup what we want
-to study is, instead, the concatenated interactions in a large but not
-infinite set of players, which are not identical (we are considering
-two types).
-The goal here is to study what dynamics arise as the agents are faced
-with the various choices in a repeated-game setup. Imagine such
-repeated setup and the high sensitivity agents start by collaborating,
-i.e. acting as nodes. ``Defection'' would be, for example, acting as
-user only and refusing to be a node. This would happen because the
-agents start realizing that there is enough anonymity in the system
-and they do not need to be a node any longer. But if too many agents
-act this way, the system might break down for lack of nodes, after
-which everybody would have to resort to non anonymous channels. Can
-there be equilibria where the high sensitivity keep on acting as nodes
-and the low sensitivity keep on using the system? There might be,
-possibly in 3 scenarios:
+alessandrocomment\{What we can show with these tables
+are simple solutions where in some cases both parties cooperate, in other
+cases only one party will act as node. I have some preliminary solutions and
+will update these tables shortly. The point here is that when the actions
+are observable it is possible to sustain cooperative solutions where for
+example both H types acts nodes if there are ``trigger'' strategies, i.e.
+appropriate punishments which in this case can be interpreted as the
+complete absence of an anonymizing tool.\}
+
+\subsubsection{Strategic Agents in a Multi-agent Environment}
+
+We now extend the analysis to many players. Fudenberg and Levine \cite
+{fudenberg88} have a model where each player plays a set of identical player
+each of which is ``infinitesimal'', i.e. its actions cannot affect the
+payoff of the first player. In this setup what we want to study is, instead,
+the concatenated interactions in a large but not infinite set of players.
+The approach on this case is to define the payoff of each player as the
+average of his payoffs against the distribution of strategies played by the
+continuum of the other players. In other words, for the high type, we will
+have: $u_{H}=\sum_{n_{s}}u_{H}\left( s_{H},s_{-H}\right) $ where the
+notation represents the comparison between one specific $H$ type and all the
+others. We can assume that the L agents will simply participate sending
+traffic if the system is cheap enough for them to use, and we can also
+assume that this will not pose any problem to the H type, which in fact has
+an interesting in having more traffic. This allows us to re-use the matrixes
+above to represent the interaction between each H type and the others:
+\begin{equation*}
+\begin{tabular}{cccc}
+H player/All other H players & $a_{s}$ & $a_{h}$ & $a_{n}$ \\
+$a_{s}$ & ... & ... & ... \\
+$a_{h}$ & ... & ... & ... \\
+$a_{n}$ & ... & ... & ...
+\end{tabular}
+\end{equation*}
+
+Traditionally, cooperative solutions in non infinite horizon are not
+sustainable because, by backward induction, each agent will have an
+incentive to deviate when the actions of other agents are not observable. As
+compared to the analysis above with only two agents, now a defection of one
+agent might affect only infinitesimally the payoff of the other agents, so
+the agents might tend not to use the trigger strategy. But then, more agents
+will tend to deviate and the cooperative equilibrium might collapse.%
+\footnote{%
+``Defection'' would be, for example, acting as user only and refusing to be
+a node. This would happen because the agents start realizing that there is
+enough anonymity in the system and they do not need to be a node any longer.
+But if too many agents act this way, the system might break down for lack of
+nodes, after which everybody would have to resort to non anonymous channels.
+A trigger strategy would punish an agent by making the system unavailable.
+Of course an H type will also suffer itself because of this strategy
+[[extend on this]]} Under which conditions this will not happen?
+
+Well, if $-v_{L}-c_{n}$ is particularly high, i.e. if the cost of non having
+anonymity is very high for each H type, then each H type might tend to act
+as node regardless of what the others do [[extend on this]]. Also, if there
+are enough low types, again an high type might have an interest in acting
+alone is its costs of non having anonymity would be too high compared to the
+costs of handling the traffic more L types [[extend on this]].
+
+paulcomment\{Can't there be an equilibrium in which
+the enhanced
+
+anonymity of running your own node will mean that ``high'' agents
+
+will want to do so, even if all the other high agents already do.
+
+That strikes me as a natural possibility depending on the initial
+
+conditions and other assumptions. Also, in this case the
+
+assumption that agent type is known goes away.\}
+
+Otherwise:
\begin{enumerate}
-\item Simply out of the analysis of the game as it is, some
- cooperative equilibria are enforceable even in non infinite horizons
- when the actions of the players are detectable: in these cases the
- strategy spaces for the ``high'' agents will be something like,
- cooperate until everybody cooperates (i.e., act as node), then
- defect forever (i.e., do not use the system). This might be
- enforceable especially if the trigger strategy is particularly
- painful (in other words, if the players \textit{really} need some
- form of anonymous channel). The problem however is that this also
- might strongly rely on the fact that the type of the agent must be
- known, i.e. the agents cannot misrepresent themselves (maybe not,
- but this has to be studied).
+\item In the scenario where the mix-net system is self-sustaining and free,
+i.e. the nodes act because of their own interest in having an anonymous
+system, we have a classic public good with free riding case. Then the agents
+should agree on reacting together to a deviation of a marginal player, thus
+re-stablishing the trigger strategy of the 2-agents case. [[I have a
+solution for this which I will write, but the issue is: how realistic can
+this be in a real application?]]
-
- \paulcomment{Can't there be an equilibrium in which the enhanced
- anonymity of running your own node will mean that ``high'' agents
- will want to do so, even if all the other high agents already do.
- That strikes me as a natural possibility depending on the initial
- conditions and other assumptions. Also, in this case the
- assumption that agent type is known goes away.}
+\item In a scenario where each participating to the system actually has to
+pay, then we are in a ``clubs'' scenario. Hence we can elanborate a pricing mechanism related to how much the
+agent will use the system (traffic) or how much sensitivity it is (which
+involves mechanism design and revelation mechanism). Consider for example
+anonymizer, where the system is offered at low costs to L types (there is a
+cost in the delay and hassles of using the basic service), and is offered
+for a premium to the others.
+\item Having a ``special agent'' whose utility function has been modified
+to consider the social value of having an anonymous system, or which is
+being paid for or supported to provide such service (this, however,
+practically brings the analysis back to square one, as again the high type
+might decide to rely only on the special agent and not provide their
+services as nodes).
-\item Having a ``special agent'' whose utility function has been
- modified to consider the social value of having an anonymous system,
- or which is being paid for or supported to provide such service
- (this, however, practically brings the analysis back to square one,
- as again the high type might decide to rely only on the special
- agent and not provide their services as nodes).
+\item Bilateral contracts (see also below, ``Extensions'') between agents
+to agree on cooperation and punishments for breaching cooperation.
-\item Bilateral contracts (see also below, ``Extensions'') between
- agents to agree on cooperation and punishments for breaching
- cooperation.
-
-\item Reputation: We already had a bunch of stuff about reputation in
- the paper that prompted this work. We should mine that for here. It
- can play a role in various forms
+\item Reputation: We already had a bunch of stuff about reputation in the
+paper that prompted this work. We should mine that for here. It can play a
+role in various forms
- \begin{itemize}
- \item mojonation: fill in the details
-
- \item high performing high volume ``high'' nodes can attract more
- traffic, get more cover for their highly sensitive anonymous
- communication
-
- \item related to the ``special agent'' above. Some nodes will attach
- a value to having good mix-nets available. Altruistic self interest
- or some such. They want the world to be a better place. We
- shouldn't ignore that as a factor in such things. Similarly, one
- could imagine government services for same (even if most of the
- current community can't imagine such a thing ;-)
+\begin{itemize}
+\item mojonation: fill in the details
- \end{itemize}
+\item high performing high volume ``high'' nodes can attract more traffic,
+get more cover for their highly sensitive anonymous communication
+\item related to the ``special agent'' above. Some nodes will attach a
+value to having good mix-nets available. Altruistic self interest or some
+such. They want the world to be a better place. We shouldn't ignore that as
+a factor in such things. Similarly, one could imagine government services
+for same (even if most of the current community can't imagine such a thing
+;-)
+\end{itemize}
\end{enumerate}
\section{Extensions}
\begin{itemize}
-
-\item Dummy traffic increases costs but it also increases anonymity.
- Here we can study bilateral or multilateral contracts between
- agents, forcing contractually each agent to send to another agent(s)
- a certain number of messages in each period - this means that if the
- sending agent has not enough real messages going through its node,
- it will have to generate them as dummy traffic.
-
-\item Assume strategic bad node can exist: reliability goes down, and
- anonymity goes down.
-
-\item The type of the agent is not know (i.e., there is a certain
- probability it is an high sensitivity vs. a low sensitivity type).
-
-\item Compare mix-net system to other systems.
-
-\item Consider costs of being exit nodes.
-
-\item The ``application'' considered in the previous section and the
- above ``extensions'' might be studied in an agent-based simulation
- framework, where a certain number of agents of the various types
- (high sensitivity, low sensitivity, etc.) might be created and then
- ``launched'' onto the mix-net arena with a set of predefined
- strategies (e.g., always cooperate, always defect, tit-for-tat,
- etc.). Similar agent-based studies have been done in economics to
- study, for example, Hal Varian's model of sales.
+\item Dummy traffic increases costs but it also increases anonymity. Here
+we can study bilateral or multilateral contracts between agents, forcing
+contractually each agent to send to another agent(s) a certain number of
+messages in each period - this means that if the sending agent has not
+enough real messages going through its node, it will have to generate them
+as dummy traffic.
+
+\item Assume strategic bad node can exist: reliability goes down, and
+anonymity goes down.
+
+\item The type of the agent is not know (i.e., there is a certain
+probability it is an high sensitivity vs. a low sensitivity type).
+
+\item Compare mix-net system to other systems.
+
+\item Consider costs of being exit nodes.
+
+\item The ``application'' considered in the previous section and the above
+``extensions'' might be studied in an agent-based simulation framework,
+where a certain number of agents of the various types (high sensitivity,
+low sensitivity, etc.) might be created and then ``launched'' onto the
+mix-net arena with a set of predefined strategies (e.g., always cooperate,
+always defect, tit-for-tat, etc.). Similar agent-based studies have been
+done in economics to study, for example, Hal Varian's model of sales.
\end{itemize}
\bibliographystyle{alpha}
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/