Search

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.

A large differentiated oligopoly yields inefficient market equilibria. An authority with imprecise information about the primitives of the market aims to design tax/subsidy interventions that increase efficiency robustly, i.e., with high probability. We identify a condition on demand that guarantees the existence of such interventions, and we show how to construct them using noisy estimates of demand complementarities and substitutabilities across products. The analysis works by deriving a novel description of the incidence of market interventions in terms of spectral statistics of a Slutsky matrix. Our notion of recoverable structure ensures that parts of the spectrum that are useful for the design of interventions are statistically recoverable from noisy demand estimates.

Let $\Gamma$ be a finitely generated group, and let $\mu$ be a nondegenerate, finitely supported probability measure on $\Gamma$. We show that every co-compact $\Gamma$ action on a locally compact Hausdorff space admits a nonzero $\mu$-stationary Radon measure. The main ingredient of the proof is a stationary analogue of Tarski's theorem: we show that for every nonempty subset $A \subseteq \Gamma$ there is a $\mu$-stationary, finitely additive measure on $\Gamma$ that assigns unit mass to $A$.

In economies without monetary transfers, token systems serve as an alternative to sustain cooperation, alleviate free riding, and increase efficiency. This paper studies whether a token-based economy can be effective in marketplaces with thin exogenous supply. We consider a marketplace in which at each time period one agent requests a service, one agent provides the service, and one token (artificial currency) is used to pay for service provision. The number of tokens each agent has represents the difference between the amount of service provisions and service requests by the agent. We are interested in the behavior of this economy when very few agents are available to provide the requested service. Since balancing the number of tokens across agents is key to sustain cooperation, the agent with the minimum amount of tokens is selected to provide service among the available agents. When exactly one random agent is available to provide service, we show that the token distribution is unstable. However, already when just two random agents are available to provide service, the token distribution is stable, in the sense that agents' token balance is unlikely to deviate much from their initial endowment, and agents return to their initial endowment in finite expected time. Our results mirror the power of two choices paradigm in load balancing problems. Supported by numerical simulations using kidney exchange data, our findings suggest that token systems may generate efficient outcomes in kidney exchange marketplaces by sustaining cooperation between hospitals., Comment: 32 pages

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., Comment: 49 pages

We introduce asymptotic R\'enyi entropies as a parameterized family of invariants for random walks on groups. These invariants interpolate between various well-studied properties of the random walk, including the growth rate of the group, the Shannon entropy, and the spectral radius. They furthermore offer large deviation counterparts of the Shannon-McMillan-Breiman Theorem. We prove some basic properties of asymptotic R\'enyi entropies that apply to all groups, and discuss their analyticity and positivity for the free group and lamplighter groups., Comment: 25 pages, 1 figure

The Boltzmann distribution is used in statistical mechanics to describe the distribution of states in systems with a given temperature. We give a novel characterization of this distribution as the unique one satisfying independence for uncoupled systems. The theorem boils down to a statement about symmetries of the convolution semigroup of finitely supported probability measures on the natural numbers, or, alternatively, about symmetries of the multiplicative semigroup of polynomials with non-negative coefficients., Comment: 21 pages, 0 figures

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., Comment: 34 pages

We study the coset covering function $\mathfrak{C}(r)$ of a finitely generated group: the number of cosets of infinite index subgroups needed to cover the ball of radius $r$. We show that $\mathfrak{C}(r)$ is of order at least $\sqrt{r}$ for all groups. Moreover, we show that $\mathfrak{C}(r)$ is linear for a class of amenable groups including virtually nilpotent and polycyclic groups, and that it is exponential for property (T) groups., Comment: 12 pages

Private signals model noisy information about an unknown state. Although these signals are called "private," they may still carry information about each other. Our paper introduces the concept of private private signals, which contain information about the state but not about other signals. To achieve privacy, signal quality may need to be sacrificed. We study the informativeness of private private signals and characterize those that are optimal in the sense that they cannot be made more informative without violating privacy. We discuss implications for privacy in recommendation systems, information design, causal inference, and mechanism design.

We study how long-lived, rational agents learn in a social network. In every period, after observing the past actions of his neighbors, each agent receives a private signal, and chooses an action whose payoff depends only on the state. Since equilibrium actions depend on higher order beliefs, it is difficult to characterize behavior. Nevertheless, we show that regardless of the size and shape of the network, the utility function, and the patience of the agents, the speed of learning in any equilibrium is bounded from above by a constant that only depends on the private signal distribution., Comment: 30 pages

