[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[freehaven-cvs] fixing up the tables so they"re legible
Update of /home/freehaven/cvsroot/doc/fc03
In directory moria.seul.org:/home/arma/work/freehaven/doc/fc03
Modified Files:
econymics.tex
Log Message:
fixing up the tables so they're legible
Index: econymics.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/fc03/econymics.tex,v
retrieving revision 1.18
retrieving revision 1.19
diff -u -d -r1.18 -r1.19
--- econymics.tex 16 Sep 2002 02:34:12 -0000 1.18
+++ econymics.tex 16 Sep 2002 04:50:08 -0000 1.19
@@ -219,8 +219,8 @@
value anonymity differently.
The strategy space $S$ for each agent $i$ $\in I$ (where $I=\left\{
-1 \dots n\right\}$) willing to use the mix-net is the set of strategies $s$
-based on the following feasible actions $a$:
+1 \dots n\right\}$) willing to use the mix-net is the set of strategies
+$s$ based on the following feasible actions $a$:
\begin{enumerate}
\item Act simply as a user of the system, $a^s$, specifically by sending
@@ -250,15 +250,15 @@
of the subjective evaluation the agent places on 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}$ (the probability that sender and
-message will remain anonymous); and the perceived level of reliability in
-the system, $p_{r}$ (the probability that the message will be
-delivered). The subjective value of the information being sent anonymously
-can be related to the profits the agent expects to make by keeping that
-information anonymous, or the losses the agents expects to avoid by keeping
-that information anonymous. We represent the level of anonymity in the
-system as a function of the traffic (number of agents sending messages in
-the system, $n_{s}$), the number of mixes (number of agents acting as honest
+anonymity in the system, $p_{a}$ (the probability that sender and message
+will remain anonymous); and the perceived level of reliability in the
+system, $p_{r}$ (the probability that the message will be delivered). The
+subjective value of the information being sent anonymously can be related
+to the profits the agent expects to make by keeping that information
+anonymous, or the losses the agents expects to avoid by keeping that
+information anonymous. We represent the level of anonymity in the system
+as a function of the traffic (number of agents sending messages in the
+system, $n_{s}$), the number of mixes (number of agents acting as honest
nodes, $n_{h}$ and as dishonest nodes, $n_{d}$), and the decisions of the
agent. We assume that this function maps these factors into a probability
space, $p$.\footnote{%
@@ -277,20 +277,20 @@
assumption that the honest node is interested in its own anonymity) is
strongly positively correlated to preserving the anonymity of one's
information. For example, suppose agents send
-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
+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 which case the sender uses his own node first
and chooses the next two at random. If an agent does not run a node,
the probability 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 batch 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) only to $50$. And
-the probability of even doing that is the probability that all of the
-messages from the relevant batch pass only through bad nodes on the
-remaining two hops: $10^{-100}$. If we pessimistically equate the
+of a message that exits the mix network is $.001$. If an agent runs
+a mix node with batch 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) only to
+$50$. And the probability of even doing that is the probability that all
+of the messages from the relevant batch pass only through bad nodes on
+the remaining two hops: $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 achieved by running one's own
node here is $2\times 10^{99}$.\footnote{%
@@ -332,17 +332,15 @@
\item sending messages:
\begin{itemize}
-\item through the mix-net system, $c_{s}$. This cost includes both
-direct financial costs such as usage fees, as well as implicit costs
-such as the time to build an anonymous message, learning curve to get
-familiar with the system, and delays incurred when using the system.
-These delays should be positively correlated to the traffic $n_{s}$ and
-negatively correlated to the number of nodes $n_{h}$.
-% FIXME is this right? -RD
-In addition, when
-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 of additional delay.
+\item through the mix-net system, $c_{s}$. This cost includes both direct
+financial costs such as usage fees, as well as implicit costs such as the
+time to build an anonymous message, learning curve to get familiar with the
+system, and delays incurred when using the system. These delays should be
+positively correlated to the traffic $n_{s}$ and negatively correlated to
+the number of nodes $n_{h}$. % FIXME is this right? -RD
+In addition, when 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 of additional delay.
\item or through a conventional non-anonymous system, $c_{n}$.
@@ -364,78 +362,96 @@
dishonest node carries a monetary penalty).
\end{enumerate}
-In addition to the above costs and benefits, there might also be
-\emph{reputation} costs and benefits from 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 messages themselves do
-remain anonymous), acting as a perceivably honest node (e.g., there can
-be a reputation benefit by acting as a reliable node), or acting as a
-perceivably dishonest node (e.g., there can be a reputation cost by being
-exposed as a dishonest node; the costs here will also be a function of
-the probability of being exposed as a bad node).
+In addition to the above costs and benefits, there might also be \emph{%
+reputation} costs and benefits from 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 messages themselves do remain anonymous), acting as
+a perceivably honest node (e.g., there can be a reputation benefit by acting
+as a reliable node), or acting as a perceivably dishonest node (e.g., there
+can be a reputation cost by being exposed as a dishonest node; the costs
+here will also be a function of the probability of being exposed as a bad
+node).
-These reputation costs and benefits can be considered ``internal''
-to the system (for example, 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). Thus they do not enter directly the utility
-functions of the agents, but rather enter indirectly through the changes
-they provoke in the behavior of the agents.
+These reputation costs and benefits can be considered ``internal'' to the
+system (for example, 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). Thus they do not enter directly the utility functions of the
+agents, but rather enter indirectly through the changes they provoke in the
+behavior of the agents.
-We assume that agents want to maximize their expected utility, which is
-a function of expected benefits minus expected costs. We represent the payoff
+We assume that agents want to maximize their expected utility, which is a
+function of expected benefits minus expected costs. We represent the payoff
function for each agent $i$ in the following compact form:
\begin{equation*}
-u_{i}=u\left( \theta \left[ \gamma \left( v_{r},p_{r}\left(
-n_{h},n_{d}\right) \right) ,\partial \left( v_{a},p_{a}\left(
-n_{s},n_{h},n_{d},a_{i}^{s}\right) \right) ,a_{i}^{s}\right]
-+b_{h}a_{i}^{h}+b_{h}a_{i}^{d}-c_{s}\left( n_{s},n_{h}\right)
+u_{i}=u\left(
+\begin{array}{c}
+\theta \left[ \gamma \left( v_{r},p_{r}\left( n_{h},n_{d}\right) \right)
+,\partial \left( v_{a},p_{a}\left( n_{s},n_{h},n_{d},a_{i}^{s}\right)
+\right) ,a_{i}^{s}\right] + \\
+b_{h}a_{i}^{h}+b_{h}a_{i}^{d}-c_{s}\left( n_{s},n_{h}\right)
a_{i}^{s}-c_{h}\left( n_{s},n_{h},n_{d}\right) a_{i}^{h}-c_{d}\left(
-..\right) a_{i}^{d}-c_{r}\left( ..\right) a_{i}^{r}-c_{n}\right)
+..\right) a_{i}^{d}-c_{r}\left( ..\right) a_{i}^{r}-c_{n}
+\end{array}
+\right)
\end{equation*}
where $u, \theta, \gamma$, and $\partial$ are unspecified functional forms.
The payoff function $u$ includes the costs and benefits for all the possible
-actions of the agents, including \textit{not} using the mix-net and
-instead sending the messages through a non-anonymous channel. We can
-represent these actions with dummy variables $a_{i}$.\footnote{%
-For example, if the agent chooses not to send the message
-anonymously, the probability of remaining anonymous $p_{a}$ will be equal
-to zero, $a^{s,d,r,h}$ will be zero too, and the only cost in the function
-will be $c_{n}$.} Note that $\gamma $ and $\partial$ describe
-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 agents might value anonymity and
-reliability differently,%\footnote{%
+actions of the agents, including \textit{not} using the mix-net and instead
+sending the messages through a non-anonymous channel. We can represent these
+actions with dummy variables $a_{i}$.\footnote{%
+For example, if the agent chooses not to send the message anonymously, the
+probability of remaining anonymous $p_{a}$ will be equal to zero, $%
+a^{s,d,r,h}$ will be zero too, and the only cost in the function will be $%
+c_{n}$.} Note that $\gamma $ and $\partial$ describe 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
+agents might value anonymity and reliability differently,%\footnote{%
%In other words, even if agents agree on metrics for reliability and
%anonymity, some might care more about anonymity than
%reliability, some vice versa.}
-and because in different scenarios anonymity
-and reliability for the same agent might have different impacts on her
-payoff.
+and because in different scenarios anonymity and reliability for the same
+agent might have different impacts on her payoff.
-While messages might be sent anonymously to avoid costs or to gain
-profits, the costs and benefits from sending the message might be
-distinct from the costs and benefits from keeping the \emph{information}
-anonymous. For example, when Alice anonymously contacts a merchant
-to purchase a book, she will gain a profit equal to the difference
-between her valuation of the good and its price. But if her anonymity
-is compromised during the process, she will incur losses completely
-independent from the price of the book or her valuation of it. The payoff
-function $u_{i}$ above allows us to represent the duality implicit in
-all privacy issues, as well as the distinction between the value of
-sending a message and the value of keeping it anonymous:
+While messages might be sent anonymously to avoid costs or to gain profits,
+the costs and benefits from sending the message might be distinct from the
+costs and benefits from keeping the \emph{information} anonymous. For
+example, when Alice anonymously contacts a merchant to purchase a book, she
+will gain a profit equal to the difference between her valuation of the good
+and its price. But if her anonymity is compromised during the process, she
+will incur losses completely independent from the price of the book or her
+valuation of it. The payoff function $u_{i}$ above allows us to represent
+the duality implicit in all privacy issues, as well as the distinction
+between the value of sending a message and the value of keeping it anonymous:
\begin{equation*}
-\begin{tabular}{cc}
-\textit{Anonymity} & \textit{Reliability} \\
-benefits from remaining anonymous / costs avoided remaining anonymous, or &
-benefits from sending a message which will be received / costs avoided
-sending a message, or \\
-costs due to loosing anonymity / profits missed because of loss of anonymity
-& costs due to not having sent a message / profits missed because of not
-having sent a message
+\begin{tabular}{|c|c|}
+\hline
+\textit{Anonymity} & \textit{Reliability} \\ \hline
+{\tiny \
+\begin{tabular}{c}
+{\tiny Benefits from remaining anonymous /} \\
+{\tiny costs avoided remaining anonymous, or}
+\end{tabular}
+} & {\tiny
+\begin{tabular}{c}
+{\tiny Benefits from sending a message which will be received /} \\
+{\tiny costs avoided sending a message, or}
+\end{tabular}
+} \\ \hline
+{\tiny \
+\begin{tabular}{c}
+{\tiny Costs due to loosing anonymity /} \\
+{\tiny \ profits missed because of loss of anonymity}
+\end{tabular}
+} & {\tiny
+\begin{tabular}{c}
+{\tiny Costs due to not having sent a message /} \\
+{\tiny \ profits missed because of not having sent a message}
+\end{tabular}
+} \\ \hline
\end{tabular}
\end{equation*}
@@ -443,7 +459,7 @@
message (in order to gain profits or avoid losses) as well as to keep it
anonymous. We also always consider the direct benefits or losses rather than
their dual opportunity costs or avoided costs. Nevertheless, the above
-representation allows us to formalize the various possible combinations.
+representation allows us to formalize the various possible combinations.
For example, if the message is sent to gain some benefit but anonymity must
be protected in order to avoid losses, then $v_{r}$ will be positive while $%
@@ -459,7 +475,7 @@
In such scenario, the certainty of sending a message that will be received
will eliminate the risk of losing $v_{r}$, while the certainty of not being
able to send a deliverable message will impose on the agent the full cost $%
-v_{r}$.}
+v_{r}$.}
With this framework we are able to compare - for example - the losses due to
compromised anonymity to the costs of protecting it. An agent will decide to
@@ -471,81 +487,79 @@
\label{sec:application}
-In this section we apply the above framework to simple scenarios. We make
-a number of assumptions to let us model the behavior of the participants
-as players in a repeated-game, simultaneous-move game theoretical
-framework. Thus we are able to analyze the economic justifications for
-the various choices of the participants, and compare design approaches
-to mix-net systems.
+In this section we apply the above framework to simple scenarios. We make a
+number of assumptions to let us model the behavior of the participants as
+players in a repeated-game, simultaneous-move game theoretical framework.
+Thus we are able to analyze the economic justifications for the various
+choices of the participants, and compare design approaches to mix-net
+systems.
Consider a set of $n_{s}$ agents interested in sending anonymous
communications. Imagine that there is only one system which can be used to
send anonymous messages, and one other system to send non-anonymous
messages. Each user has three options: only send her own messages through
-the mix-net; send her messages but also act as a node forwarding
-messages from other users; or not use the system at all (by sending a message
-without using the mix-net, or by not sending the message at all). Thus
-initially we do not consider the strategy of choosing to be a bad node
-or additional honest strategies like creating and receiving dummy traffic.
-We represent the game as a simultaneous-move, repeated-game because the
-large number of participants, plus the fact that earlier actions indicate
-only a weak commitment to future actions,
+the mix-net; send her messages but also act as a node forwarding messages
+from other users; or not use the system at all (by sending a message without
+using the mix-net, or by not sending the message at all). Thus initially we
+do not consider the strategy of choosing to be a bad node or additional
+honest strategies like creating and receiving dummy traffic. We represent
+the game as a simultaneous-move, repeated-game because the large number of
+participants, plus the fact that earlier actions indicate only a weak
+commitment to future actions,
% did my changes just make this statement incorrect?
-suggest against using a sequential approach \textit{a la }
-Stackleberg.
+suggest against using a sequential approach \textit{a la } Stackleberg.
%cite?
-With a large group size there might be no discernable nor
-agreeable order for the actions of all participants, so actions can be
-considered simultaneous. The limited commitment produced by earlier actions
-allow us to consider a repeated-game scenario. We also imagine that the need
-to send a message at each period is high enough that a ``war of attrition''
-framework is not applicable.
+With a large group size there might be no discernable nor agreeable order
+for the actions of all participants, so actions can be considered
+simultaneous. The limited commitment produced by earlier actions allow us to
+consider a repeated-game scenario. We also imagine that the need to send a
+message at each period is high enough that a ``war of attrition'' framework
+is not applicable.
\subsection{Adversary}
-Strategic agents cannot choose to be bad nodes in this simplified
-scenario. But we do assume there is 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, we also study the case when the adversary
-includes some percentage of mix-nodes. In choosing strategies agents will
-attach a subjective probability to arbitrary nodes being compromised ---
-all nodes not run by the agent are assigned the same probability of being
-compromised. This factor influences their assessment 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}). 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 nodes and links never selectively trickle or flood messages
-\cite{trickle02}. Nonetheless, a \emph{global} passive adversary is still
-quite strong, and thus a typical starting point of anonymity analyses.
+Strategic agents cannot choose to be bad nodes in this simplified scenario.
+But we do assume there is 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, we also
+study the case when the adversary includes some percentage of mix-nodes. In
+choosing strategies agents will attach a subjective probability to arbitrary
+nodes being compromised --- all nodes not run by the agent are assigned the
+same probability of being compromised. This factor influences their
+assessment 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}). 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 nodes and links never selectively
+trickle or flood messages \cite{trickle02}. Nonetheless, a \emph{global}
+passive adversary is still quite strong, and thus a typical starting point
+of anonymity analyses.
\subsection{Honest agents}
If a user only sends her messages, the cost of using the anonymous service
-is $c_{s}$. This cost might be higher than using the non anonymous channel,
-$c_{n}$, because of usage fees, usage hassles, or delays.
-To keep things simple, we assume that all messages pass
-through the mix-net system in fixed length free routes, so that we can write
-$c_{s}$ as a fixed value, the same for all agents. Users send messages at
-the same time, and only one message at a time. We also assume that routes
-are chosen randomly by users, so that traffic is uniformly distributed among
-the nodes. If a user decides to be a node, costs increase with the traffic,
-as described in the Section above. For nodes we concentrate on the
-traffic-based variable costs. Given that there are no active bad nodes
-(our adversary is restricted to watching messages), reliability
-is deterministically complete ($p_{r}=1$). 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 initially assume that the type of an agent is publicly known (i.e. a high
-sensitivity type cannot pretend to be a low type). We later relax this
-assumption. We also assume that all agents perceive the
-level of anonymity in the system (based on traffic and number of nodes)
-the same way. Further, we imagine that both
-agent types use the system because they want to avoid potential losses from
-not being anonymous. This sensitivity to anonymity can be represented with
-the variable $v_{i}$, which we treat as uniformly distributed between 0 and 1.
+is $c_{s}$. This cost might be higher than using the non anonymous channel, $%
+c_{n}$, because of usage fees, usage hassles, or delays. To keep things
+simple, we assume that all messages pass through the mix-net system in fixed
+length free routes, so that we can write $c_{s}$ as a fixed value, the same
+for all agents. Users send messages at the same time, and only one message
+at a time. We also assume that routes are chosen randomly by users, so that
+traffic is uniformly distributed among the nodes. If a user decides to be a
+node, costs increase with the traffic, as described in the Section above.
+For nodes we concentrate on the traffic-based variable costs. Given that
+there are no active bad nodes (our adversary is restricted to watching
+messages), reliability is deterministically complete ($p_{r}=1$). 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 initially assume that the type of an agent is
+publicly known (i.e. a high sensitivity type cannot pretend to be a low
+type). We later relax this assumption. We also assume that all agents
+perceive the level of anonymity in the system (based on traffic and number
+of nodes) the same way. Further, we imagine that both agent types use the
+system because they want to avoid potential losses from not being anonymous.
+This sensitivity to anonymity can be represented with the variable $v_{i}$,
+which we treat as uniformly distributed between 0 and 1.
These assumptions let us reformulate the framework above in a simpler way.
The utility function can be re-written as:
@@ -555,21 +569,19 @@
-c_{s}a_{i}^{s}-c_{h}\left( n_{s},n_{h},n_{d}\right) a_{i}^{h}-c_{n}
\end{equation*}
-This function reads as follows: each agent $i$ tries to
-\textit{minimize} the costs of sending messages and the risk of being
-tracked. $1-p_{a}\left( n_{s},n_{h},n_{d},a_{i}^{h}\right) $ is the
-probability that the anonymity will be lost given the number of agents
-sending messages, the number of them acting as honest and dishonest nodes,
-and the action $a$ of agent $i$ itself. $v_{i}$ is the disutility an agent
-derives from its message being exposed, assumed to be a continuous variable $%
-v_{i}=\left[ \text{\b{v}},\bar{v}\right] $. $c_{s},c_{h}\left(
-n_{s},n_{h}\right) ,$ and $c_{n}$ are the costs of sending a message through
-the mix-net system, acting as a node when there are $n_{s}$ agents sending
-messages over $n_{h}$ and $n_{d}$ nodes, and sending messages through
-a non-anonymous system, respectively. Each period, the rational agent
-can compare
-the disutility coming from each of these three one-period strategies.
-%: only send her own
+This function reads as follows: each agent $i$ tries to \textit{minimize}
+the costs of sending messages and the risk of being tracked. $1-p_{a}\left(
+n_{s},n_{h},n_{d},a_{i}^{h}\right) $ is the probability that the anonymity
+will be lost given the number of agents sending messages, the number of them
+acting as honest and dishonest nodes, and the action $a$ of agent $i$
+itself. $v_{i}$ is the disutility an agent derives from its message being
+exposed, assumed to be a continuous variable $v_{i}=\left[ \text{\b{v}},\bar{%
+v}\right] $. $c_{s},c_{h}\left( n_{s},n_{h}\right) ,$ and $c_{n}$ are the
+costs of sending a message through the mix-net system, acting as a node when
+there are $n_{s}$ agents sending messages over $n_{h}$ and $n_{d}$ nodes,
+and sending messages through a non-anonymous system, respectively. Each
+period, the rational agent can compare the disutility coming from each of
+these three one-period strategies. %: 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}$.
@@ -577,36 +589,35 @@
\begin{equation*}
\begin{tabular}{cc}
Action & Payoff \\
-$a_{s}$ & $-v_{i}\left( 1-p_{a}\left( n_{s},n_{h},n_{d}\right) \right) -c_{s}
-$ \\
+$a_{s}$ & $-v_{i}\left( 1-p_{a}\left( n_{s},n_{h},n_{d}\right) \right)
+-c_{s} $ \\
$a_{h}$ & $-v_{i}\left( 1-p_{a}\left( n_{s},n_{h},n_{d},a_{i}^{h}\right)
\right) -c_{s}-c_{h}\left( n_{s},n_{h},n_{d}\right) $ \\
$a_{n}$ & $-v_{i}-c_{n}$%
\end{tabular}
\end{equation*}
-We do not explicitly allow the agent to choose \textit{not} to
-send a message at all, which would of course minimize the risk of anonymity
+We do not explicitly allow the agent to choose \textit{not} to send a
+message at all, which would of course minimize the risk of anonymity
compromise. %Rather, she can only choose amongst the three given actions.
-Also, we
-do not explicitly report the value of sending a successful message. Both are
-simplifications that do not alter the rest of the analysis. We could in fact
-have inserted an action $a^{0}$ with a certain disutility from not sending
-any message, and solve the problem of minimizing the expected losses; or, we
-could have inserted in the payoff function for actions $a^{s,h,n}$ also the
-utility of sending a succesful message compared to not sending it (which
-could be interpreted also as an opportunity cost), and solve the dual
-problem of maximizing the expected utility. Either way, the ``exit''
-strategy for each agent will either be sending a message non-anonymously, or
-not sending it at all, depending on which option maximizes the expected
-benefits or minimizes the expected losses. Thereafter, we can simply compare
-the two other actions (being a user, or being also a node) to the locally
-optimal exit strategy.\footnote{%
-For example, sending an anonymous message might be so expensive, and sending it
-through a non anonymous channel so potentially costly, that the user might
-prefer not to send a message at all. We discuss again some more general
-issues related to this point in one of the later sections [[add reference
-here]].}
+Also, we do not explicitly report the value of sending a successful message.
+Both are simplifications that do not alter the rest of the analysis. We
+could in fact have inserted an action $a^{0}$ with a certain disutility from
+not sending any message, and solve the problem of minimizing the expected
+losses; or, we could have inserted in the payoff function for actions $%
+a^{s,h,n}$ also the utility of sending a succesful message compared to not
+sending it (which could be interpreted also as an opportunity cost), and
+solve the dual problem of maximizing the expected utility. Either way, the
+``exit'' strategy for each agent will either be sending a message
+non-anonymously, or not sending it at all, depending on which option
+maximizes the expected benefits or minimizes the expected losses.
+Thereafter, we can simply compare the two other actions (being a user, or
+being also a node) to the locally optimal exit strategy.\footnote{%
+For example, sending an anonymous message might be so expensive, and sending
+it through a non anonymous channel so potentially costly, that the user
+might prefer not to send a message at all. We discuss again some more
+general issues related to this point in one of the later sections [[add
+reference here]].}
%[[Go back to this in later sections, discuss the ``why bother having anonymity'' question.]]
We now consider various versions of this model with increasing details.
@@ -615,41 +626,58 @@
Myopic agents do not take into consideration the strategic consequences of
their actions. They simply consider the status of the network and, depending
-on the payoffs of the one-period game, adopt a certain strategy.
-Imagine a new agent with a privacy
-sensitivity $v_{i}$ is considering using 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.
+on the payoffs of the one-period game, adopt a certain strategy. Imagine a
+new agent with a privacy sensitivity $v_{i}$ is considering using 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_{i}\left( 1-p_{a}\left( \bar{n}_{s}+1,\bar{n}%
-_{h}+1,n_{d},a_{i}^{h}\right) \right) -c_{s}-c_{h}\left( \bar{n}_{s}+1,\bar{n%
-}_{h}+1,n_{d}\right) <$ $-v_{i}\left( 1-p_{a}\left( \bar{n}_{s}+1,\bar{n}%
-_{h},n_{d}\right) \right) -c_{s}$ and $-v_{i}\left( 1-p_{a}\left( \bar{n}%
-_{s}+1,\bar{n}_{h}+1,n_{d},a_{i}^{h}\right) \right) -c_{s}-c_{h}\left( \bar{n%
-}_{s}+1,\bar{n}_{h}+1,n_{d}\right) <-v_{i}-c_{n}$ agent $i$ will choose to
-become a node in the mix-net.
+Then if
+\begin{gather*}
+-v_{i}\left( 1-p_{a}\left( \bar{n}_{s}+1,\bar{n}_{h}+1,n_{d},a_{i}^{h}%
+\right) \right) -c_{s}-c_{h}\left( \bar{n}_{s}+1,\bar{n}_{h}+1,n_{d}\right)
+\\
+<-v_{i}\left( 1-p_{a}\left( \bar{n}_{s}+1,\bar{n}_{h},n_{d}\right) \right)
+-c_{s}
+\end{gather*}
+and
+\begin{gather*}
+-v_{i}\left( 1-p_{a}\left( \bar{n}_{s}+1,\bar{n}_{h}+1,n_{d},a_{i}^{h}%
+\right) \right) -c_{s}-c_{h}\left( \bar{n}_{s}+1,\bar{n}_{h}+1,n_{d}\right)
+\\
+<-v_{i}-c_{n}
+\end{gather*}
+agent $i$ will choose to become a node in the mix-net.
-If $-v_{i}\left( 1-p_{a}\left( \bar{n}_{s}+1,\bar{n}_{h}+1,n_{d},a_{i}^{h}%
+If
+\begin{gather*}
+-v_{i}\left( 1-p_{a}\left( \bar{n}_{s}+1,\bar{n}_{h}+1,n_{d},a_{i}^{h}%
\right) \right) -c_{s}-c_{h}\left( \bar{n}_{s}+1,\bar{n}_{h}+1,n_{d}\right) >
-$ $-v_{i}\left( 1-p_{a}\left( \bar{n}_{s}+1,\bar{n}_{h},n_{d}\right) \right)
--c_{s}$ and $-v_{i}\left( 1-p_{a}\left( \bar{n}_{s}+1,\bar{n}%
-_{h},n_{d}\right) \right) -c_{s}<-v_{i}-c_{n}$ then agent $i$ will choose to
-be a user of the system. Otherwise, $i$ will simply not use the system.
+\\
+-v_{i}\left( 1-p_{a}\left( \bar{n}_{s}+1,\bar{n}_{h},n_{d}\right) \right)
+-c_{s}
+\end{gather*}
+and
+\begin{gather*}
+-v_{i}\left( 1-p_{a}\left( \bar{n}_{s}+1,\bar{n}_{h},n_{d}\right) \right)
+-c_{s} \\
+<-v_{i}-c_{n}
+\end{gather*}
+then agent $i$ will choose to be a user of the system. Otherwise, $i$ will
+simply not use the system.
Of course, for a formal solution we need an explicit functional form of the
-probability function. We have seen above, however, that privacy metrics (like
-\cite{Serj02,Diaz02}) do not directly translate into monotonic probability
-functions of the type traditionally used in game theory. Furthermore, the
-actual level of anonymity will depend on the mix-net protocol and topology
-(cascades will provide larger anonymity sets at each node than free-route
-networks). Nevertheless we can highlight the
-economic rationale implicit in the above equation. In the first
-comparison agent $i$ is comparing her contribution to her own anonymity by
-acting as a node to the costs of doing so. Acting as a node dramatically
-increases anonymity, but it will also bring more
-traffic-related costs to the agent. Agents with high privacy sensitivity
-(high $v_{i}$) will be obviously keener in accepting the trade-off and
-becoming nodes.
+probability function. We have seen above, however, that privacy metrics
+(like \cite{Serj02,Diaz02}) do not directly translate into monotonic
+probability functions of the type traditionally used in game theory.
+Furthermore, the actual level of anonymity will depend on the mix-net
+protocol and topology (cascades will provide larger anonymity sets at each
+node than free-route networks). Nevertheless we can highlight the economic
+rationale implicit in the above equation. In the first comparison agent $i$
+is comparing her contribution to her own anonymity by acting as a node to
+the costs of doing so. Acting as a node dramatically increases anonymity,
+but it will also bring more traffic-related costs to the agent. Agents with
+high privacy sensitivity (high $v_{i}$) will be obviously keener in
+accepting the trade-off and becoming nodes.
\subsubsection{Strategic Agents: Simple Case}
@@ -669,29 +697,11 @@
\begin{equation*}
\begin{tabular}{cccc}
-$i/j$ & $a_{j}^{h}$ & $a_{j}^{s}$ & $a_{j}^{n}$ \\
-$a_{i}^{h}$ & $-v_{i}\left( 1-p_{a}\left( \bar{n}_{s}+2,\bar{n}%
-_{h}+2,n_{d},a_{i}^{h}\right) \right) -c_{s}-c_{h}\left( \bar{n}_{s}+2,\bar{n%
-}_{h}+2,n_{d}\right) ,-v_{j}\left( 1-p_{a}\left( \bar{n}_{s}+2,\bar{n}%
-_{h}+2,n_{d},a_{j}^{h}\right) \right) -c_{s}-c_{h}\left( \bar{n}_{s}+2,\bar{n%
-}_{h}+2,n_{d}\right) $ & $-v_{i}\left( 1-p_{a}\left( \bar{n}_{s}+2,\bar{n}%
-_{h}+1,n_{d},a_{i}^{h}\right) \right) -c_{s}-c_{h}\left( \bar{n}_{s}+2,\bar{n%
-}_{h}+1,n_{d}\right) ,-v_{j}\left( 1-p_{a}\left( \bar{n}_{s}+2,\bar{n}%
-_{h}+1,n_{d}\right) \right) -c_{s}$ & $-v_{i}\left( 1-p_{a}\left( \bar{n}%
-_{s}+1,\bar{n}_{h}+1,n_{d},a_{i}^{h}\right) \right) -c_{s}-c_{h}\left( \bar{n%
-}_{s}+1,\bar{n}_{h}+1,n_{d}\right) ,-v_{j}-c_{n}$ \\
-$a_{i}^{s}$ & $-v_{i}\left( 1-p_{a}\left( \bar{n}_{s}+2,\bar{n}%
-_{h}+1,n_{d}\right) \right) -c_{s},-v_{j}\left( 1-p_{a}\left( \bar{n}_{s}+2,%
-\bar{n}_{h}+1,n_{d},a_{j}^{h}\right) \right) -c_{s}-c_{h}\left( \bar{n}%
-_{s}+2,\bar{n}_{h}+1,n_{d}\right) $ & $-v_{i}\left( 1-p_{a}\left( \bar{n}%
-_{s}+2,\bar{n}_{h},n_{d}\right) \right) -c_{s},-v_{j}\left( 1-p_{a}\left(
-\bar{n}_{s}+2,\bar{n}_{h},n_{d}\right) \right) -c_{s}$ & $-v_{i}\left(
-1-p_{a}\left( \bar{n}_{s}+1,\bar{n}_{h},n_{d}\right) \right)
--c_{s},-v_{j}-c_{n}$ \\
-$a_{i}^{n}$ & $-v_{i}-c_{n},-v_{j}\left( 1-p_{a}\left( \bar{n}_{s}+1,\bar{n}%
-_{h}+1,n_{d},a_{j}^{h}\right) \right) -c_{s}-c_{h}\left( \bar{n}_{s}+1,\bar{n%
-}_{h}+1,n_{d}\right) $ & $-v_{i}-c_{n},-v_{j}\left( 1-p_{a}\left( \bar{n}%
-_{s}+1,\bar{n}_{h},n_{d}\right) \right) -c_{s}$ & $-v_{i}-c_{n},-v_{j}-c_{n}$%
+{\tiny Player i / Player j} & $a_{j}^{h}$ & $a_{j}^{s}$ & $a_{j}^{n}$ \\
+$a_{i}^{h}$ & [see appendix for values - do not fit table yet] & ... & ...
+\\
+$a_{i}^{s}$ & ... & ... & ... \\
+$a_{i}^{n}$ & ... & ... & ...
\end{tabular}
\end{equation*}
@@ -700,17 +710,14 @@
nodes and less nodes. In addition to the previous analysis, now the final
outcome will also depend on how much each player knows about whether the
other is honest or not, and how much he knows about the other player's
-sensitivity to privacy.
-
-[[extend from here on]]
-
-when $v_{1}>>v_{2}$ then equilibrium with free-riding can be sustained. \cite
-{palfrey-rosenthal-89}\footnote{%
-Show proof for a specific probability function here [[extend]].}
-
-unknow type:\ then probability distribution over other player's type. Again
-following \cite{palfrey-rosenthal-89} there can be solutions here where one
-player free-rides.
+sensitivity to privacy.%extend
+When $v_{1}>>v_{2}$ then equilibrium with free-riding can be sustained: the
+problem can be mapped to \cite{palfrey-rosenthal-89}.%
+%show proof with prob. distribition here, simplygfiy
+Also when the other agent's unknow type is unknow the system can have
+equilibria with free-riding, under certain probability distribution over
+other player's type. This can be proved again following \cite
+{palfrey-rosenthal-89}.
\subsubsection{Strategic Agents: Multi-player Case}
@@ -731,85 +738,71 @@
Of course an H type will also suffer itself because of this strategy
[[extend on this]]} This can be seen as a public good with free-riding type
of problem \cite{cornes-sandler-86}. Under which conditions this will not
-happen?\footnote{%
-Re-use and extend the following:
-\par
-\begin{equation*}
-\begin{tabular}{cccc}
-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*}
-\par
-\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*}
-}
+happen?
Well, one of the interesting economic aspects of this scenario is that the
-high sensitive agents do want some level of free-riding, from the low
-sensitive types that will provide traffic and therefore noise. On the other
-side, they might not want too much free-riding if this involves too high
-traffic costs. This latter point however must be specified: high privacy
-sensitive types, at parity of traffic, prefer to be a node (because
+highly sensitive agents \textit{do} want some level of free-riding, from the
+less sensitive types that will provide traffic and therefore noise. On the
+other side, they might not want too much free-riding if this involves too
+high traffic costs. This latter point however must be specified: highly
+privacy sensitive types, at parity of traffic, prefer to be a node (because
anonymity and reliability will increase) and prefer to work in systems with
fewer nodes (otherwise traffic gets too dispersed and the anonymity sets get
-too small). So, if $-v_{L}-c_{n}$ is particularly high, i.e. if the cost of
-not 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]].
+too small). So, if $-v_{i}-c_{n}$ is particularly high, i.e. if the cost of
+not having anonymity is very high for each very privacy sensitive type, then
+each highly sensitive type might tend to act as node regardless of what the
+others do.%{extend}
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]]. In addition, certain nodes with higher sensitivity might indeed
-prefer to incur all the costs and be the only nodes in system.
+high compared to the costs of handling the traffic of more less sensitive
+types.%{extend}
+In addition, certain nodes with higher sensitivity might indeed prefer to
+incur all the costs and be the only nodes in system.
When the valuations are continously distributed this is likely to create
equilibria where the agents with the highest evaluations $v_{i}$ will become
-node, and the others, starting with the ``marginal'' type, will provide
+nodes, and the others, starting with the ``marginal'' type, will provide
traffic (see also \cite{bergstrom-blume--varian-86}). At this point an
-equilibrium level of free-riding might be reached.
+equilibrium level of free-riding might be reached. This condition can be
+compared to \cite{grossman-stiglitz-80}, where the paradox of
+informationally efficient markets is described.\footnote{%
+The equilibrium in \cite{grossman-stiglitz-80} relies in fact on the
+``marginal'' agent which is indifferent between getting more information
+about the market and not getting it.}
-The problems start if we consider now a different situation. Rather than
-having a continuous distribution of evaluations $v_{i}$, we consider two
-types of agents: the agent with an high evaluation, $v_{H}$, and the agent
-with a low evaluations, $v_{L}$. 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 each 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 $v_{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 $v_{H}$ type, which in
-fact has an interesting in having more traffic. This allows us to focus on
-the interaction between a sub-set of users, the identical high-types. Here
-the marginal argument discussed above will not work, and coordination might
-be costly especially when nodes do not trust each other. [[extend this]] In
-this scenario where the mix-net system is self-sustaining and free and the
-agents are of high and low type, the actions of the agents must be visible
-and the agents themselves must agree on reacting together to respond to any
+The problems however start if we consider now a different situation. Rather
+than having a continuous distribution of evaluations $v_{i}$, we consider
+two types of agents: the agent with an high evaluation, $v_{H}$, and the
+agent with a low evaluations, $v_{L}$. 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 each 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 $v_{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 $v_{H}$ type, which
+in fact has an interesting in having more traffic. This allows us to focus
+on the interaction between a sub-set of users, the identical high-types.
+Here the marginal argument discussed above will not work, and coordination
+might be costly especially when nodes do not trust each other. In this
+scenario where the mix-net system is self-sustaining and free and the agents
+are of high and low type, the actions of the agents must be visible and the
+agents themselves must agree on reacting together to respond to any
deviation of a marginal player, thus re-stablishing the trigger strategy of
-the 2-agents case.[[extend this]]. In realistic scenarios, however, this
-will involve very high transaction/coordination costs, and will require an
-extreme (and possibly unlikely) level of rationality on the side of the
-agents. One option to counter coordiantion costs is to maintain the
-distributed trust structure but centralize other elements of the system. We
-consider some alternative mechanisms that can make mix-net systems
-economically viable in the next section.
+the 2-agents case.%{extend}
+In realistic scenarios, however, this will involve very high
+transaction/coordination costs, and will require an extreme (and possibly
+unlikely) level of rationality on the side of the agents. One option to
+counter coordiantion costs is to maintain the distributed trust structure
+but centralize other elements of the system. We consider some alternative
+mechanisms that can make mix-net systems economically viable in the next
+section.
+
\section{Alternate incentive mechanisms}
\label{sec:alternate-incentives}
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/