We study the use of Bayesian persuasion (i.e., strategic use of information disclosure signaling) in endogenous team formation. This is an important consideration in settings such as crowdsourcing competitions, open science challenges and group-based assignments, where a large number of agents organize themselves into small teams which then compete against each other. A central tension here is between the strategic interests of agents who want to have the highest-performing team, and that of the principal who wants teams to be balanced. Moreover, although the principal cannot choose the teams or modify rewards, she often has additional knowledge of agents' abilities, and can leverage this information asymmetry to provide signals that influence team formation. Our work uncovers the critical role of self-awareness (i.e., knowledge of one's own abilities) for the design of such mechanisms. For settings with two-member teams and binary-valued agents partitioned into a constant number of prior classes, we provide signaling mechanisms which are asymptotically optimal when agents are agnostic of their own abilities. On the other hand, when agents are self-aware, then we show that there is no signaling mechanism that can do better than not releasing information, while satisfying agent participation constraints.
In the context of multi-agent settings with no externalities, Arieli and Babichenko @cite_10 look at a model where the principal is trying to persuade individuals to adopt a product by sending signals. They characterize the optimal policy for supermodular, submodular, and supermajority utility functions of the principal. More recent work has been devoted to proving hardness or inefficacy results for finding the optimal information disclosure policy in such settings @cite_12 @cite_6 .
@cite_10 @cite_6 @cite_12
2615774546 2064032144
We study the algorithmics of information structure design --- a.k.a. persuasion or signaling --- in a fundamental special case introduced by Arieli and Babichenko: multiple agents, binary actions, and no inter-agent externalities. Unlike prior work on this model, we allow many states of nature. We assume that the principal's objective is a monotone set function, and study the problem both in the public signal and private signal models, drawing a sharp contrast between the two in terms of both efficacy and computational complexity. When private signals are allowed, our results are largely positive and quite general. First, we use linear programming duality and the equivalence of separation and optimization to show polynomial-time equivalence between (exactly) optimal signaling and the problem of maximizing the objective function plus an additive function. This yields an efficient implementation of the optimal scheme when the objective is supermodular or anonymous. Second, we exhibit a (1-1 e)-approximation of the optimal private signaling scheme, modulo an additive loss of e, when the objective function is submodular. These two results simplify, unify, and generalize results of [Arieli and Babichenko, 2016] and [Babichenko and Barman, 2016], extending them from a binary state of nature to many states (modulo the additive loss in the latter result). Third, we consider the binary-state case with a submodular objective, and simplify and slightly strengthen the result of [Babichenko and Barman, 2016] to obtain a (1-1 e)-approximation via a scheme which (i) signals independently to each receiver and (ii) is "oblivious" in that it does not depend on the objective function so long as it is monotone submodular. When only a public signal is allowed, our results are negative. First, we show that it is NP-hard to approximate the optimal public scheme, within any constant factor, even when the objective is additive. Second, we show that the optimal private scheme can outperform the optimal public scheme, in terms of maximizing the sender's objective, by a polynomial factor. There has been a recent surge of interest in the role of information in strategic interactions. Much of this work seeks to understand how the realized equilibrium of a game is influenced by uncertainty in the environment and the information available to players in the game. Lurking beneath this literature is a fundamental, yet largely unexplored, algorithmic question: how should a "market maker" who is privy to additional information, and equipped with a specified objective, inform the players in the game? This is an informational analogue of the mechanism design question, and views the information structure of a game as a mathematical object to be designed, rather than an exogenous variable. We initiate a complexity-theoretic examination of the design of optimal information structures in general Bayesian games, a task often referred to as signaling. We focus on one of the simplest instantiations of the signaling question: Bayesian zero-sum games, and a principal who must choose an information structure maximizing the equilibrium payoff of one of the players. In this setting, we show that optimal signaling is computationally intractable, and in some cases hard to approximate, assuming that it is hard to recover a planted clique from an Erdos-Renyi random graph. This is despite the fact that equilibria in these games are computable in polynomial time, and therefore suggests that the hardness of optimal signaling is a distinct phenomenon from the hardness of equilibrium computation. Necessitated by the non-local nature of information structures, en-route to our results we prove an "amplification lemma" for the planted clique problem which may be of independent interest. Specifically, we show that even if we plant many cliques in an Erdos-Renyi random graph, so much so that most nodes in the graph are in some planted clique, recovering a constant fraction of the planted cliques is no easier than the traditional planted clique problem.