Suppliers of differentiated goods make simultaneous pricing decisions, which are strategically linked. Because of market power, the equilibrium is inefficient. We study how a policymaker should target a budget-balanced tax-and-subsidy policy to increase welfare. A key tool is a certain basis for the goods space, determined by the network of interactions among suppliers. It consists of eigenbundles -- orthogonal in the sense that a tax on any eigenbundle passes through only to its own price -- with pass-through coefficients determined by associated eigenvalues. Our basis permits a simple characterization of optimal interventions. A planner maximizing consumer surplus should tax eigenbundles with low pass-through and subsidize ones with high pass-through. The Pigouvian leverage of the system -- the gain in consumer surplus achievable by an optimal tax scheme -- depends only on the dispersion of the eigenvalues of the matrix of strategic interactions. We interpret these results in terms of the network structure of the market.

We show that the automorphism group of every zero entropy infinite shift admits a "drift" homomorphism to $(\mathbb{R},+)$ that maps the shift map to 1. This homomorphism arises as the expectation, under an invariant measure, of a cocycle defined on a space of asymptotic pairs., Comment: 10 pages. Minor corrections with respect to the previous version

We review the theory of information cascades and social learning. Our goal is to describe in a relatively integrated and accessible way the more important themes, insights and applications of the literature as it has developed over the last thirty years. We also highlight open questions and promising directions for further theoretical and empirical exploration.

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. This extension offers a new perspective on risk attitudes toward time, as well as on the aggregation of multiple discount factors. We also offer a novel class of nonexpected utility preferences over gambles which satisfy invariance to background risk as well as betweenness, but are versatile enough to capture mixed risk attitudes., Comment: 59 pages, two figures

We show that under plausible levels of background risk, no theory of choice under risk -- such as expected utility theory, prospect theory, or rank dependent utility -- can simultaneously satisfy the following three economic postulates: (i) Decision makers are risk-averse over small gambles, (ii) they respect stochastic dominance, and (iii) they account for background risk.

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. For two agents we introduce a quantitative version of Aumann's Agreement Theorem, and show that it is equivalent to a characterization of feasible distributions due to Dawid et al. (1995). For any number of agents, we characterize feasible distributions in terms of a "no-trade" condition. We use these characterizations to study information structures with independent posteriors. We also study persuasion problems with multiple receivers, exploring the extreme feasible distributions., Comment: 51 pages

We study monotone homomorphisms on the semigroup of probability measures on $\mathbb{R}$, by which we mean maps to the reals that are monotone with respect to the stochastic order and additive under convolution. We show that scalar multiples of the expectation are the unique monotone homomorphisms on the semigroup of measures with finite $p$-th moment, for any $1 \le p < \infty$. We also prove that the entire semigroup of probability measures admits no non-zero monotone homomorphism.

A probability measure is a characteristic measure of a topological dynamical system if it is invariant to the automorphism group of the system. We show that zero entropy shifts always admit characteristic measures. We use similar techniques to show that automorphism groups of minimal zero entropy shifts are sofic., Comment: 9 pages

We study repeated independent Blackwell experiments; standard examples include drawing multiple samples from a population, or performing a measurement in different locations. In the baseline setting of a binary state of nature, we compare experiments in terms of their informativeness in large samples. Addressing a question due to Blackwell (1951), we show that generically an experiment is more informative than another in large samples if and only if it has higher Renyi divergences. We apply our analysis to the problem of measuring the degree of dissimilarity between distributions by means of divergences. A useful property of Renyi divergences is their additivity with respect to product distributions. Our characterization of Blackwell dominance in large samples implies that every additive divergence that satisfies the data processing inequality is an integral of Renyi divergences., Comment: 57 pages

We say that two unitary or orthogonal representations of a finitely generated group $G$ are additive conjugates if they are intertwined by an additive map, which need not be continuous. We associate to each representation of $G$ a topological action that is a complete additive conjugacy invariant: the action of $G$ by group automorphisms on the Bohr compactification of the underlying Hilbert space. Using this construction we show that the property of having almost invariant vectors is an additive conjugacy invariant. As an application we show that $G$ is amenable if and only if there is a nonzero homomorphism from $L^2(G)$ into $\mathbb{R}/\mathbb{Z}$ that is invariant to the $G$-action., Comment: 16 pages

