[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[freehaven-cvs] bugfixes for section 4
Update of /home/freehaven/cvsroot/doc/fc03
In directory moria.seul.org:/home/arma/work/freehaven/doc/fc03
Modified Files:
econymics.tex
Log Message:
bugfixes for section 4
Index: econymics.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/fc03/econymics.tex,v
retrieving revision 1.22
retrieving revision 1.23
diff -u -d -r1.22 -r1.23
--- econymics.tex 16 Sep 2002 06:27:12 -0000 1.22
+++ econymics.tex 16 Sep 2002 07:37:07 -0000 1.23
@@ -491,26 +491,25 @@
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
+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,
-% did my changes just make this statement incorrect?
-suggest against using a sequential approach \textit{a la} Stackleberg.
+from other users; or don't 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 [elaborate],
+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. [explain war of attrition]
+is not applicable. [briefly explain war of attrition]
\subsection{Adversary}
@@ -519,7 +518,7 @@
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
+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
@@ -540,14 +539,14 @@
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
+node, costs increase with the traffic; we focus here 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
+publicly known (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
@@ -563,14 +562,14 @@
-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}
+Thus 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
+n_{s},n_{h},n_{d},a_{i}^{h}\right) $ is the probability that 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
+v}\right] $. $c_{s},c_{h}\left( n_{s},n_{h},n_d\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
@@ -596,19 +595,20 @@
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
+a^{s,h,n}$ also the utility of sending a successful 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]].}
+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.
@@ -642,9 +642,9 @@
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) >
+\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)
+>-v_{i}\left( 1-p_{a}\left( \bar{n}_{s}+1,\bar{n}_{h},n_{d}\right) \right)
-c_{s}
\end{gather*}
and
@@ -658,18 +658,18 @@
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
+(like \cite{Diaz02,Serj02}) 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 (cascade-based or synchronous networks will provide
larger anonymity sets than asynchronous networks where traffic is divided
among the nodes). 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
+comparing the contribution to her own anonymity of 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.
+with high privacy sensitivity (high $v_{i}$) will clearly be more likely
+to accept the trade-off and become nodes.
\subsubsection{Strategic Agents: Simple Case}
@@ -702,18 +702,18 @@
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
-When $v_{1}>>v_{2}$ then equilibrium with free-riding can be sustained: the
-problem can be mapped to \cite{palfrey-rosenthal-89}.%
+sensitivity to privacy. %extend
+When $v_{i}>>v_{j}$ 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
+Also when the other agent's type is unknown 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}
-Traditionally, cooperative solutions in non infinite horizon are not
+Traditionally, cooperative solutions with a finite 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
@@ -721,18 +721,19 @@
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
+``Defection'' would be, for example, acting only as a user and refusing to be
+a node: 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
+Of course a high sensitivity user 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
+of problem \cite{cornes-sandler-86}. Under which conditions will this not
happen?
-Well, one of the interesting economic aspects of this scenario is that the
+One of the interesting economic aspects of this scenario is that the
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
@@ -743,13 +744,13 @@
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 of more less sensitive
-types.%{extend}
+others do. %{extend}
+Also, if there are enough low types, again a high type might have an
+interest in acting alone if its costs of not having anonymity would be too
+high compared to the costs of handling the traffic of the 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.
+incur all the costs and be the only nodes in the system.
When the valuations are continously distributed this is likely to create
equilibria where the agents with the highest evaluations $v_{i}$ will become
@@ -764,36 +765,37 @@
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
+two types of agents: the agent with a high valuation, $v_{H}$, and the
+agent with a low valuations, $v_{L}$. Fudenberg and Levine \cite
+{fudenberg88} have a model where each player plays a set of identical
+players,
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
+the concatenated interactions in a large but finite set of players.
+The approach in 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
+continuum of the other players. In other words, for 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.
+in fact has an interest in having more traffic. This allows us to focus
+on the interaction between a subset 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
+are of high and low types, 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}
+deviation of a marginal player, thus re-establishing the trigger strategy of
+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.
+unlikely) level of rationality on the side of the agents. One option
+to help reduce coordination costs is to maintain the distributed trust
+structure but centralize other elements of the system. We consider some
+other mechanisms that can make mix-net systems economically viable in
+the next section.
\section{Alternate incentive mechanisms}
\label{sec:alternate-incentives}
@@ -1072,6 +1074,9 @@
It is clear that, given their limited tractability in closed-form terms,
some of the above extensions will need computational solutions.
+
+[Plus a brief summary here of what we've said in the paper that's neat.
+(What is that?)]
\bibliographystyle{plain}
\bibliography{econymics}
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/