I am a game
theorist with a background in computer science working at a business school.
My current research focuses on strategic issues surrounding privacy
regulation and transparency requirements, as well as complexity and
decentralization. Recently I’ve also become interested in game
theoretic aspects of machine learning and AI.
Contact
Kellogg Global Hub 4189
2211 Campus Drive
Evanston, IL 60208
8474670943
rgradwohl at kellogg dot
northwestern dot edu
Working
Papers
 Privacy in Repeated Games, with Rann Smorodinsky.
 Decentralized
Advice,
with Tim Feddersen.
 Information
Sharing and Privacy in Networks.
Extended abstract in EC 2017.
Users of social, economic, or medical networks share personal
information in exchange for tangible benefits, but may be harmed by
leakage and misuse of the shared information. I analyze the effect of
enhancing privacy in the presence of two opposing forces: network
effects and informational interdependencies. I show that two privacy
enhancementsreducing the likelihood of leakage and decreasing the
level of informational interdependencehave opposite effects on the
volume of information sharing, and that although they always seem
beneficial to nonstrategic users, both privacy enhancements may
backfire when users are strategic.
Journal
Publications
An advisory committee with common values and asymmetric information provides
a recommendation to a decision maker facing a binary choice. We investigate
the effect of a transparency requirementrequiring committee members'
actions to be observableon the committee's ability to influence the
decision maker. We show that unless the preferences of the committee and
decision maker are sufficiently close, requiring transparency eliminates the
committee's ability to provide any useful information. In contrast, if
preferences are very close or if committee members are able to verifiably
reveal their signals then transparency is beneficial.
When committees make decisions, the voting rule that determines the outcome
is coupled with one of three informationdisclosure rules: open voting, in
which each committee member's individual vote is revealed; anonymous voting,
in which only an anonymized tally is publicized; and secret voting, in which
only the outcome is disclosed. I focus on strategic voters who care about
maintaining the privacy of their vote, and show that, despite these privacy
concerns, the amount of information disclosed has a nonmonotonic effect on
both the accuracy of the decision and the welfare of the voters. In
particular, the firstbest accuracy is often attained at the extremesin
open voting, when all information is disclosed, and in secret voting, when no
information is disclosedbut is never attained in anonymous voting, when
some but not all information is disclosed. Furthermore, while welfare is
always minimal in open voting, it is sometimes maximal in anonymous rather
than secret voting.
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
private information. In this paper I consider the problem of full
implementation with agents who may prefer to protect their privacy. I show
that privacyprotecting implementation, while typically impossible with
normalform mechanisms, is achievable with extensiveform mechanisms.
Players have privacy concerns that may affect their choice of actions in
strategic settings. We use a variant of signaling games to model this effect
and study its relation to pooling behavior, misrepresentation of information,
and inefficiency.
Two players choose whether to cooperate on a project. Each of them is endowed
with some evidence, and if both possess a sufficient amount then cooperation
is profitable. In order to facilitate cooperation the players reveal evidence
to one another. However, some players are concerned about privacy, and so
revelation of evidence that does not result in cooperation is costly.
We show that in equilibrium evidence can be exchanged both incrementally and
all at once, and identify conditions under which the different rates of
evidence exchange are optimal.
We propose to strengthen Popper's notion of falsifiability by adding the
requirement that when an observation is inconsistent with a theory, there
must be a "short proof" of this inconsistency. We model the concept
of a short proof using tools from computational complexity, and provide some
examples of economic theories that are falsifiable in the usual sense but not
with this additional requirement. We consider several variants of the
definition of "short proof" and several assumptions about the
difficulty of computation, and study their different implications on the
falsifiability of theories.
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 nontrivial resilience against faults.
Much of the literature on rational cryptography focuses on analyzing the
strategic properties of cryptographic protocols. However, due to the presence
of computationallybounded 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 threatfree
Nash equilibrium that is more permissive but still eliminates the undesirable
"empty threats" of nonsequential solution concepts.
To demonstrate the applicability of our
framework, we revisit the problem of implementing a mediator for correlated
equilibria (DodisHaleviRabin, Crypto'00), and propose a variant of their
protocol that is sequentially rational for a nontrivial 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 simultaneousmove Bayesian game are exposed to the realized
types and chosen actions of a subset of the other players. We show that in
large simultaneousmove 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.
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 zeroknowledge 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 scratchoff 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
â€œlaypeopleâ€ and implementable without
the use of computers.
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
twise independent.
Refereed
Conference Proceedings
We study rationality in protocol design for the fullinformation 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 singleminded. We also show
that there are no such protocols for 2 items or for complex preferences.
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.
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.
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 fullinformation model (where the adversary is computationally unbounded
and all communication is via nonsimultaneous 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.
