Ronen Gradwohl

Assistant Professor
MEDS, Kellogg School of Management
Electrical Engineering and Computer Science (courtesy)
Northwestern University

 


 

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
847-467-0943
r-gradwohl 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 enhancements---reducing the likelihood of leakage and decreasing the level of informational interdependence---have opposite effects on the volume of information sharing, and that although they always seem beneficial to non-strategic 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 requirement---requiring committee members' actions to be observable---on 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 information-disclosure 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 non-monotonic effect on both the accuracy of the decision and the welfare of the voters. In particular, the first-best accuracy is often attained at the extremes---in open voting, when all information is disclosed, and in secret voting, when no information is disclosed---but 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 privacy-protecting implementation, while typically impossible with normal-form mechanisms, is achievable with extensive-form 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 non-trivial 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 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.


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.


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.
        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.


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.

Refereed Conference Proceedings


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.


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 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.