We study when interventions can robustly increase market surplus despite imprecise information about economic primitives, in a setting with many strategic firms possessing market power. The key sufficient condition, recoverable structure, requires large-scale product complementarities. The analysis works by decomposing the incidence of interventions in terms of principal components of a Slutsky matrix. Under recoverable structure, a noisy signal of this matrix reveals enough about these principal components to design robust interventions. Our results demonstrate the utility of spectral methods for analyzing imperfectly observed strategic interactions with many agents.

We consider a group of agents who can each take an irreversible costly action whose payoff depends on an unknown state. Agents learn about the state from private signals, as well as from past actions of their social network neighbors, which creates an incentive to postpone taking the action. We show that outcomes depend on network structure: on networks with a linear structure patient agents do not converge to the first-best action, while on regular directed tree networks they do.

We investigate stochasticity in choice behavior across diverse decisions. Each decision is modeled as a menu of actions with associated outcomes, and a stochastic choice rule assigns probabilities to actions based on the outcome profile. We characterize rules whose predictions are not affected by whether or not additional, irrelevant decisions are included in the model. Our main result is that such rules form the parametric family of mixed-logit rules.

We investigate inherent stochasticity in individual choice behavior across diverse decisions. Each decision is modeled as a menu of actions with outcomes, and a stochastic choice rule assigns probabilities to actions based on the outcome profile. Outcomes can be monetary values, lotteries, or elements of an abstract outcome space. We characterize decomposable rules: those that predict independent choices across decisions not affecting each other. For monetary outcomes, such rules form the one-parametric family of multinomial logit rules. For general outcomes, there exists a universal utility function on the set of outcomes, such that choice follows multinomial logit with respect to this utility. The conclusions are robust to replacing strict decomposability with an approximate version or allowing minor dependencies on the actions' labels. Applications include choice over time, under risk, and with ambiguity.

In a misspecified social learning setting, agents are condescending if they perceive their peers as having private information that is of lower quality than it is in reality. Applying this to a standard sequential model, we show that outcomes improve when agents are mildly condescending. In contrast, too much condescension leads to worse outcomes, as does anti-condescension.

In a private private information structure, agents' signals contain no information about the signals of their peers. We study how informative such structures can be, and characterize those that are on the Pareto frontier, in the sense that it is impossible to give more information to any agent without violating privacy. In our main application, we show how to optimally disclose information about an unknown state under the constraint of not revealing anything about a correlated variable that contains sensitive information.

We study how long-lived, rational, exponentially discounting agents learn in a social network. In every period, each agent observes the past actions of his neighbors, receives a private signal, and chooses an action with the objective of matching the state. Since agents behave strategically, and since their actions depend on higher order beliefs, it is difficult to characterize equilibrium behavior. Nevertheless, we show that regardless of the size and shape of the network, and the patience of the agents, the equilibrium speed of learning is bounded from above by a constant that only depends on the private signal distribution.

The expectation is an example of a descriptive statistic that is monotone with respect to stochastic dominance, and additive for sums of independent random variables. We provide a complete characterization of such statistics, and explore a number of applications to models of individual and group decision-making. These include a representation of stationary, monotone time preferences, extending the work of Fishburn and Rubinstein (1982) to time lotteries, as well as a characterization of risk-averse preferences over monetary gambles that are invariant to mean-zero background risks.

We study the set of possible joint posterior belief distributions of a group of agents who share a common prior regarding a binary state and who observe some information structure. Our main result is that, for the two-agent case, a quantitative version of Aumann's Agreement Theorem provides a necessary and sufficient condition for feasibility. For any number of agents, a related "no-trade" condition likewise provides a characterization of feasibility. We use our characterization to construct joint belief distributions in which agents are informed regarding the state, and yet receive no information regarding the other's posterior. We study a related class of Bayesian persuasion problems with a single sender and multiple receivers, and explore the extreme points of the set of feasible distributions.

We introduce the notion of exploitability in cut-and-choose protocols for repeated cake cutting. If a cut-and-choose protocol is repeated, the cutter can possibly gain information about the chooser from her previous actions, and exploit this information for her own gain, at the expense of the chooser. We define a generalization of cut-and-choose protocols - forced-cut protocols - in which some cuts are made exogenously while others are made by the cutter, and show that there exist non-exploitable forced-cut protocols that use a small number of cuts per day: When the cake has at least as many dimensions as days, we show a protocol that uses a single cut per day. When the cake is 1-dimensional, we show an adaptive non-exploitable protocol that uses 3 cuts per day, and a non-adaptive protocol that uses n cuts per day (where n is the number of days). In contrast, we show that no non-adaptive non-exploitable forced-cut protocol can use a constant number of cuts per day. Finally, we show that if the cake is at least 2-dimensional, there is a non-adaptive non-exploitable protocol that uses 3 cuts per day.

In the classic herding model, agents receive private signals about an underlying binary state of nature, and act sequentially to choose one of two possible actions, after observing the actions of their predecessors. We investigate what types of behaviors lead to asymptotic learning, where agents will eventually converge to the right action in probability. It is known that for rational agents and bounded signals, there will not be asymptotic learning. Does it help if the agents can be cooperative rather than act selfishly? This is simple to achieve if the agents are allowed to use randomized protocols. In this paper, we provide the first deterministic protocol under which asymptotic learning occurs. In addition, our protocol has the advantage of being much simpler than previous protocols.

