Blackwell's celebrated theorem is a cornerstone of information economics, establishing a necessary and sufficient condition for when a distribution F of posterior means can be induced from a prior G: namely, if and only if F majorizes G. While this result provides a deep understanding of the structure of feasible belief distributions, it is non-constructive and does not explain how to design a signal that achieves a given F.

The literature on strategic communication originated with the influential cheap talk model, which precedes the Bayesian persuasion model by three decades. This model describes an interaction between two agents: sender and receiver. The sender knows some state of the world which the receiver does not know, and tries to influence the receiver's action by communicating a cheap talk message to the receiver.

We study a variant of the principal-agent problem in which the principal does not directly observe the agent's effort outcome; rather, she gets a signal about the agent's action according to a variable information structure designed by a regulator. We consider both the case of a risk-neutral and of a risk-averse agent, focusing mainly on a setting with a limited liability assumption. We ask the following question - which actions and utility profiles can be implemented by some information structure? Surprisingly, even though the principal-agent problem with unobserved outcomes has appeared in previous work, ours is the first work to study the implementability of utility profiles and expected transfers.

We consider the problem of fair division, where a set of indivisible goods should be distributed fairly among a set of agents with combinatorial valuations. To capture fairness, we adopt the notion of shares, where each agent is entitled to a fair share, based on some fairness criterion, and an allocation is considered fair if the value of every agent (weakly) exceeds her fair share. A share-based notion is considered universally feasible if it admits a fair allocation for every profile of monotone valuations. A major question arises: is there a non-trivial share-based notion that is universally feasible? The most well-known share-based notions, namely the proportional share and the maximin share, are not universally feasible, nor are any constant approximations of them.

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.

We study a setting with a decision maker making a binary decision by aggregating information from symmetric agents. Each agent provides the decision maker a recommendation depending on her private signal about the hidden state. We assume that agents are truthful - an agent recommends guessing the more likely state based on her information. This assumption is natural if the agents are unaware of how the decision-maker will aggregate their recommendations. While the decision maker has a prior distribution over the hidden state and knows the marginal distribution of each agent's private signal, the correlation between these signals is chosen adversarially. The decision maker's goal is choosing an information aggregation rule that is robustly optimal.

The celebrated Bayesian persuasion model considers strategic communication between an informed agent (the sender) and uninformed decision makers (the receivers). The current rapidly-growing literature mostly assumes a dichotomy: either the sender is powerful enough to communicate separately with each receiver (a.k.a. private persuasion), or she cannot communicate separately at all (a.k.a. public persuasion). We study a model that smoothly interpolates between the two, by considering a natural multi-channel communication structure in which each receiver observes a subset of the sender's communication channels. This captures, e.g., receivers on a network, where information spillover is almost inevitable. We completely characterize when one communication structure is better for the sender than another, in the sense of yielding higher optimal expected utility universally over all prior distributions and utility functions. The characterization is based on a simple pairwise relation among receivers - one receiver information-dominates another if he observes at least the same channels. We prove that a communication structure $M_1$ is (weakly) better than $M_2$ if and only if every information-dominating pair of receivers in $M_1$ is also such in $M_2$. We also provide an additive FPTAS for the optimal sender's signaling scheme when the number of states is constant and the graph of information-dominating pairs is a directed forest. Finally, we prove that finding an optimal signaling scheme under multi-channel persuasion is, generally, computationally harder than under both public and private persuasion.

We consider a population of Bayesian agents who share a common prior over some finite state space and each agent is exposed to some information about the state. We ask which distributions over empirical distributions of posteriors beliefs in the population are feasible. We provide a necessary and sufficient condition for feasibility. We apply this result in several domains. First, we study the problem of maximizing the polarization of beliefs in a population. Second, we provide a characterization of the feasible agent-symmetric product distributions of posteriors. Finally, we study an instance of a private Bayesian persuasion problem and provide a clean formula for the sender's optimal value.

We consider a model of Bayesian persuasion with one informed sender and several uninformed receivers. The sender can affect receivers' beliefs via private signals and the sender's objective depends on the combination of induced beliefs.