In an unfriendly coloring of a graph the color of every node mismatches that of the majority of its neighbors. We show that every probability measure preserving Borel graph with finite average degree admits a Borel unfriendly coloring almost everywhere. We also show that every bounded degree Borel graph of subexponential growth admits a Borel unfriendly coloring., Comment: 6 pages

Given a random walk on a free group, we study the random walks it induces on the group's quotients. We show that the spectrum of asymptotic entropies of the induced random walks has no isolated points, except perhaps its maximum.

We develop an axiomatic theory of information acquisition that captures the idea of constant marginal costs in information production: the cost of generating two independent signals is the sum of their costs, and generating a signal with probability half costs half its original cost. Together with Blackwell monotonicity and a continuity condition, these axioms determine the cost of a signal up to a vector of parameters. These parameters have a clear economic interpretation and determine the difficulty of distinguishing states., Comment: 69 pages

May's Theorem (1952), a celebrated result in social choice, provides the foundation for majority rule. May's crucial assumption of symmetry, often thought of as a procedural equity requirement, is violated by many choice procedures that grant voters identical roles. We show that a weakening of May's symmetry assumption allows for a far richer set of rules that still treat voters equally. We show that such rules can have minimal winning coalitions comprising a vanishing fraction of the population, but not less than the square root of the population size. Methodologically, we introduce techniques from group theory and illustrate their usefulness for the analysis of social choice questions., Comment: 43 pages, 5 figures

We study a repeated game with payoff externalities and observable actions where two players receive information over time about an underlying payoff-relevant state, and strategically coordinate their actions. Players learn about the true state from private signals, as well as the actions of others. They commonly learn the true state (Cripps et al., 2008), but do not coordinate in every equilibrium. We show that there exist stable equilibria in which players can overcome unfavorable signal realizations and eventually coordinate on the correct action, for any discount factor. For high discount factors, we show that in addition players can also achieve efficient payoffs.

Stochastic dominance is a crucial tool for the analysis of choice under risk. It is typically analyzed as a property of two gambles that are taken in isolation. We study how additional independent sources of risk (e.g. uninsurable labor risk, house price risk, etc.) can affect the ordering of gambles. We show that, perhaps surprisingly, background risk can be strong enough to render lotteries that are ranked by their expectation ranked in terms of first-order stochastic dominance. We extend our results to second order stochastic dominance, and show how they lead to a novel, and elementary, axiomatization of mean-variance preferences., Comment: 24 pages. Minor changes. Accepted to the Journal of Political Economy

A countable discrete group $G$ is called Choquet-Deny if for every non-degenerate probability measure $\mu$ on $G$ it holds that all bounded $\mu$-harmonic functions are constant. We show that a finitely generated group $G$ is Choquet-Deny if and only if it is virtually nilpotent. For general countable discrete groups, we show that $G$ is Choquet-Deny if and only if none of its quotients has the infinite conjugacy class property. Moreover, when $G$ is not Choquet-Deny, then this is witnessed by a symmetric, finite entropy, non-degenerate measure., Comment: 14 pages. Minor error corrections and changes to definitions, wording and notation

A group is said to be strongly amenable if each of its proximal topological actions has a fixed point. We show that a finitely generated group is strongly amenable if and only if it is virtually nilpotent. More generally, a countable discrete group is strongly amenable if and only if none of its quotients have the infinite conjugacy class property., Comment: 20 pages, 3 figures. Some minor corrections to the proofs

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.

In the classical herding literature, agents receive a private signal regarding a binary state of nature, and sequentially choose an action, after observing the actions of their predecessors. When the informativeness of private signals is unbounded, it is known that agents converge to the correct action and correct belief. We study how quickly convergence occurs, and show that it happens more slowly than it does when agents observe signals. However, we also show that the speed of learning from actions can be arbitrarily close to the speed of learning from signals. In particular, the expected time until the agents stop taking the wrong action can be either finite or infinite, depending on the private signal distribution. In the canonical case of Gaussian private signals we calculate the speed of convergence precisely, and show explicitly that, in this case, learning from actions is significantly slower than learning from signals., Comment: Forthcoming in the Journal of Economic Theory