We consider social learning settings in which a group of agents face uncertainty regarding a state of the world, observe private signals, share the same utility function, and act in a general dynamic setting. We introduce Social Learning Equilibria, a static equilibrium concept that abstracts away from the details of the given dynamics, but nevertheless captures the corresponding asymptotic equilibrium behavior. We establish strong equilibrium properties on agreement, herding, and information aggregation.

We study security games in which a defender commits to a mixed strategy for protecting a finite set of targets of different values. An attacker, knowing the defender's strategy, chooses which target to attack and for how long. If the attacker spends time t at a target i of value αi, and if he leaves before the defender visits the target, his utility is t · ai; if the defender visits before he leaves, his utility is 0. The defender's goal is to minimize the attacker's utility. The defender's strategy consists of a schedule for visiting the targets; it takes her unit time to switch between targets. Such games are a simplified model of a number of real-world scenarios such as protecting computer networks from intruders, crops from thieves, etc. We show that optimal defender play for such security games, although played in continuous time, reduces to the solution of a combinatorial question regarding the existence of infinite sequences over a finite alphabet, with the following properties for each symbol i: (1) i constitutes a prescribed limiting fraction pi of the sequence. (2) The occurrences of i are spread apart close to evenly, in that the ratio of the longest to shortest interval between consecutive occurrences is bounded by a parameter K. We call such sequences K-quasi-regular; a 1-quasi-regular sequence is one in which the occurrences of each symbol form an arithmetic sequence. As we show, a 1-quasi-regular sequence ensures an optimal defender strategy for these security games: the intuition for this fact lies in the famous “inspection paradox.” However, as we demonstrate, for K < 2 and general pi, K-quasi-regular sequences may not exist. Fortunately, this does not turn out to be an obstruction: we show that, surprisingly, 2-quasi-regular sequences also suffice for optimal defender play. What is more, even randomized 2-quasi-regular sequences suffice for optimality. We show that such sequences always exist, and can be calculated efficiently. Thus, we can ensure optimal defender play for these security games. The question of the least K for which deterministic K-quasi-regular sequences exist is fascinating. Using an ergodic theoretical approach, we proceed to show that deterministic 3-quasi-regular sequences always exist (and can be calculated efficiently). We also show that these deterministic 3-regular sequences give rise to a ≈ 1.006-approximation algorithm for the defender's optimal strategy. For 2 ≤ K < 3 we do not know whether deterministic K-quasi-regular sequences always exist; however, when the pi are all small, improved bounds are possible, and in fact, (1 + ∊)-quasi-regular deterministic sequences exist for any ∊ > 0 for sufficiently small pi.

Learning programs is a timely and interesting challenge. In Programming by Example (PBE), a system attempts to infer a program from input and output examples alone, by searching for a composition of some set of base functions. We show how machine learning can be used to speed up this seemingly hopeless search problem, by learning weights that relate textual features describing the provided input-output examples to plausible sub-components of a program. This generic learning framework lets us address problems beyond the scope of earlier PBE systems. Experiments on a prototype implementation show that learning improves search and ranking on a variety of text processing tasks found on help forums.

We study agents in a social network who learn by observing the actions of their neighbors. The agents iteratively estimate an unknown "state of the world" s from initial private signals, and the past actions of their neighbors in the social network. First, we consider a set of Bayesian agents, and investigate the computational problem the agents face in implementing the (myopic) Bayesian decision rule. When private signals are independent conditioned on s, and when the social network graph is a tree, we provide a new `dynamic cavity algorithm' for the agents' calculations, with computational effort that is exponentially lower than what is currently known. We use our algorithm to perform the first numerical simulations of interacting Bayesian agents on networks with hundreds of nodes. Second, we investigate a different model of social learning, with naive agents who practice "majority dynamics", i.e., at each round adopt the majority opinion of their neighbors. Under mild conditions, we show that under majority dynamics, agents learn s with probability 1-ϵ in O(log log (1/ϵ)) rounds. We conjecture that on d-regular trees, myopic Bayesian agents learn s as quickly as agents who practice majority dynamics. Using our algorithm for Bayesian agents, the conjecture implies that the computational effort required of Bayesian agents to learn s is only polylogarithmic in 1/ϵ on d-regular trees. Thus, our results challenge the belief that iterative Bayesian learning is computationally intractable.

We study a model of Bayesian agents in social networks who learn from the actions of their neighbors. Agents attempt to iteratively estimate an unknown `state of the world' s from initial private signals, and the past actions of their neighbors in the network. We investigate the computational problem the agents face in implementing the (myopic) Bayesian decision rule. When private signals are independent conditioned on s, and when the social network graph is a tree, we provide a new `dynamic cavity algorithm' for the agents' calculations, with computational effort that is exponentially lower than a naive dynamic program. We use this algorithm to perform the first numerical simulations of Bayesian agents on networks with hundreds of nodes, and observe rapid learning of s in some settings.