Considerations for mix-net path equilibrium analysis:
Notes from economic theory
-----------------------------------------------------
Source: Microeconomic Theory. Mas-Colell, Whinston, Green. 1995
Partial equilibrium model, ignore the feedback effects between the
individual firm, consumer, or market and the rest of the economy.
General equilibrium model, an entire economy is studied. Insight on
how the various elements of the system are interrelated.
A general equilibrium for competitive economy:
competitive equilibrium (Walrasin equilibrium)
1. each consumer maximized utility subject to budget constraints
2. each firm maximizing the present value of profits and distributing
profits to households owning firm
3. prices are such that market quantities demanded for all goods and
services equal their market quantities supplied
Asymmetric information: how characterize market equilibria in
presence of aymmetric info?
Constrained Pareto optimal allocation: allocations cannot be Pareto
improved upon by central authority who, like market participants,
cannot observe individuals' privately help information.
Possibility that informed individuals may find ways to *signal*
information about their unobservable knowledge through observable
actions.
- Who are the informed individuals?
1) Statistics page owners (if telling the truth!)
2) Remailer operators (who can't be trusted)
3) Senders whose messages failed to arrive.
Uninformed parties may develop mechanisms to distinguish, or *screen*,
informed individuals who have differing information.
- i.e. if you trust a statistics page today and your message
fails to deliver, you don't trust him tomorrow.
Also you try to take consensus information from stats pages.
The problem is that if a sender S has a decision rule D()
for picking a mix node which depends on just the history
S has with the stats pages, then an adversary A should attack
that history - cause S to have a bad experience with the
stats page A doesn't like, so S turns to A's stats.
- We have two levels of screening.
1) Sender screens the scorers.
2) Based on the information from scorers, sender
screens the mix nodes.
Self-selection process: Consider welfare characteristics of resulting
market equilibrium and potential for Pareto-improving market
intervention.
- What exactly does this mean for us - that we want the
nodes to have an economic incentive to be "good" ?
(Not sure I understand - dm)
Mixnet system
-------------
Actors in the system (partial list)
* Sender. Wants to send a message anonymously to some
receiver.
* Nodes.
* Scorers (statistics pages).
* Adversary.
"Node productivity" - loosely, how often the node does what it's
supposed to do!
In our system, node productivity is publicly observable.
- Yes and no. The sender can observe the productivity of
any node indirectly by seeing whether a message made it
or not. (NOTE: this assumes sender gets a return receipt
or otherwise knows when failure happens. may not be true).
The sender can observe the statistics pages (scorers).
But "node productivity" is difficult for anyone but the
node itself to directly observe. Unless the sender is
also a passive monitoring adversary...
First fundamental welfare theorem: if every relevant good is traded in
a market at publicly known prices, and if households and firms act
perfectly competitively, then the market outcome is Pareto optimal (pg
308). That is, when markets are complete, any competitive equilibrium
is necessarily Pareto optimal (a system is Pareto optimal if it is
impossible to make some individuals better off without making some
other individuals worse off.)
- What is the justification for considering a Pareto optimal
state in our situation? What does that exactly mean for our
mix-net system?
Suppose markets complete and no adversaries. Then everyone
will end up in a situation where the reliability of all
messages sent is maximized. That seems to be the idea? but
then how does that correspond to who's "better off?"
(better off now means "my message will get through?")
Does this need a notion of wear on a node in order to
avoid everyone just sending *all* messages through the
most reliable (single) mix node?
Focal points in Nash equilibrium: some outcomes are better than
others, for example, using a path with higher expectation of success.
Games of incomplete information are referred to as Bayesian Nash
equilibrium. Our scorers create this probability distribution of
expectation for successful transmission across mix-net nodes/paths.
We use this distribution for Bayesian game.
We really want to consider *dynamic games*, which consider decisions
over time, with possible feedback mechanisms of previous decisions
affecting future equilibrium.
Subgame optimal Nash equilibrium: principal of sequential rationality:
equilibrium strategies should specify optimal behavior from any point
in the game onwards (a principle intimately related to procedure of
backward induction, although, in infinite games -- which we consider
-- we instead need to consider "reasonable beliefs" and "forward
induction".)
Consider subgame perfect Nash equilibria (SPNEs) for adverse selection
model. In stage 1, scorer publishes the scores of various mix-net
nodes. In stage 2, senders decide which mix-net nodes to use to form
a path.
Reasonable belief for choosing paths?
-------------------------------------
Assumption: Rational users will only choose mix-net nodes with score
greater or equal to x, where x is some threshold probability of
success (0,1).
The set of all possible paths chosen by rational users in the system
is the set of permutations of length 1..k of all nodes \element GOOD
of length 1 to k, where
a node is \element GOOD iff it's score is above some (system-wide,
user-specific?) threshold x, and
k is |GOOD|
Is this threshold a bad assumption? Perhaps we should actually just
have the set of all permutations of length 1..n (where n is
|{nodes}|). Many are bad, but who cares -- here, we only consider
probability distribution for nodes, not selection of nodes into
dissimilar groups based on (self-selection/observed behavior/etc.)
like GOOD and BAD. For grouping, turn to theory about signaling:
Scorers perform signaling - i.e., the communicate information about
the parties (nodes) efficiency, not the nodes themselves. We wish to
create a system that does not have signaling by parties themselves,
but instead by another third party authority.
- Or several third party authorities (several scorers)
- unless we count the ledger as an authority here?
Note: probability u that node action is of type S, therefore expected
productivity of node is u*S + (1-u)*F, where S is success - the
message is transmitted, and F is fail, the message is not transmitted.
Simple system, as productivity for S is 1, F is 0. Therefore,
expected productivity is merely u*1 + (1-u)*0 = u
Principal-agent problem:
------------------------
When asymmetries of information develop subsequent to signing of
contract. This applies to our situation, as (assuming) all users have
similar scores prior to path selection. What happens after?
Moral hazard is principal-agent model:
User (principal) cannot always observe nodes (agent) actions. When
agent's actions are not observable, contract can no longer specify
them in an effective manner, because there is simply no way to verify
whether the agent has fulfilled his obligations.
- Also a principal-agent problem in the users and the
scorers? The users want to know if the nodes are "good."
The scorers may want something else (are they being paid?
not in money, but in reputation of their own).
- Also the scorers may be controlled by an adversary who
wishes to maximize its benefit by minimizing the user's.
Come to think of it, is that a good way to characterize
the adversary:
"That player whose utility is maximized exactly when
the sender's utility is minimized" ?
Therefore, principal must design agent's compensation scheme in a way
that indirectly gives him the incentive to take the correct action
(that is, if actions were observable).
- Note that compensation isn't just monetary. Also in
the reputation the scorer obtains by providing good info.
So the scorer needs to take this into consideration.
(Can/should we assume that the scorer knows how the
sender will evaluate its decisions? What about the
possibility of honest mistakes?)