On Decentralized Incentive Compatible Mechanisms for Partially Informed Environments ∗ Ahuva Mu"alem School of Engineering and Computer Science The Hebrew University of Jerusalem ahumu@cs.huji.ac.il ABSTRACT Algorithmic Mechanism Design focuses on Dominant Strategy Implementations. The main positive results are the celebrated Vickrey-Clarke-Groves (VCG) mechanisms and computationally efficient mechanisms for severely restricted players (single-parameter domains). As it turns out, many natural social goals cannot be implemented using the dominant strategy concept [35, 32, 22, 20]. This suggests that the standard requirements must be relaxed in order to construct general-purpose mechanisms. We observe that in many common distributed environments computational entities can take advantage of the network structure to collect and distribute information. We thus suggest a notion of partially informed environments. Even if the information is recorded with some probability, this enables us to implement a wider range of social goals, using the concept of iterative elimination of weakly dominated strategies. As a result, cooperation is achieved independent of agents" belief. As a case study, we apply our methods to derive Peer-to-Peer network mechanism for file sharing. Categories and Subject Descriptors J.4 [Social and Behavioral Sciences]: Economics General Terms Design, Algorithms 1. INTRODUCTION Recently, global networks have attracted widespread study. The emergence of popular scalable shared networks with self-interested entities - such as peer-to-peer systems over the Internet and mobile wireless communication ad-hoc networks - poses fundamental challenges. Naturally, the study of such giant decentralized systems involves aspects of game theory [32, 34]. In particular, the subfield of Mechanism Design deals with the construction of mechanisms: for a given social goal the challenge is to design rules for interaction such that selfish behavior of the agents will result in the desired social goal [23, 33]. Algorithmic Mechanism Design (AMD) focuses on efficiently computable constructions [32]. Distributed Algorithmic Mechanism Design (DAMD) studies mechanism design in inherently decentralized settings [30, 12]. The standard model assumes rational agents with quasi-linear utilities and private information, playing dominant strategies. The solution concept of dominant strategies - in which each player has a best response strategy regardless of the strategy played by any other player - is well suited to the assumption of private information, in which each player is not assumed to have knowledge or beliefs regarding the other players. The appropriateness of this set-up stems from the strength of the solution concept, which complements the weak information assumption. Many mechanisms have been constructed using this set-up, e.g., [1, 4, 6, 11, 14, 22]. Most of these apply to severely-restricted cases (e.g., single-item auctions with no externalities) in which a player"s preference is described by only one parameter (single-parameter domains). To date, Vickrey-Clarke-Groves (VCG) mechanisms are the only known general method for designing dominant strategy mechanisms for general domains of preferences. However, in distributed settings without available subsidies from outside sources, VCG mechanisms cannot be accepted as valid solutions due to a serious lack of budget balance. Additionally, for some domains of preferences, VCG mechanisms and weighted VCG mechanisms are faced with computational hardness [22, 20]. Further limitations of the set-up are discussed in subsection 1.3. In most distributed environments, players can take advantage of the network structure to collect and distribute information about other players. This paper thus studies the effects of relaxing the private information assumption. 240 One model that has been extensively studied recently is the Peer-to-Peer (P2P) network. A P2P network is a distributed network with no centralized authority, in which the participants share their individual resources (e.g., processing power, storage capacity, bandwidth and content). The aggregation of such resources provides inexpensive computational platforms. The most popular P2P networks are those for sharing media files, such as Napster, Gnutella, and Kazaa. Recent work on P2P Incentives include micropayment methods [15] and reputation-based methods [9, 13]. The following description of a P2P network scenario illustrates the relevance of our relaxed informational assumption. Example 1. Consider a Peer-to-Peer network for file sharing. Whenever agent B uploads a file from agent A, all peers along the routing path know that B has loaded the file. They can record this information about agent B. In addition, they can distribute this information. However, it is impossible to record all the information everywhere. First, such duplication induces huge costs. Second, as agents dynamically enter and exit from the network, the information might not be always available. And so it is seems natural to consider environments in which the information is locally recorded, that is, the information is recorded in the closest neighborhood with some probability p. In this paper we shall see that if the information is available with some probability, then this enables us to implement a wider range of social goals. As a result, cooperation is achieved independent of agents" belief. This demonstrates that in some computational contexts our approach is far less demanding than the Bayesian approach (that assumes that players" types are drawn according to some identified probability density function). 1.1 Implementations in Complete Information Set-ups In complete information environments, each agent is informed about everyone else. That is, each agent observes his own preference and the preferences of all other agents. However, no outsider can observe this information. Specifically, neither the mechanism designer nor the court. Many positive results were shown for such arguably realistic settings. For recent surveys see [25, 27, 18]. Moore and Repullo implement a large class of social goals using sequential mechanisms with a small number of rounds [28]. The concept they used is subgame-perfect implementations (SPE). The SPE-implementability concept seems natural for the following reasons: the designed mechanisms usually have non-artificial constructs and a small strategy space. As a result, it is straightforward for a player to compute his strategy.1 Second, sequential mechanisms avoid simultaneous moves, and thus can be considered for distributed networks. Third, the constructed mechanisms are often decentralized (i.e., lacking a centralized authority or designer) 1 Interestingly, in real life players do not always use their subgame perfect strategies. One such widely studied case is the Ultimatum Bargaining 2-person game. In this simple game, the proposer first makes an offer of how to divide a certain known sum of money, and the responder either agrees or refuses, in the latter case both players earn zero. Somewhat surprisingly, experiments show that the responder often rejects the suggested offer, even if it is bounded away from zero and the game is played only once (see e.g. [38]). and budget-balanced (i.e., transfers always sum up to zero). This happens essentially if there are at least three players, and a direct network link between any two agents. Finally, Moore and Repullo observed that they actually use a relaxed complete information assumption: it is only required that for every player there exists only one other player who is informed about him. 1.2 Implementations in Partially Informed Set-ups and Our Results The complete information assumption is realistic for small groups of players, but not in general. In this paper we consider players that are informed about each other with some probability. More formally, we say that agent B is p-informed about agent A, if B knows the type of A with probability p. For such partially-informed environments, we show how to use the solution concept of iterative elimination of weakly dominated strategies. We demonstrate this concept through some motivating examples that (i) seem natural in distributed settings and (ii) cannot be implemented in dominant strategies even if there is an authorized center with a direct connection to every agent or even if players have single-parameter domains. 1. We first show how the subgame perfect techniques of Moore and Repullo [28] can be applied to p-informed environments and further adjusted to the concept of iterative elimination of weakly dominated strategies (for large enough p). 2. We then suggest a certificate based challenging method that is more natural in computerized p-informed environments and different from the one introduced by Moore and Repullo [28] (for p ∈ (0, 1]). 3. We consider implementations in various network structures. As a case study we apply our methods to derive: (1) Simplified Peer-to-Peer network for file sharing with no payments in equilibrium. Our approach is (agent, file)-specific. (2) Web-cache budget-balanced and economically efficient mechanism. Our mechanisms use reasonable punishments that inversely depend on p. And so, if the fines are large then small p is enough to induce cooperation. Essentially, large p implies a large amount of recorded information. 1.2.1 Malicious Agents Decentralized mechanisms often utilize punishing outcomes. As a result, malicious players might cause severe harm to others. We suggest a quantified notion of malicious player, who benefits from his own gained surplus and from harm caused to others. [12] suggests several categories to classify non-cooperating players. Our approach is similar to [7] (and the references therein), who considered independently such players in different context. We show a simple decentralized mechanism in which q-malicious players cooperate and in particular, do not use their punishing actions in equilibrium. 241 1.3 Dominant Strategy Implementations In this subsection we shall refer to some recent results demonstrating that the set-up of private information with the concept of dominant strategies is restrictive in general. First, Roberts" classical impossibility result shows that if players" preferences are not restricted and there are at least 3 different outcomes, then every dominant-strategy mechanism must be weighted VCG (with the social goal that maximizes the weighted welfare) [35]. For slightly-restricted preference domains, it is not known how to turn efficiently computable algorithms into dominant strategy mechanisms. This was observed and analyzed in [32, 22, 31]. Recently [20] extends Roberts" result to some leading examples. They showed that under mild assumptions any dominant strategy mechanism for variety of Combinatorial Auctions over multi-dimensional domains must be almost weighted VCG. Additionally, it turns out that the dominant strategy requirement implies that the social goal must be monotone [35, 36, 22, 20, 5, 37]. This condition is very restrictive, as many desired natural goals are non-monotone2 . Several recent papers consider relaxations of the dominant strategy concept: [32, 1, 2, 19, 16, 17, 26, 21]. However, most of these positive results either apply to severely restricted cases (e.g., single-parameter, 2 players) or amount to VCG or almost VCG mechanisms (e.g., [19]). Recently, [8, 3] considered implementations for generalized single-parameter players. Organization of this paper: In section 2 we illustrate the concepts of subgame perfect and iterative elimination of weakly dominated strategies in completely-informed and partially-informed environments. In section 3 we show a mechanism for Peer-to-Peer file sharing networks. In section 4 we apply our methods to derive a web cache mechanism. Future work is briefly discussed in section 5. 2. MOTIVATING EXAMPLES In this section we examine the concepts of subgame perfect and iterative elimination of weakly dominated strategies for completely informed and p-informed environments. We also present the notion of q-maliciousness and some other related considerations through two illustrative examples. 2.1 The Fair Assignment Problem Our first example is an adjustment to computerized context of an ancient procedure to ensure that the wealthiest man in Athens would sponsor a theatrical production known as the Choregia [27]. In the fair assignment problem, Alice and Bob are two workers, and there is a new task to be performed. Their goal is to assign the task to the least loaded worker without any monetary transfers. The informational assumption is that Alice and Bob know both loads and the duration of the new task.3 2 E.g., minimizing the makespan within a factor of 2 [32] and Rawls" Rule over some multi-dimensional domains [20]. 3 In first glance one might ask why the completely informed agents could not simply sign a contract, specifying the desired goal. Such a contract is sometimes infeasible due to fact that the true state cannot be observed by outsiders, especially not the court. Claim 1. The fair assignment goal cannot be implemented in dominant strategies.4 2.1.1 Basic Mechanism The following simple mechanism implements this goal in subgame perfect equilibrium. • Stage 1: Alice either agrees to perform the new task or refuses. • Stage 2: If she refuses, Bob has to choose between: - (a) Performing the task himself. - (b) Exchanging his load with Alice and performing the new task as well. Let LT A, LT B be the true loads of Alice and Bob, and let t > 0 be the load of the new task. Assume that load exchanging takes zero time and cost. We shall see that the basic mechanism achieves the goal in a subgame perfect equilibrium. Intuitively this means that in equilibrium each player will choose his best action at each point he might reach, assuming similar behavior of others, and thus every SPE is a Nash equilibrium. Claim 2. ([27]) The task is assigned to the least loaded worker in subgame perfect equilibrium. Proof. By backward induction argument (look forward and reason backward), consider the following cases: 1. LT B ≤ LT A. If stage 2 is reached then Bob will not exchange. 2. LT A < LT B < LT A + t. If stage 2 is reached Bob will exchange, and this is what Alice prefers. 3. LT A + t ≤ LT B. If stage 2 is reached then Bob would exchange, as a result it is strictly preferable by Alice to perform the task. Note that the basic mechanism does not use monetary transfers at all and is decentralized in the sense that no third party is needed to run the procedure. The goal is achieved in equilibrium (ties are broken in favor of Alice). However, in the second case exchange do occur in an equilibrium point. Recall the unrealistic assumption that load exchange takes zero time and cost. Introducing fines, the next mechanism overcomes this drawback. 2.1.2 Elicitation Mechanism In this subsection we shall see a centralized mechanism for the fair assignment goal without load exchange in equilibrium. The additional assumptions are as follows. The cost performing a load of duration d is exactly d. We assume that the duration t of the new task is < T. The payoffs 4 proof: Assume that there exists a mechanism that implements this goal in dominant strategies. Then by the Revelation Principle [23] there exists a mechanism that implements this goal for which the dominant strategy of each player is to report his true load. Clearly, truthfully reporting cannot be a dominant strategy for this goal (if monetary transfers are not available), as players would prefer to report higher loads. 242 of the utility maximizers agents are quasilinear. The following mechanism is an adaptation of Moore and Repullo"s elicitation mechanism [28]5 . • Stage 1: (Elicitation of Alice"s load) Alice announces LA. Bob announces LA ≤ LA. If LA = LA (Bob agrees) goto the next Stage. Otherwise (Bob challenges), Alice is assigned the task. She then has to choose between: - (a) Transferring her original load to Bob and paying him LA − 0.5 · min{ , LA − LA}. Alice pays to the mechanism. Bob pays the fine of T + to the mechanism. - (b) No load transfer. Alice pays to Bob. STOP. • Stage 2: The elicitation of Bob"s load is similar to Stage 1 (switching the roles of Alice and Bob). • Stage 3: If LA < LB Alice is assigned the task, otherwise Bob. STOP. Observe that Alice is assigned the task and fined with whenever Bob challenges. We shall see that the bonus of is paid to a challenging player only in out of equilibria cases. Claim 3. If the mechanism stops at Stage 3, then the payoff of each agent is at least −t and at most 0. Proposition 1. It is a subgame perfect equilibrium of the elicitation mechanism to report the true load, and to challenge with the true load only if the other agent overreports. Proof. Assume w.l.o.g that the elicitation of Alice"s load is done after Bob"s, and that Stage 2 is reached. If Alice truly reports LA = LT A, Bob strictly prefers to agree. Otherwise, if Bob challenges, Alice would always strictly prefer to transfer (as in this case Bob would perform her load for smaller cost), as a result Bob would pay T + to the mechanism. This punishing outcome is less preferable than the normal outcome of Stage 3 achieved had he agreed. If Alice misreports LA > LT A, then Bob can ensure himself the bonus (which is always strictly preferable than reaching Stage 3) by challenging with LA = LT A, and so whenever Bob gets the bonus Alice gains the worst of all payoffs. Reporting a lower load LA < LT A is not beneficial for Alice. In this case, Bob would strictly prefer to agree (and not to announce LA < LA, as he limited to challenge with a smaller load than what she announces). Thus such misreporting can only increase the possibility that she is assigned the task. And so there is no incentive for Alice to do so. All together, Alice would prefer to report the truth in this stage. And so Stage 2 would not abnormally end by STOP, and similarly Stage 1. Observe that the elicitation mechanism is almost balanced: in all outcomes no money comes in or out, except for the non-equilibrium outcome (a), in which both players pay to the mechanism. 5 In [28], if an agent misreport his type then it is always beneficial to the other agent to challenge. In particular, even if the agent reports a lower load. 2.1.3 Elicitation Mechanism for Partially Informed Agents In this subsection we consider partially informed agents. Formally: Definition 1. An agent A is p-informed about agent B, if A knows the type of B with probability p (independently of what B knows). It turns out that a version of the elicitation mechanism works for this relaxed information assumption, if we use the concept of iterative elimination of weakly dominated strategies6 . We replace the fixed fine of in the elicitation mechanism with the fine: βp = max{L, 1 − p 2p − 1 T} + , and assume the bounds LT A, LT B ≤ L. Proposition 2. If all agents are p-informed, p > 0.5, the elicitation mechanism(βp) implements the fair assignment goal with the concept of iterative elimination of weakly dominated strategies. The strategy of each player is to report the true load and to challenge with the true load if the other agent overreport. Proof. Assume w.l.o.g that the elicitation of Alice"s load is done after Bob"s, and that Stage 2 is reached. First observe that underreporting the true value is a dominated strategy, whether Bob is not informed and mistakenly challenges with a lower load (as βp ≥ L) or not, or even if t is very small. Now we shall see that overreporting her value is a dominated strategy, as well. Alice"s expected payoff gained by misreporting ≤ p (payoff if she lies and Bob is informed) +(1 − p) (max payoff if Bob is not informed) ≤ p (−t − βp) < p (−t) + (1 − p) (−t − βp) ≤ p (min payoff of true report if Bob is informed) + (1 − p) (min payoff if Bob is not informed) ≤ Alice"s expected payoff if she truly reports. The term (−t−βp) in the left hand side is due to the fact that if Bob is informed he will always prefer to challenge. In the right hand side, if he is informed, then challenging is a dominated strategy, and if he is not informed the worst harm he can make is to challenge. Thus in stage 2 Alice will report her true load. This implies that challenging without being informed is a dominated strategy for Bob. This argument can be reasoned also for the first stage, when Bob reports his value. Bob knows the maximum payoff he can gain is at most zero since he cannot expect to get the bonus in the next stage. 2.1.4 Extensions The elicitation mechanism for partially informed agents is rather general. As in [28], we need the capability to judge between two distinct declarations in the elicitation rounds, 6 A strategy si of player i is weakly dominated if there exists si such that (i) the payoff gained by si is at least as high as the payoff gained by si, for all strategies of the other players and all preferences, and (ii) there exist a preference and a combination of strategies for the other players such that the payoff gained by si is strictly higher than the payoff gained by si. 243 and upper and lower bounds based on the possible payoffs derived from the last stage. In addition, for p-informed environments, some structure is needed to ensure that underbidding is a dominated strategy. The Choregia-type mechanisms can be applied to more than 2 players with the same number of stages: the player in the first stage can simply points out the name of the wealthiest agent. Similarly, the elicitation mechanisms can be extended in a straightforward manner. These mechanisms can be budget-balanced, as some player might replace the role of the designer, and collect the fines, as observed in [28]. Open Problem 1. Design a decentralized budget balanced mechanism with reasonable fines for independently p-informed n players, where p ≤ 1 − 1/2 1 n−1 . 2.2 Seller and Buyer Scenario A player might cause severe harm to others by choosing a non-equilibrium outcome. In the mechanism for the fair assignment goal, an agent might maliciously challenge even if the other agent truly reports his load. In this subsection we consider such malicious scenarios. For the ease of exposition we present a second example. We demonstrate that equilibria remain unchanged even if players are malicious. In the seller-buyer example there is one item to be traded and two possible future states. The goal is to sell the item for the average low price pl = ls+lb 2 in state L, and the higher price ph = hs+hb 2 in the other state H, where ls is seller"s cost and lb is buyer"s value in state L, and similarly hs, hb in H. The players fix the prices without knowing what will be the future state. Assume that ls < hs < lb < hb, and that trade can occur in both prices (that is, pl, ph ∈ (hs, lb)). Only the players can observe the realization of the true state. The payoffs are of the form ub = xv−tb, us = ts −xvs, where the binary variable x indicates if trade occurred, and tb, ts are the transfers. Consider the following decentralized trade mechanism. • Stage 1: If seller reports H goto Stage 2. Otherwise, trade at the low price pl. STOP. • Stage 2: The buyer has to choose between: - (a) Trade at the high price ph. - (b) No trade and seller pays ∆ to the buyer. Claim 4. Let ∆ = lb−ph+ . The unique subgame perfect equilibrium of the trade mechanism is to report the true state in Stage 1 and trading if Stage 2 is reached. Note that the outcome (b) is never chosen in equilibrium. 2.2.1 Trade Mechanism for Malicious Agents The buyer might maliciously punish the seller by choosing the outcome (b) when the true state is H. The following notion quantifies the consideration that a player is not indifferent to the private surpluses of others. Definition 2. A player is q-malicious if his payoff equals: (1 − q) (his private surplus) − q (summation of others surpluses), q ∈ [0, 1]. This definition appeared independently in [7] in different context. We shall see that the traders would avoid such bad behavior if they are q-malicious, where q < 0.5, that is if their non-indifference impact is bounded by 0.5. Equilibria outcomes remain unchanged, and so cooperation is achieved as in the original case of non-malicious players. Consider the trade mechanism with pl = (1 − q) hs + q lb , ph = q hs + (1 − q) lb , ∆ = (1 − q) (hb − lb − ). Note that pl < ph for q < 0.5. Claim 5. If q < 0.5, then the unique subgame perfect equilibrium for q-malicious players remains unchanged. Proof. By backward induction we consider two cases. In state H, the q-malicious buyer would prefer to trade if (1 − q)(hb − ph) + q(hs − ph) > (1 − q)∆ + q(∆). Indeed, (1 − q)hb + qhs > ∆ + ph. Trivially, the seller prefers to trade at the higher price, (1 − q)(pl − hs) + q(pl − hb) < (1 − q)(ph − hs) + q(ph − hb). In state L the buyer prefers the no trade outcome, as (1−q)(lb −ph)+q(ls −ph) < ∆. The seller prefers to trade at a low price, as (1 − q)(pl − ls) + q(pl − lb) > 0 > −∆. 2.2.2 Discussion No mechanism can Nash-implement this trading goal if the only possible outcomes are trade at pl and trade at ph. To see this, it is enough to consider normal forms (as any extensive form mechanism can be presented as a normal one). Consider a matrix representation, where the seller is the row player and the buyer is the column player, in which every entry includes an outcome. Suppose there is equilibrium entry for the state L. The associate column must be all pl, otherwise the seller would have an incentive to deviate. Similarly, the associate row of the H equilibrium entry must be all ph (otherwise the buyer would deviate), a contradiction. 7 8 The buyer prefers pl and seller ph, and so the preferences are identical in both states. Hence reporting preferences over outcomes is not enough - players must supply additional information. This is captured by outcome (b) in the trade mechanism. Intuitively, if a goal is not Nash-implementable we need to add more outcomes. The drawback is that some new additional equilibria must be ruled out. E.g., additional Nash equilibrium for the trade mechanism is (trade at pl, (b)). That is, the seller chooses to trade at low price at either states, and the buyer always chooses the no trade option that fines the seller, if the second stage is reached. Such buyer"s threat is not credible, because if the mechanism is played only once, and Stage 2 is reached in state H, the buyer would strictly decrease his payoff if he chooses (b). Clearly, this is not a subgame perfect equilibrium. Although each extensive game-form is strategically equivalent to a normal form one, the extensive form representation places more structure and so it seems plausible that the subgame perfect equilibrium will be played.9 7 Formally, this goal is not Maskin monotonic, a necessary condition for Nash-implementability [24]. 8 A similar argument applies for the Fair Assignment Problem. 9 Interestingly, it is a straight forward to construct a sequential mechanism with unique SPE, and additional NE with a strictly larger payoff for every player. 244 3. PEER-TO-PEER NETWORKS In this section we describe a simplified Peer-to-Peer network for file sharing, without payments in equilibrium, using a certificate-based challenging method. In this challenging method - as opposed to [28] - an agent that challenges cannot harm other agents, unless he provides a valid certificate. In general, if agent B copied a file f from agent A, then agent A knows that agent B holds a copy of the file. We denote such information as a certificate(B, f) (we shall omit cryptographic details). Such a certificate can be recorded and distributed along the network, and so we can treat each agent holding the certificate as an informed agent. Assumptions: We assume an homogeneous system with files of equal size. The benefit each agent gains by holding a copy of any file is V . The only cost each agent has is the uploading cost C (induced while transferring a file to an immediate neighbor). All other costs are negligible (e.g., storing the certificates, forwarding messages, providing acknowledgements, digital signatures, etc). Let upA, downA be the numbers of agent A uploads and downloads if he always cooperates. We assume that each agent A enters the system if upA · C < downA · V . Each agent has a quasilinear utility and only cares about his current bandwidth usage. In particular, he ignores future scenarios (e.g., whether forwarding or dropping of a packet might affect future demand). 3.1 Basic Mechanism We start with a mechanism for a network with 3 p-informed agents: B, A1, A2. We assume that B is directly connected to A1 and A2. If B has the certificate(A1, f), then he can apply directly to A1 and request the file (if he refuses, then B can go to court). The following basic sequential mechanism is applicable whenever agent B is not informed and still would like to download the file if it exists in the network. Note that this goal cannot be implemented in dominant strategies without payments (similar to Claim 1, when the type of each agent here is the set of files he holds). Define tA,B to be the monetary amount that agent A should transfer to B. • Stage 1: Agent B requests the file f from A1. - If A1 replies yes then B downloads the file from A1. STOP. - Otherwise, agent B sends A1s no reply to agent A2. ∗ If A2 declares agree then goto the next stage. ∗ Else, A2 sends a certificate(A1, f) to agent B. · If the certificate is correct then tA1,A2 = βp. STOP. · Else tA2,A1 = |C| + . STOP. Stage 2: Agent B requests the file f from A2. Switch the roles of the agents A1, A2. Claim 6. The basic mechanism is budget-balanced (transfers always sum to zero) and decentralized. Theorem 1. Let βp = |C| p + , p ∈ (0, 1]. A strategy that survives iterative elimination of weakly dominated strategies is to reply yes if Ai holds the file, and to challenge only with a valid certificate. As a result, B downloads the file if some agent holds it, in equilibrium. There are no payments or transfers in equilibrium. Proof. Clearly if the mechanism ends without challenging: −C ≤ u(Ai) ≤ 0. And so, challenging with an invalid certificate is always a dominated strategy. Now, when Stage 2 is reached, A2 is the last to report if he has the file. If A2 has the file it is a weakly undominated strategy to misreport, whether A1 is informed or not: A2"s expected payoff gained by misreporting no ≤ p · (−βp) + (1 − p) · 0 < −C ≤ A2"s payoff if she reports yes. This argument can be reasoned also for Stage 1, when A1 reports whether he has the file. A1 knows that A2 will report yes if and only if she has the file in the next stage, and so the maximum payoff he can gain is at most zero since he cannot expect to get a bonus. 3.2 Chain Networks In a chain network, agent B is directly connected to A1, and Ai is directly connected to agent Ai+1. Assume that we have an acknowledgment protocol to confirm the receipt of a particular message. To avoid message dropping, we add the fine (βp +2 ) to be paid by an agent who hasn"t properly forwarded a message. The chain mechanism follows: • Stage i: Agent B forwards a request for the file f to Ai (through {Ak}k≤i). • If Ai reports yes, then B downloads f from Ai. STOP. • Otherwise Ai reports no. If Aj sends a certificate(Ak, f) to B, ( j, k ≤ i), then - If certificate(Ak, f) is correct, then t(Ak, Aj) = βp. STOP. - Else, t(Aj, Ak) = C + . STOP. If Ai reports that he has no copy of the file, then any agent in between might challenge. Using digital signatures and acknowledgements, observe that every agent must forward each message, even if it contains a certificate showing that he himself has misreported. We use the same fine, βp, as in the basic mechanism, because the protocol might end at stage 1 (clearly, the former analysis still applies, since the actual p increases with the number of players). 3.3 Network Mechanism In this subsection we consider general network structures. We need the assumption that there is a ping protocol that checks whether a neighbor agent is on-line or not (that is, an on-line agent cannot hide himself). To limit the amount of information to be recorded, we assume that an agent is committed to keep any downloaded file to at least one hour, and so certificates are valid for a limited amount of time. We assume that each agent has a digitally signed listing of his current immediate neighbors. As in real P2P file sharing applications, we restrict each request for a file to be forwarded at most r times (that is, downloads are possible only inside a neighborhood of radius r). 245 The network mechanism utilizes the chain mechanism in the following way: When agent B requests a file from agent A (at most r − 1 far), then A sends to B the list of his neighbors and the output of the ping protocol to all of these neighbors. As a result, B can explore the network. Remark: In this mechanism we assumed that the environment is p-informed. An important design issue that it is not addressed here is the incentives for the information propagation phase. 4. WEB CACHE Web caches are widely used tool to improve overall system efficiency by allowing fast local access. They were listed in [12] as a challenging application of Distributed Algorithmic Mechanism Design. Nisan [30] considered a single cache shared by strategic agents. In this problem, agent i gains the value vT i if a particular item is loaded to the local shared cache. The efficient goal is to load the item if and only if ΣvT i ≥ C, where C is the loading cost. This goal reduces to the public project problem analyzed by Clarke [10]. However, it is well known that this mechanism is not budget-balanced (e.g., if the valuation of each player is C, then everyone pays zero). In this section we suggest informational and environmental assumptions for which we describe a decentralized budgetbalanced efficient mechanism. We consider environments for which future demand of each agent depends on past demand. The underlying informational and environmental requirements are as follows. 1. An agent can read the content of a message only if he is the target node (even if he has to forward the message as an intermediate node of some routing path). An agent cannot initiate a message on behalf of other agents. 2. An acknowledgement protocol is available, so that every agent can provide a certificate indicating that he handled a certain message properly. 3. Negligible costs: we assume p-informed agents, where p is such that the agent"s induced cost for keeping records of information is negligible. We also assume that the cost incurred by sending and forwarding messages is negligible. 4. Let qi(t) denotes the number of loading requests agent i initiated for the item during the time slot t. We assume that vT i (t), the value for caching the item in the beginning of slot t depends only on most recent slot, formally vT i (t) = max{Vi(qi(t − 1)), C}, where Vi(·) is a non-decreasing real function. In addition, Vi(·) is a common knowledge among the players. 5. The network is homogeneous in the sense that if agent j happens to handle k requests initiated by agent i during the time slot t, then qi(t) = kα, where α depends on the routing protocol and the environment (α might be smaller than 1, if each request is flooded several times). We assume that the only way agent i can affect the true qi(t) is by superficially increasing his demand for the cached item, but not the other way (that is, agent"s loss, incurred by giving up a necessary request for the item, is not negligible). The first requirement is to avoid free riding, and also to avoid the case that an agent superficially increases the demand of others and as a result decreases his own demand. The second requirement is to avoid the case that an agent who gets a routing request for the item, records it and then drops it. The third is to ensure that the environment stays well informed. In addition, if the forwarding cost is negligible each agent cooperates and forwards messages as he would not like to decrease the future demand (that monotonically depends on the current time slot, as assumed in the forth requirement) of some other agent. Given that the payments are increasing with the declared values, the forth and fifth requirements ensure that the agent would not increase his demand superficially and so qi(t) is the true demand. The following Web-Cache Mechanism implements the efficient goal that shares the cost proportionally. For simplicity it is described for two players and w.l.o.g vT i (t) equals the number of requests initiated by i and observed by any informed j (that is, α = 1 and Vi(qi(t − 1)) = qi(t − 1)). • Stage 1: (Elicitation of vT A(t)) Alice announces vA. Bob announces vA ≥ vA. If vA = vA goto the next Stage. Otherwise (Bob challenges): - If Bob provides vA valid records then Alice pays C to finance the loading of the item into the cache. She also pays βp to Bob. STOP. - Otherwise, Bob finances the loading of the item into the cache. STOP. • Stage 2: The elicitation of vT B(t) is done analogously. • Stage 3: If vA + vB < C, then STOP. Otherwise, load the item to the cache, Alice pays pA = vA vA+vB · C, and Bob pays pB = vB vA+vB · C. Claim 7. It is a dominated strategy to overreport the true value. Proof. Let vT A < VA. There are two cases to consider: • If vT A + vB < C and vA + vB ≥ C. We need to show that if the mechanism stops normally Alice would pay more than vT A, that is: vA vA+vB ·C > vT A. Indeed, vA C > vA (vT A + vB) > vT A (vA + vB). • If vT A + vB ≥ C, then clearly, vA vA+vB > vT A vT A +vB . Theorem 2. Let βp = max{0, 1−2p p · C} + , p ∈ (0, 1]. A strategy that survives iterative elimination of weakly dominated strategies is to report the truth and to challenge only when the agent is informed. The mechanism is efficient, budget-balanced, exhibits consumer sovereignty, no positive transfer and individual rationality10 . Proof. Challenging without being informed (that is, without providing enough valid records) is always dominated strategy in this mechanism. Now, assume w.l.o.g. Alice is 10 See [29] or [12] for exact definitions. 246 the last to report her value. Alice"s expected payoff gained by underreporting ≤ p · (−C − βp) + (1 − p) · C < p · 0 + (1 − p) · 0 ≤ Alice"s expected payoff if she honestly reports. The right hand side equals zero as the participation costs are negligible. Reasoning back, Bob cannot expect to get the bonus and so misreporting is dominated strategy for him. 5. CONCLUDING REMARKS In this paper we have seen a new partial informational assumption, and we have demonstrated its suitability to networks in which computational agents can easily collect and distribute information. We then described some mechanisms using the concept of iterative elimination of weakly dominated strategies. Some issues for future work include: • As we have seen, the implementation issue in p-informed environments is straightforward - it is easy to construct incentive compatible mechanisms even for non-singleparameter cases. The challenge is to find more realistic scenarios in which the partial informational assumption is applicable. • Mechanisms for information propagation and maintenance. In our examples we choose p such that the maintenance cost over time is negligible. However, the dynamics of the general case is delicate: an agent can use the recorded information to eliminate data that is not likely to be needed, in order to decrease his maintenance costs. As a result, the probability that the environment is informed decreases, and selfish agents would not cooperate. Incentives for information propagation should be considered as well (e.g., for P2P networks for file sharing). • It seems that some social choice goals cannot be implemented if each player is at least 1/n-malicious (where n is the number of players). It would be interesting to identify these cases. Acknowledgements We thank Meitav Ackerman, Moshe Babaioff, Liad Blumrozen, Michal Feldman, Daniel Lehmann, Noam Nisan, Motty Perry and Eyal Winter for helpful discussions. 6. REFERENCES [1] A. Archer and E. Tardos. Truthful mechanisms for one-parameter agents. In IEEE Symposium on Foundations of Computer Science, pages 482-491, 2001. [2] Aaron Archer, Christos Papadimitriou, Kunal Talwar, and Eva Tardos. An approximate truthful mechanism for combinatorial auctions with single parameter agent. In SODA, 2003. [3] Moshe Babaioff, Ron Lavi, and Elan Pavlov. Single-parameter domains and implementation in undominated strategies, 2004. Working paper. [4] Yair Bartal, Rica Gonen, and Noam Nisan. Incentive compatible multi-unit combinatorial auctions, 2003. TARK-03. [5] Sushil Bikhchandani, Shurojit Chatterji, and Arunava Sen. Incentive compatibility in multi-unit auctions, 2003. Working paper. [6] Liad Blumrosen, Noam Nisan, and Ilya Segal. Auctions with severely bounded communication, 2004. Working paper. [7] F. Brandt, T. Sandholm, and Y. Shoham. Spiteful bidding in sealed-bid auctions, 2005. [8] Patrick Briest, Piotr Krysta, and Berthold Voecking. Approximation techniques for utilitarian mechanism design. In STOC, 2005. [9] Chiranjeeb Buragohain, Divy Agrawal, and Subhash Suri. A game-theoretic framework for incentives in p2p systems. In IEEE P2P, 2003. [10] E. H. Clarke. Multipart pricing of public goods. Public Choice, 11:17-33, 1971. [11] Joan Feigenbaum, Christos Papadimitrios, and Scott Shenkar. Sharing the cost of multicast transmissions. Computer and system Sciences, 63(1), 2001. [12] Joan Feigenbaum and Scott Shenker. Distributed algorithmic mechanism design: Recent results and future directions. In Proceedings of the 6th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pages 1-13. ACM Press, New York, 2002. [13] M. Feldman, K. Lai, I. Stoica, and J. Chuang. Robust incentive techniques for peer-to-peer networks. In EC, 2004. [14] A. Goldberg, J. Hartline, A. Karlin, and A. Wright. Competitive auctions, 2004. Working paper. [15] Philippe Golle, Kevin Leyton-Brown, Ilya Mironov, and Mark Lillibridge. Incentives for sharing in peer-to-peer networks. In EC, 2001. [16] Ron Holzman, Noa Kfir-Dahav, Dov Monderer, and Moshe Tennenholtz. Bundling equilibrium in combinatorial auctions. Games and Economic Behavior, 47:104-123, 2004. [17] Ron Holzman and Dov Monderer. Characterization of ex post equilibrium in the vcg combinatorial auctions. Games and Economic Behavior, 47:87-103, 2004. [18] Matthew O. Jackson. A crash course in implementation theory, 1997. mimeo: California Institute of Technology. 25. [19] A. Kothari, D. Parkes, and S. Suri. Approximately-strategyproof and tractable multi-unit auctions. In EC, 2003. [20] Ron Lavi, Ahuva Mu"alem, and Noam Nisan. Towards a characterization of truthful combinatorial auctions. In FOCS, 2003. [21] Ron Lavi and Noam Nisan. Online ascending auctions for gradually expiring goods. In SODA, 2005. [22] Daniel Lehmann, Liadan O"Callaghan, and Yoav Shoham. Truth revelation in approximately efficient combinatorial auctions. Journal of the ACM, 49(5):577-602, 2002. [23] A. Mas-Collel, W. Whinston, and J. Green. Microeconomic Theory. Oxford university press, 1995. [24] Eric Maskin. Nash equilibrium and welfare optimality. Review of Economic Studies, 66:23-38, 1999. [25] Eric Maskin and Tomas Sj¨ostr¨om. Implementation theory, 2002. 247 [26] Aranyak Mehta and Vijay Vazirani. Randomized truthful auctions of digital goods are randomizations over truthful auctions. In EC, 2004. [27] John Moore. Implementation, contract and renegotiation in environments with complete information, 1992. [28] John Moore and Rafael Repullo. Subgame perfect implementation. Econometrica, 56(5):1191-1220, 1988. [29] H. Moulin and S. Shenker. Strategyproof sharing of submodular costs: Budget balance versus efficiency. Economic Theory, 18(3):511-533, 2001. [30] Noam Nisan. Algorithms for selfish agents. In STACS, 1999. [31] Noam Nisan and Amir Ronen. Computationally feasable vcg mechanisms. In EC, 2000. [32] Noam Nisan and Amir Ronen. Algorithmic mechanism design. Games and Economic Behavior, 35:166-196, 2001. [33] M. J. Osborne and A. Rubinstein. A Course in Game Theory. MIT press, 1994. [34] Christos H. Papadimitriou. Algorithms, games, and the internet. In STOC, 2001. [35] Kevin Roberts. The characterization of implementable choice rules. In Jean-Jacques Laffont, editor, Aggregation and Revelation of Preferences. Papers presented at the 1st European Summer Workshop of the Econometric Society, pages 321-349. North-Holland, 1979. [36] Irit Rozenshtrom. Dominant strategy implementation with quasi-linear preferences, 1999. Master"s thesis, Dept. of Economics, The Hebrew University, Jerusalem, Israel. [37] Rakesh Vohra and Rudolf Muller. On dominant strategy mechanisms, 2003. Working paper. [38] Shmuel Zamir. Rationality and emotions in ultimatum bargaining. Annales D" Economie et De Statistique, 61, 2001. 248
distributed algorithmic mechanism design dominant strategy implementation cooperation agent
decentralized incentive compatible mechanism partially informed environment vickrey-clarke-grove distributed environment computational entity iterative elimination of weakly dominated strategy weakly dominated strategy iterative elimination peer-to-peer p-informed environment distribute algorithmic mechanism design