Title: Language Barriers

Private information about language competence drives a wedge between the indicative meanings of messages (i.e. the sets of states indicated by those messages) and their imperative meanings (i.e. the actions induced by those messages). Even when sender and receiver have common interests, optimal use of an imperfectly shared language subverts both the indicative and imperative meanings of utterances: Messages convey both directly payoff relevant information and instrumental information about the sender's language competence. Furthermore the actions induced by messages depend on the receiver's uncertain ability to decode them. With conflict of interest, an imperfectly shared language can substitute for mediated communication.

Title: Approximate Privacy: Foundations and Quantification

Increasing use of computers and networks in business, government, recreation, and almost all aspects of daily life has led to a proliferation of online sensitive data about individuals and organizations. Consequently, concern about the privacy of these data has become a top priority, particularly those data that are created and used in electronic commerce. Despite many careful formulations and extensive study, there are still open questions about the feasibility of maintaining meaningful privacy in realistic networked environments. We formulate communication-complexity-based definitions, both worst-case and average-case, of a problem's privacy-approximation ratio. We use our definitions to investigate the extent to which approximate privacy is achievable in many well studied contexts: the 2nd-price Vickrey auction [20], the millionaires problem of Yao [22], the pro- visioning of a public good, and also set disjointness and set intersection. We present both positive and negative results and many interesting directions for future research.

Title: Short Non-Interactive Cryptographic Proofs

We propose a Vickrey auction scheme in which discreet proofs are used both to commit the bidder to a bid and also to hide that bid from others, including the auctioneer. In order to determine the winner, the auctioneer calls out successively lower legal bids and ask if anyone has bid at least that amount. When the called threshold equals the highest bid, the highest bidder is expected to respond in the affirmative. This process continues until the highest and second highest bidder have been identified. At that point, both are required to open their bids. The remaining bidders do not ever open their bids, but they are required to prove, using a discreet proof, that their own bids do not exceed the announced second highest bid. This maintains the privacy of their bid while allowing all parties to check that the announced highest and second highest bids are indeed correct.

A discreet proof is a cryptographic object that contains a Boolean circuit, encrypted input bits, visible output bits, and additional data that serves to prove that the visible outputs are the correct values produced by the circuit when evaluated on the hidden input bits. Applied to auctions, the hidden input bits encode the sealed bid. The Boolean circuit computes the less-than-or-equal function and enables a privacy-preserving proof that the hidden values are less than or equal to the announced second highest bid. A construction for short discreet proofs appears in the paper,

Joint work with Joan Boyar, Ivan Damgad, and Rene Peralta

Title: The Role of Commitment in Bilateral Trade

Using mechanism design, we examine the buyer-seller problem under different levels of commitment. The seller is informed of the quality of the good, which affects both his cost and the buyer's valuation, but the buyer is not. We characterize the payoffs that can be achieved in a mechanism in which, unlike with full commitment, the buyer has the option to walk away after observing a given offer. We further characterize the equilibrium payoffs that can be achieved in the bargaining game in which the seller makes all the offers, as the discount factor goes to one. This allows us to identify how different levels of commitment affect outcomes, and which constraints, if any, preclude efficiency.

Joint work with Dino Gerardi and Lucas Maestri

Title: Asynchronous Distributed Computing with Adaptive Heuristics

Internet protocols, large-scale markets, social networks, and multi-processor computer architectures are dynamic environments where computational nodes, or decision makers, repeatedly interact. Game theory provides a useful tool to help analyze these kinds of interactions, but such analysis has so far primarily concentrated on synchronous environments in which steps take place simultaneously or in a known, prescribed order.

We explore the convergence of dynamics to an equilibrium in asynchronous computational environments. We use ideas from distributed computing to exhibit a general non-termination result for a broad class of dynamics based on adaptive heuristics, even if system components are guaranteed not to fail. Our approach resembles the classic distributed computing result of Fischer, Lynch, and Paterson, but neither result is a special case of the other. We consider implications of our result across a wide variety of interesting and timely applications: game dynamics, asynchronous circuits, diffusion of technologies in social networks, and networking. We also present some basic observations that show that other kinds of dynamics, such as regret-minimizing dynamics, are more robust to asynchrony.

Joint work with Michael Schapira and Rebecca N. Wright.

Title: Effective Communication in Cheap Talk Games

This paper studies cheap talk games by imposing a monotonicity condition on Sender strategies and then applies iterative deletion of weakly dominated strategies. This procedure selects among Crawford and Sobel (1982) equilibria, typically selecting the outcome with the maximal number of induced actions. Other refinements, such as NITS, select the same outcome. It also predicts that Senders will inflate their communication using only relatively high messages in equilibrium.

Joint work with Joel Sobel

Title: Rational Secret Sharing: A Survey

One goal at the intersection of game theory and cryptography is to model participants in a distributed (cryptographic) protocol as rational entities, in the hopes of both circumventing known impossibility results (by relying on self-interested, rather than byzantine, behavior) as well as offering a more realistic picture of real-world behavior (in which altruism may not be present). This line of work has so far reached its greatest success in the study of rational secret sharing, where all players wish to reconstruct a secret while preventing other players from doing so. This talk will offer a survey of this area, focusing on both the protocols themselves as well as the development of appropriate definitions of rationality for this setting.

Title: Inefficiency of equilibria in query auctions with continuous valuations

Query auctions are iterative auctions in which bidders have to select in each round an action from a finite set. We show that, when bidders have continuous valuations, any ex post implementation of the Vickrey outcome in a query auction has a running time that is infinite for almost all realizations of valuations of the bidders. We also show that, under mild individual rationality constraints, any ex post efficient ex post equilibrium of a query auction does indeed implement the Vickrey auction, so that the result applies to any such individually rational query auction. Another direct consequence is that, when valuations are drawn from a continuous probability distribution, efficiency can only be bought at the expense of a running time that is infinite with probability one. For two bidders we even show this to be true when we only require efficiency with probability one.

