- Privacy in Implementation.
[paper]
[abstract]
In most implementation frameworks agents care only about the outcome,
and not at all about the way in which it was obtained. Additionally, typical mechanisms for full implementation involve the
complete revelation of all pri- vate information to the planner. In this paper we consider the problem of full
implementation with agents who may prefer to protect their privacy and reveal as little of their private information as possible.
We analyze the extent to which privacy-protecting mechanisms can be constructed under various assumptions about agents'
predilection for privacy and the permissible game forms.
- How to Buy Advice, with Yuval Salant.
[paper]
[abstract]
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.
- Rationality and Equilibrium in Perfect-Information Games, with Aviad Heifetz.
[paper]
[abstract]
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, Þnally, more restrictive than AEFR.
- Partial Exposure in Large Games, with Omer Reingold (2010).
Games and Economic Behavior 68(2): 602-613.
[paper]
[abstract]
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.
- Players' Effects under Limited Independence, with Omer Reingold, Ariel Yadin, and Amir Yehudayoff (2009).
Mathematics of Operations Research 34(4): 971-980.
[paper]
[abstract]
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.
- Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzles,
with Moni Naor, Benny Pinkas, and Guy N. Rothblum (2009).
Theory of Computing Systems 44: 245-266.
[paper]
[abstract]
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.
In this paper we consider several protocols that achieve these goals.
Broadly speaking, the protocols are either cryptographic or physical. By a cryptographic protocol we mean one in the usual model
found in the foundations of cryptography literature. In this model, two machines exchange messages, and the security of the protocol
relies on computational hardness. By a physical protocol we mean one that is implementable by humans using common objects, and
preferably without the aid of computers. In particular, our physical protocols utilize items such as scratch-off cards, similar to
those used in lotteries, or even just simple playing cards.
The cryptographic protocols are direct and efficient, and do not involve a reduction to other problems.
The physical protocols are meant to be understood by Òlay-peopleÓ and implementable without the use of computers.
- t-Wise Independence with Local Dependencies, with Amir Yehudayoff (2008).
Information Processing Letters 106: 208-212.
[paper]
[abstract]
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.
- Sequential Rationality in Cryptographic Protocols, with Noam Livne and Alon Rosen. In FOCS 2010.
[paper]
[abstract]
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 (Dodis-Halevi-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.
- Rationality in the Full-Information Model. In TCC 2010.
[paper]
[abstract]
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.
- Fault Tolerance in Distributed Mechanism Design. In WINE 2008.
[paper]
[abstract]
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.
- Fault Tolerance in Large Games, with Omer Reingold. In EC 2008.
[paper]
[abstract]
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.
- Price Variation in a Bipartite Exchange Network. In SAGT 2008.
[paper]
[abstract]
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.
- Random Selection with an Adversarial Majority, with Salil P. Vadhan and David Zuckerman. In CRYPTO 2006.
[paper]
[abstract]
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.
- On the Error Parameter of Dispersers, with Guy Kindler, Omer Reingold, and Amnon Ta-Shma. In RANDOM 2005.
[paper]
[abstract]
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.
