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?)