We study invariant random subgroups (IRSs) of semidirect products $G = A \rtimes \Gamma$. In particular, we characterize all IRSs of parabolic subgroups of $\mathrm{SL}_d(\mathbb{R})$, and show that all ergodic IRSs of $\mathbb{R}^d \rtimes \mathrm{SL}_d(\mathbb{R})$ are either of the form $\mathbb{R}^d \rtimes K$ for some IRS of $\mathrm{SL}_d(\mathbb{R})$, or are induced from IRSs of $\Lambda \rtimes \mathrm{SL}(\Lambda)$, where $\Lambda < \mathbb{R}^d$ is a lattice., Comment: 16 pages

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 $\alpha_i$, and if he leaves before the defender visits the target, his utility is $t \cdot \alpha_i $; 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 this continuous time security games 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 fraction $p_i$ 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. We show that, surprisingly, $2$-quasi-regular sequences 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. The question of the least $K$ for which deterministic $K$-quasi-regular sequences exist is fascinating. Using an ergodic theoretical approach, we show that deterministic $3$-quasi-regular sequences always exist. For $2 \leq K < 3$ we do not know whether deterministic $K$-quasi-regular sequences always exist., Comment: to appear in Proc. of SODA 2018

We show that Thompson's group $F$ has a topological action on a compact metric space that is proximal and has no fixed points., Comment: Accepted to Ergodic Theory and Dynamical Systems

We introduce the notion of weak containment for stationary actions of a countable group and define a natural topology on the space of weak equivalence classes. We prove that Furstenberg entropy is an invariant of weak equivalence, and moreover that it descends to a continuous function on the space of weak equivalence classes., Comment: The proof of Theorem 4.6 in the previous version contained a gap, and we withdraw that claim. All the other results are still valid, including in particular the invariance of Furstenberg entropy under weak equivalence

We show that every normal amenable subgroup of the automorphism group of the full shift is contained in its center. This follows from the analysis of this group's Furstenberg topological boundary, through the construction of a minimal and strongly proximal action. We extend this result to higher dimensional full shifts. This also provides a new proof of Ryan's Theorem and of the fact that these groups contain free groups.

Let $G$ be a finitely generated amenable group. We study the space of shifts on $G$ over a given finite alphabet $A$. We show that the zero entropy shifts are generic in this space, and that more generally the shifts of entropy $c$ are generic in the space of shifts with entropy at least $c$. The same is shown to hold for the space of transitive shifts and for the space of weakly mixing shifts. As applications of this result, we show that for every entropy value $c \in [0,\log |A|]$ there is a weakly mixing subshift of $A^G$ with entropy $c$. We also show that the set of strongly irreducible shifts does not form a $G_\delta$ in the space of shifts, and that all non-trivial, strongly irreducible shifts are non-isolated points in this space.

We study how long-lived rational agents learn from repeatedly observing a private signal and each others' actions. With normal signals, a group of any size learns more slowly than just four agents who directly observe each others' private signals in each period. Similar results apply to general signal structures. We identify rational groupthink---in which agents ignore their private signals and choose the same action for long periods of time---as the cause of this failure of information aggregation.

We show that the "grandfather graph" has the following property: it is the unique completion to a transitive graph of a large enough finite subgraph of itself., Comment: 6 pages

We establish a new characterization of property (T) in terms of the Furstenberg entropy of nonsingular actions. Given any generating measure $\mu$ on a countable group $G$, A. Nevo showed that a necessary condition for $G$ to have property (T) is that the Furstenberg $\mu$-entropy values of the ergodic, properly nonsingular $G$-actions are bounded away from zero. We show that this is also a sufficient condition., Comment: 10 pages

In majority dynamics, agents located at the vertices of an undirected simple graph update their binary opinions synchronously by adopting those of the majority of their neighbors. On infinite unimodular transitive graphs (e.g., Cayley graphs), when initial opinions are chosen from a distribution that is invariant with respect to the graph automorphism group, we show that the opinion of each agent almost surely either converges, or else eventually oscillates with period two; this is known to hold for finite graphs, but not for all infinite graphs. On Erd\H{o}s-R\'enyi random graphs with degrees $\Omega(\sqrt{n})$, we show that when initial opinions are chosen i.i.d. then agents all converge to the initial majority opinion, with constant probability. Conversely, on random 4-regular finite graphs, we show that with high probability different agents converge to different opinions., Comment: 19 pages