Bayesian persuasion, as introduced by Kamenica and Gentzkow in 2011, is the study of information sharing policies among strategic agents. A prime example is signaling in online ad auctions: what information should a platform signal to an advertiser regarding a user when selling the opportunity to advertise to her? Practical considerations such as preventing discrimination, protecting privacy or acknowledging limited attention of the information receiver impose constraints on information sharing. We propose a simple way to mathematically model such constraints as restrictions on Receiver's admissible posterior beliefs. We consider two families of constraints - ex ante and ex post; the latter limits each instance of Sender-Receiver communication, while the former more general family can also pose restrictions in expectation. For the ex ante family, a result of Doval and Skreta (2018) establishes the existence of an optimal signaling scheme with a small number of signals - at most the number of constraints plus the number of states of nature - and we show this result is tight. For the ex post family, we tighten the previous bound of Vølund (2018), showing that the required number of signals is at most the number of states of nature, as in the original Kamenica-Gentzkow setting. As our main algorithmic result, we provide an additive bi-criteria FPTAS for an optimal constrained signaling scheme assuming a constant number of states of nature; we improve the approximation to single-criteria under a Slater-like regularity condition. The FPTAS holds under standard assumptions, and more relaxed assumptions yield a PTAS. We then establish a bound on the ratio between Sender's optimal utility under convex ex ante constraints and the corresponding ex post constraints. We demonstrate how this result can be applied to find an approximately welfare-maximizing constrained signaling scheme in ad auctions.

We analyze boundedly rational updating from aggregate statistics in a model with binary actions and binary states. Agents each take an irreversible action in sequence after observing the unordered set of previous actions. Each agent first forms her prior based on the aggregate statistic, then incorporates her signal with the prior based on Bayes rule, and finally applies a decision rule that assigns a (mixed) action to each belief. If priors are formed according to a discretized DeGroot rule, then actions converge to the state (in probability), i.e., asymptotic learning, in any informative information structure if and only if the decision rule satisfies probability matching. This result generalizes to unspecified information settings where information structures differ across agents and agents know only the information structure generating their own signal. Also, the main result extends to the case of n states and n actions.

We study a Bayesian persuasion setting with binary actions (adopt and reject) for Receiver. We examine the following question - how well can Sender perform, in terms of persuading Receiver to adopt, when ignorant of Receiver's utility? We take a robust (adversarial) approach to study this problem; that is, our goal is to design signaling schemes for Sender that perform well for all possible Receiver's utilities. We measure performance of signaling schemes via the notion of (additive) regret: the difference between Sender's hypothetically optimal utility had she known Receiver's utility function and her actual utility induced by the given scheme. On the negative side, we show that if Sender has no knowledge at all about Receiver's utility, then Sender has no signaling scheme that performs robustly well. On the positive side, we show that if Sender only knows Receiver's ordinal preferences of the states of nature - i.e., Receiver's utility upon adoption is monotonic as a function of the state - then Sender can guarantee a surprisingly low regret even when the number of states tends to infinity. In fact, we exactly pin down the minimum regret value that Sender can guarantee in this case, which turns out to be at most 1/e. We further show that such positive results are not possible under the alternative performance measure of a multiplicative approximation ratio by proving that no constant ratio can be guaranteed even for monotonic Receiver's utility; this may serve to demonstrate the merits of regret as a robust performance measure that is not too pessimistic. Finally, we analyze an intermediate setting in between the no-knowledge and the ordinal-knowledge settings.

We prove communication complexity lower bounds for (possibly mixed) Nash equilibrium in potential games. In particular, we show that finding a Nash equilibrium requires poly(N) communication in two-player N×N potential games, and 2poly(n)communication in n-player two-action games. To the best of our knowledge, these are the first results to demonstrate hardness in any model of (possibly mixed) Nash equilibrium in potential games.

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.