Title: Detecting Profitable Deviations

This paper finds necessary and sufficient conditions for implementability as well as interim implementability in a quasi-linear context with arbitrary type spaces. By viewing an agent's deviation gains as payments in a hypothetical zero-sum game between a principal and an agent, I show that an allocation is (i) implementable if and only if every profitable deviation is detectable, and (ii) interim implementable if and only if every infinitesimally detectable deviation is at most infinitesimally profitable. I also provide several natural extensions of these results, including complete characterizations of revenue equivalence (both ex post and interim), budget balanced implementation, bargaining with interdependent values, moral hazard, optimal mechanisms, surplus extraction, and revealed stochastic preference.

Title: Mechanism Design and Communication Networks

This paper studies a mechanism design model where the players and the designer are nodes in a communication network. We characterize the communication networks (directed graphs) for which, in any environment (utilities and beliefs), every incentive compatible social choice function is implementable. We show that any incentive compatible social choice function is implementable on a given communication network, in all environments with either common independent beliefs and private values or a worst outcome, if and only if the network is strongly connected and weakly 2-connected. A network is strongly connected if for each player, there exists a directed path to the designer. It is weakly 2- connected if each player is either directly connected to the designer or indirectly connected to the designer through two disjoint paths, not necessarily directed. We couple encryption techniques together with appropriate incentives to secure the transmission of each player's private information to the designer.

Title: Sequential Rationality in Cryptographic Protocols

Much of the literature on rational cryptography focuses on analyzing the strategic properties of cryptographic protocols. However, due to the presence of computationally-bounded players and the asymptotic nature of cryptographic security, a definition of sequential rationality for this setting has thus far eluded researchers.

We propose a new framework for overcoming these obstacles, and provide the first definitions of computational solution concepts that guarantee sequential rationality. We argue that natural computational variants of subgame perfection are too strong for cryptographic protocols. As an alternative, we introduce a weakening called threat-free Nash equilibrium that is more permissive but still eliminates the undesirable ``empty threats'' of non-sequential solution concepts.

Joint work with Ronen Gradwohl and Noam Livne.

Title: When is it best to best-reply?

We consider computational and economic environments in which the interaction between agents takes the form of *best-response dynamics*, that is, each agent continuously selects its best action with respect to the others' most recent actions (examples include Internet protocols, global markets, and more). Often, in such contexts, obedient execution of best-response dynamics has no strategic justification. We address the following natural question: " *When is myopic best-replying the best course of action for each agent in the long run?*". That is, when is best-response dynamics strategically justified? We present subclasses of games for which best-replying is indeed incentive compatible. Our results have interesting implications for Internet protocols, auctions, cost-sharing mechanisms, matching, and more.

Joint work with Noam Nisan, Greg Valiant and Aviv Zohar.

Title: Mediated Contracts and Mechanism Design

This note relates the mechanisms that are based on mediated contracts of Rahman and Obara (2010) to the mechanisms of Myerson (1982). It shows that the mechanisms in Myerson (1982) are more general in that they encompass the mechanisms based on mediated contracts. It establishes an equivalence between the two classes if mediated contracts are allowed to be stochastic.

Rump Session:

Lucia Draque Penso: Conversions in Social Networks

In this talk, we analyse some interesting conversion problems arising in social networks. Hardness results and efficient algorithms are discussed.

Tal Moran: Botnet-resistant Time-lock puzzles

Jing Chen: How to boost the classical Vickrey auction for multiple copies of a single good to get more revenue.

Depending on the players' knowledge about each other, the mechanism we propose guarantees revenue which is at least that of the Vickrey auction, and can be as high as the maximum social welfare. The solution concept we use is a new notion of rationalizability defined by us. I'll talk about the solution concept also.

Edmund Wong: It's On Me! The Benefit of Altruism in BAR Environments

Cooperation, a necessity for any peer-to-peer (P2P) cooperative service, is often achieved by rewarding good behavior now with the promise of future benefits. However, in most cases, interactions with a particular peer or the service itself eventually end, resulting in some last exchange in which departing participants have no incentive to contribute. Without cooperation in the last round, cooperation in any prior round may be unachievable. In this paper, we propose leveraging altruistic participants that simply follow the protocol as given. We show that altruism is a simple, necessary, and sufficient way to incentivize cooperation in a realistic model of a cooperative service's last exchange, in which participants may be Byzantine, altruistic, or rational and network loss is explicitly considered. By focusing on network-level incentives in the last exchange, we believe our approach can be used as the cornerstone for incentivizing cooperation in any cooperative service.

Tim van Zandt: Complexity in macroeconomics and financial markets.

Aniket Ket: Distributed Key Generation for Use over the Internet

Although distributed key generation (DKG) has been studied for some time, it has never been examined outside of the synchronous setting. In this talk, I will present the first realistic DKG implementation for use over the Internet. We observed the necessity of Byzantine agreement for DKG in the asynchronous communication setting and analyzed the difficulty of using a randomized agreement protocol for it. Using an asynchronous verifiable secret sharing scheme and a leader-based agreement protocol, we then designed a provably secure DKG protocol. To establish the efficiency and the reliability of our protocol over the Internet, we implemented and tested it on the PlanetLab platform. We also considered cryptographic properties such as uniform randomness of the shared secret and defined provably secure protocols for the same. Our DKG system will be a useful primitive for any multi-party computation over the Internet in the discrete logarithm setting.

This is a joint work Ian Goldberg.

David Rahman (rump): Approaching Wilson's Doctrine