We study the robustness of cheap-talk equilibria to infinitesimal private information of the receiver in a model with a binary state-space and state-independent sender-preferences.

The classic herding model examines the asymptotic behavior of agents who observe their predecessors' actions as well as a private signal from an exogenous information structure. In this paper we introduce a self-interested sender into the model, and study the sender's problem of designing this information structure. If agents cannot observe each other the model reduces to Bayesian persuasion. However, when agents observe predecessors' actions, they may learn from each other, potentially harming the sender. We identify necessary and sufficient conditions under which the sender can nevertheless obtain the same utility as when the agents are unable to observe each other.

Bayes-rational agents reside on a social network. They take binary actions sequentially and irrevocably, and the right action depends on an unobservable state. Each agent receives a bounded private signal about the realized state and observes the actions taken by the neighbors who acted before. How does the network topology affect the ability of agents to aggregate the information dispersed over the population by means of the private signals?

The Bayesian persuasion paradigm of strategic communication models interaction between a privately-informed agent, called the sender, and an ignorant but rational agent, called the receiver. The goal is typically to design a (near-)optimal communication (or signaling) scheme for the sender. It enables the sender to disclose information to the receiver in a way as to incentivize her to take an action that is preferred by the sender. Finding the optimal signaling scheme is known to be computationally difficult in general. This hardness is further exacerbated when there is also a constraint on the size of the message space, leading to NP-hardness of approximating the optimal sender utility within any constant factor. In this paper, we show that in several natural and prominent cases the optimization problem is tractable even when the message space is limited. In particular, we study signaling under a symmetry or an independence assumption on the distribution of utility values for the actions. For symmetric distributions, we provide a novel characterization of the optimal signaling scheme. It results in a polynomial-time algorithm to compute an optimal scheme for many compactly represented symmetric distributions. In the independent case, we design a constant-factor approximation algorithm, which stands in marked contrast to the hardness of approximation in the general case.

We study an information-structure design problem (i.e., a Bayesian persuasion problem) in an online scenario. Inspired by the classic gambler's problem, consider a set of candidates who arrive sequentially and are evaluated by one agent (the sender). This agent learns the value from hiring the candidate to herself as well as the value to another agent, the receiver. The sender provides a signal to the receiver who, in turn, makes an irrevocable decision on whether or not to hire the candidate. A-priori, for each agent the distribution of valuation is independent across candidates but may not be identical. We design good online signaling schemes for the sender. To assess the performance, we compare the expected utility to that of an optimal offline scheme by a prophet sender who knows all candidate realizations in advance. We show an optimal prophet inequality for online Bayesian persuasion, with a 1/2-approximation when the instance satisfies a "satisfactory-status-quo" assumption. Without this assumption, there are instances without any finite approximation factor. We extend the results to combinatorial domains and obtain prophet inequalities for matching with multiple hires and multiple receivers.

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.

In this paper we revisit the basic variant of the classical secretary problem. We propose a new approach in which we separate between an agent that evaluates the secretary performance and one that has to make the hiring decision. The evaluating agent (the sender) signals the quality of the candidate to the hiring agent (the receiver) who must make a decision. Whenever the two agents' interests are not fully aligned, this induces an information transmission (signaling) challenge for the sender. We study the sender's optimization problem subject to persuasiveness constraints of the receiver for several variants of the problem.

We study the intersection signalling control problem for cars with heterogeneous valuations of time (VoT). We are interested in a control algorithm that has some desirable properties: (1) it induces cars to report their VoT truthfully, (2) it minimizes the value of time lost for cars waiting at the intersection, and (3) it is computationally efficient. We obtain three main results: (1) We describe a computationally efficient heuristic forward search approach to solve the static problem. Simulation results show that this method is significantly faster than the dynamic-programming approach to solve the static problem (which is by itself polynomial time). We therefore believe that our algorithm can be commercially implemented. (2) We extend the solution of the static problem to the dynamic case. We couple our algorithm with a carefully designed payment scheme which yields an incentive compatible mechanism. In other words, it is the best interest of each car to truthfully report its VoT. (3) We describe simulation results that compare the social welfare obtained by our scheduling algorithm, as measured by the total value of waiting time, to the social welfare obtained by other intersection signalling control methods.

Society uses the following game to decide on the supply of a public good. Each agent can choose whether or not to contribute to the good. Contributions are collected and the good is supplied whenever total contributions exceed a threshold. We study the case where the public good is excludable, agents have a common value and each agent receives a private signal about the common value. This game models a standard crowdfunding setting as it is executed in popular crowdfunding platforms such as Kickstarter and Indiegogo. We study how well crowdfunding performs from the firm's perspective, in terms of market penetration, and how it performs from the perspective of society, in terms of efficiency.

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.

In the on-line Explore & Exploit [E&E] literature, central to Machine Learning, a central planner is faced with a set of alternatives, each yielding some unknown reward. The planner's goal is to learn the optimal alternative as soon as possible, via experimentation. A typical assumption in this model is that the planner has full control over the experiment design and implementation. When experiments are implemented by a society of self-motivated agents the planner can only recommend experimentation but has no power to enforce it. The first paper to marry the social aspects with the challenge of E&E, a new research domain for which we coin the term "social explore and exploit", is Kremer et. al. [Kremer et al. 2014]. In that work the authors introduce a naive setting (We use the notion of a "naive setting" for settings where the optimal non-social explore and exploit scheme is trivial - try all actions sequentially, each once, and settle on the optimal one thereafter) and study optimal explore and exploit schemes that account for agents' incentives.

We study the implementation challenge in an abstract interdependent values model and an arbitrary objective function. We design a generic mechanism that allows for approximate optimal implementation of insensitive objective functions in ex-post Nash equilibrium. If, furthermore, values are private then the same mechanism is strategy proof. We cast our results onto two specific models: pricing and facility location. The mechanism we design is optimal up to an additive factor of the order of magnitude of one over the square root of the number of agents and involves no utility transfers.

Mechanism design deals with distributed algorithms that are executed with self-interested agents. The designer, whose objective is to optimize some function of the agents private types, needs to construct a computation that takes into account agent incentives which are not necessarily in alignment with the objective of the mechanism. Traditionally, mechanisms are designed for agents who only care about the utility they derive from the mechanism outcome, which often fully or partially discloses their (declared) types. Such mechanisms may become inadequate when agents are privacy-aware, i.e., when their loss of privacy adversely affects their utility. In such cases ignoring privacy-awareness in the design of a mechanism may render it not incentive compatible, and hence inefficient. Interestingly, and somewhat counter-intuitively, Xiao [eprint 2011] has recently showed that this can happen even when the mechanism preserves a strong notion of privacy.