The canonical Bayesian persuasion setting studies a model where an informed agent, the Sender, can partially share his information with an uninformed agent, the Receiver. The Receiver's utility is a function of the state of nature and the Receiver's action while the Sender's is only a function of the Receiver's action. The classical results characterize the Sender's optimal information disclosure policy whenever the state space is finite. In this paper we study the same setting where the state space is an interval on the real line. We introduce the class of bi-pooling policies and the induced distribution over posteriors which we refer to as bi-pooling distributions. We show that this class of distributions characterizes the set of optimal distributions in the aforementioned setting. Every persuasion problem admits an optimal bi-pooling distribution as a solution. Conversely, for every bi-pooling distribution there exists a persuasion problem in which the given distribution is the unique optimal one. We leverage this result to study the structure of the price function (see [1]) in this setting and to identify optimal information disclosure policies. The full paper can be accessed at https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3511516.

Given a directed forest-graph, a probabilistic selection mechanismis a probability distribution over the vertex set. A selection mechanism is incentive-compatible(IC), if the probability assigned to a vertex does not change when we alter its outgoing edge (or even remove it). The quality of a selection mechanism is the worst-case ratio between the expected progeny under the mechanism's distribution and the maximal progeny in the forest. In this paper we prove an upper bound of 4/5 and a lower bound of 1/łn16 ~0.36 for the quality of any IC selection mechanism. The lower bound is achieved by two novel mechanisms and is a significant improvement to the results of Babichenko et al. (WWW '18). The first, simpler mechanism, has the nice feature of generating distributions which are fair (i.e., monotone and proportional). The downside of this mechanism is that it is not exact (i.e., the probabilities might sum-up to less than 1). Our second, more involved mechanism, is exact but not fair. We also prove an impossibility for an IC mechanism that is both exact and fair and has a positive quality.

We study a communication variant of local search. There is some fixed, commonly known graph G. Alice holds fA and Bob holds fB, both are functions that specify a value for each vertex. The goal is to find a local maximum of fA+fB with respect to G, i.e., a vertex v for which (fA+fB)(v)≥ (fA+fB)(u) for each neighbor u of v.

Our work bridges the literature on incentive-compatible mechanism design and the literature on diffusion algorithms. We introduce the study of finding an incentive-compatible (strategy-proof) mechanism for selecting an influential vertex in a directed graph (e.g. Twitter»s network). The goal is to devise a mechanism with a bounded ratio between the maximal influence and the influence of the selected user, and in which no user can improve its probability of being selected by following or unfollowing other users. We introduce the Two Path mechanism which is based on the idea of selecting the vertex that is the first intersection of two independent random walks in the network. The Two Path mechanism is incentive compatible on directed acyclic graphs (DAGs), and has a finite approximation ratio on natural subfamilies of DAGs. Simulations indicate that this mechanism is suitable for practical uses.

We consider a multi-receivers Bayesian persuasion model where an informed sender tries to persuade a group of receivers to take a certain action. The state of nature is known to the sender, but it is unknown to the receivers. The sender is allowed to commit to a signaling policy where she sends a private signal to every receiver. This work studies the computation aspects of finding a signaling policy that maximizes the sender's revenue. We show that if the sender's utility is a submodular function of the set of receivers that take the desired action, then we can efficiently find a signaling policy whose revenue is at least (1-1/e) times the optimal. We also prove that approximating the sender's optimal revenue by a factor better than (1-1/e) is NP-hard and, hence, the developed approximation guarantee is essentially tight. When the sender's utility is a function of the number of receivers that take the desired action (i.e., the utility function is anonymous), we show that an optimal signaling policy can be computed in polynomial time. Our results are based on an interesting connection between the Bayesian persuasion problem and the evaluation of the concave closure of a set function.

We consider ε-equilibria notions for a constant value of ε in n-player m-action games, where m is a constant. We focus on the following question: What is the largest grid size over the mixed strategies such that ε-equilibrium is guaranteed to exist over this grid.

