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.

To demonstrate the applicability of our framework, we revisit the problem of implementing a mediator for correlated equilibria (DodisHalevi-Rabin, Crypto'00), and propose a variant of their protocol that is sequentially rational for a non-trivial class of correlated equilibria. Our treatment provides a better understanding of the conditions under which mediators in a correlated equilibrium can be replaced by a stable protocol.

In this work we introduce the notion of partial exposure, in which the players of a simultaneous-move Bayesian game are exposed to the realized types and chosen actions of a subset of the other players. We show that in large simultaneous-move game, each player has very little regret even after being partially exposed to other players. If players are given the opportunity to be exposed to others at the expense of a small decrease in utility, players will decline this opportunity, and the original Nash equilibria of the game will survive.

We study rationality in protocol design for the full-information model, a model characterized by computationally unbounded adversaries, no private communication, and no simultaneity within rounds.  Assuming that players derive some utility from the outcomes of an interaction, we wish to design protocols that are faithful: following the protocol should be an optimal strategy for every player, for various definitions of "optimal" and under various assumptions about the behavior of others and the presence, size, and incentives of coalitions.  We first focus on leader election for players who only care about whether or not they are elected.  We seek protocols that are both faithful and resilient, and for some notions of faithfulness we provide protocols, whereas for others we prove impossibility results.  We then proceed to random sampling, in which the aim is for the players to jointly sample from a set of m items with a distribution that is a function of players' preferences over them.  We construct protocols for m>2 that are faithful and resilient when players are single-minded.  We also show that there are no such protocols for 2 items or for complex preferences.

In a function that takes its inputs from various players, the effect of a player measures the variation he can cause in the expectation of that function. In this paper we prove a tight upper bound on the number of players with a large effect, a bound that holds even when the players' inputs are only known to be pairwise independent. We also study the effect of a set of players, and show that there always exists a "small" set of players that, when eliminated, leaves every small set with little effect. Finally, we ask whether there always exists a player with positive effect, and show that, in general, the answer is negative. More specifically, we show that if the function is nonmonotone or the distribution is only known to be pairwise independent, then it is possible that all players have zero effect.

We consider cryptographic and physical zero-knowledge proof schemes for Sudoku, a popular combinatorial puzzle. We discuss methods that allow one party, the prover, to convince another party, the verifier, that the prover has solved a Sudoku puzzle, without revealing the solution to the verifier. The question of interest is how a prover can show: (i) that there is a solution to the given puzzle, and (ii) that he knows the solution, while not giving away any information about the solution to the verifier.

We argue that in distributed mechanism design frameworks it is important to consider not only rational manipulation by players, but also malicious, faulty behavior. To this end, we show that in some instances it is possible to take a centralized mechanism and implement it in a distributed setting in a fault tolerant manner. More specifically, we examine two distinct models of distributed mechanism design --- a Nash implementation with the planner as a node on the network, and an ex post Nash implementation with the planner only acting as a "bank". For each model we show that the implementation can be made resilient to faults.

A Nash equilibrium is an optimal strategy for each player under the assumption that others play according to their respective Nash strategies. In the presence of irrational players or coalitions of colluding players, however, it provides no guarantees. Some recent literature has focused on measuring the potential damage caused by the presence of faulty behavior, as well as designing mechanisms that are resilient against such faults. In this paper we show that large games are naturally fault tolerant. We first quantify the ways in which two subclasses of large games -- λ-continuous games and anonymous games -- are resilient against Byzantine faults (i.e. irrational behavior), coalitions, and asynchronous play. We then show that general large games also have some non-trivial resilience against faults.

We analyze the variation of prices in a model of an exchange market introduced by Kakade et al. [11], in which buyers and sellers are represented by vertices of a bipartite graph and trade is allowed only between neighbors. In this model the graph is generated probabilistically, and each buyer is connected via preferential attachment to v sellers. We show that even though the tail of the degree distribution of the sellers gets heavier as v increases, the prices at equilibrium decrease exponentially with v. This strengthens the intuition that as the number of vendors available to buyers increases, the prices of goods decrease.

In this note we prove a large deviation bound on the sum of random variables with the following dependency structure: there is a dependency graph G with a bounded chromatic number, in which each vertex represents a random variable. Variables that are represented by neighboring vertices may be arbitrarily dependent, but collections of variables that form an independent set in G are t-wise independent.

We consider the problem of random selection, where p players follow a protocol to jointly select a random element of a universe of size n. However, some of the players may be adversarial and collude to force the output to lie in a small subset of the universe. We describe essentially the first protocols that solve this problem in the presence of a dishonest majority in the full-information model (where the adversary is computationally unbounded and all communication is via non-simultaneous broadcast). Our protocols are nearly optimal in several parameters, including the round complexity (as a function of n), the randomness complexity, the communication complexity, and the tradeoffs between the fraction of honest players, the probability that the output lies in a small subset of the universe, and the density of this subset.

Optimal dispersers have better dependence on the error than optimal extractors. In this paper we give explicit disperser constructions that beat the best possible extractors in some parameters. Our constructions are not strong, but we show that having such explicit strong constructions implies a solution to the Ramsey graph construction problem.

In generic perfect-information games the unique Subgame-Perfect Equilibrium (SPE) outcome is identical to the one predicted by several rationalizability notions, like Extensive-Form Rationalizability (EFR), the Backward Dominance Procedure (BDP), and Extensive-Form Rationalizability of the Agent form (AEFR). We show that, in contrast, within the general class of perfect information games all these solution concepts are genuinely distinct in terms of the outcomes that they predict: SPE is more restrictive than EFR, which is in turn more restrictive than BDP, which is, finally, more restrictive than AEFR.

A decision maker, whose payoff is influenced by an unknown stochastic process, seeks the advice of an advisor, who may be informed about the process. We identify a sufficient condition on the correlation between the advisor's information and the true stochastic process, called conservativeness, for which there exists a strategy D of the decision maker that will yield him an almost first-best payoff in every period. We also demonstrate that without conservativeness no strategy can approximate the first-best payoff.