Bayesian experts with a common prior that are exposed to different evidence possibly make contradicting probabilistic forecasts. A policy maker who receives the forecasts must aggregate them in the best way possible. This is a challenge whenever the policy maker is not familiar with the prior nor the model and evidence available to the experts. We propose a model of non-Bayesian forecast aggregation and adapt the notion of regret as a means for evaluating the policy maker's performance. Whenever experts are Blackwell ordered taking a weighted average of the two forecasts, the weight of which is proportional to its precision (the reciprocal of the variance), is optimal. The resulting regret is equal 1/8(5√ 5-11) approx 0.0225425, which is 3 to 4 times better than naive approaches such as choosing one expert at random or taking the non-weighted average.

We define and study a new variant of the secretary problem. Whereas in the classic setting multiple secretaries compete for a single position, we study the case where the secretaries arrive one at a time and are assigned, in an on-line fashion, to one of multiple positions. Secretaries are ranked according to talent, as in the original formulation, and in addition positions are ranked according to attractiveness. To evaluate an online matching mechanism, we use the notion of blocking pairs from stable matching theory: our goal is to maximize the number of positions (or secretaries) that do not take part in a blocking pair. This is compared with a stable matching in which no blocking pair exists. We consider the case where secretaries arrive randomly, as well as that of an adversarial arrival order, and provide corresponding upper and lower bounds.

We conjecture that PPAD has a PCP-like complete problem, seeking a near equilibrium in which all but very few players have very little incentive to deviate. We show that, if one assumes that this problem requires exponential time, several open problems in this area are settled. The most important implication, proved via a "birthday repetition" reduction, is that the nO(log n) approximation scheme of Lipton et al. [23] for the Nash equilibrium of two-player games is essentially optimum. Two other open problems in the area are resolved once one assumes this conjecture, establishing that certain approximate equilibria are PPAD-complete: Finding a relative approximation of two-player Nash equilibria (without the well-supported restriction of [14]), and an approximate competitive equilibrium with equal incomes [10] with small clearing error and near-optimal Gini coefficient.

We study the query complexity of approximate notions of Nash equilibrium in games with a large number of players n . Our main result states that for n -player binary-action games and for constant ε, the query complexity of an ε-well-supported Nash equilibrium is exponential in n . As a consequence of this result, we get an exponential lower bound on the rate of convergence of adaptive dynamics to approximate Nash equilibria.

We prove that in every normal form n-player game with m actions for each player, there exists an approximate Nash equilibrium in which each player randomizes uniformly among a set of O(log m + log n) pure actions. This result induces an O(N log log N)-time algorithm for computing an approximate Nash equilibrium in games where the number of actions is polynomial in the number of players (m=poly(n)); here N=nmn is the size of the game (the input size). Furthermore, when the number of actions is a fixed constant (m=O(1)) the same algorithm runs in O(Nlog log log N) time. In addition, we establish an inverse connection between the entropy of Nash equilibria in the game, and the time it takes to find such an approximate Nash equilibrium using the random sampling method.

We study the query complexity of approximate notions of Nash equilibrium in games with a large number of players n and a constant number of actions m. Our main result states that even for constant ε, the query complexity of an ε-well-supported Nash equilibrium is exponential in n.

In the musical chairs game $MC(n,m)$, a team of $n$ players plays against an adversarial scheduler. The scheduler wins if the game proceeds indefinitely, while termination after a finite number of rounds is declared a win of the team. At each round of the game each player occupies one of the $m$ available chairs. Termination (and a win of the team) is declared as soon as each player occupies a unique chair. Two players that simultaneously occupy the same chair are said to be in conflict. In other words, termination (and a win for the team) is reached as soon as there are no conflicts. The only means of communication throughout the game is this: At every round of the game, the scheduler selects an arbitrary nonempty set of players who are currently in conflict, and notifies each of them separately that it must move. A player who is thus notified changes its chair according to its deterministic program. As we show, for $m\ge 2n-1$ chairs the team has a winning strategy. Moreover, using topological arguments we show that this bound is tight. For $m\leq 2n-2$ the scheduler has a strategy that is guaranteed to make the game continue indefinitely and thus win. We also have some results on additional interesting questions. For example, if $m \ge 2n-1$ (so that the team can win), how quickly can they achieve victory?