Search

A basic lesson from game theory is that strategic behavior often renders the equilibrium outcome inefficient. The recent literature of information design -- a.k.a. signaling or persuasion -- looks to improve equilibria by providing carefully-tuned information to players in order to influence their actions. Most previous studies have focused on the question of designing optimal signaling schemes. This work departs from previous research by considering a descriptive question and looks to quantitatively characterize the power of signaling (PoS), i.e., how much a signaling designer can improve her objective of the equilibrium outcome. We consider four signaling schemes with increasing power: full information, optimal public signaling, optimal private signaling and optimal ex-ante private signaling. Our main result is a clean and tight characterization of the additional power each signaling scheme has over its immediate predecessor above in the broad classes of cost-minimization and payoff-maximization games where: (1) all players minimize non-negative cost functions or maximize non-negative payoff functions; (2) the signaling designer (naturally) optimizes the sum of players' utilities. We prove that the additional power of signaling -- defined as the worst-case ratio between the equilibrium objectives of two consecutive signaling schemes in the above list -- is bounded precisely by the well-studied notion of the price of anarchy of the corresponding games. Moreover, we show that all these bounds are tight.

We study the computation of equilibria in prediction markets in perhaps the most fundamental special case with two players and three trading opportunities. To do so, we show equivalence of prediction market equilibria with those of a simpler signaling game with commitment introduced by Kong and Schoenebeck (2018). We then extend their results by giving computationally efficient algorithms for additional parameter regimes. Our approach leverages a new connection between prediction markets and Bayesian persuasion, which also reveals interesting conceptual insights.

We propose and study Collpasing Bandits, a new restless multi-armed bandit (RMAB) setting in which each arm follows a binary-state Markovian process with a special structure: when an arm is played, the state is fully observed, thus "collapsing" any uncertainty, but when an arm is passive, no observation is made, thus allowing uncertainty to evolve. The goal is to keep as many arms in the "good" state as possible by planning a limited budget of actions per round. Such Collapsing Bandits are natural models for many healthcare domains in which workers must simultaneously monitor patients and deliver interventions in a way that maximizes the health of their patient cohort. Our main contributions are as follows: (i) Building on the Whittle index technique for RMABs, we derive conditions under which the Collapsing Bandits problem is indexable. Our derivation hinges on novel conditions that characterize when the optimal policies may take the form of either "forward" or "reverse" threshold policies. (ii) We exploit the optimality of threshold policies to build fast algorithms for computing the Whittle index, including a closed-form. (iii) We evaluate our algorithm on several data distributions including data from a real-world healthcare task in which a worker must monitor and deliver interventions to maximize their patients' adherence to tuberculosis medication. Our algorithm achieves a 3-order-of-magnitude speedup compared to state-of-the-art RMAB techniques while achieving similar performance.

We consider a monopoly information holder selling information to a budget-constrained decision maker, who may benefit from the seller's information. The decision maker has a utility function that depends on his action and an uncertain state of the world. The seller and the buyer each observe a private signal regarding the state of the world, which may be correlated with each other. The seller's goal is to sell her private information to the buyer and extract maximum possible revenue, subject to the buyer's budget constraints. We consider three different settings with increasing generality, i.e., the seller's signal and the buyer's signal can be independent, correlated, or follow a general distribution accessed through a black-box sampling oracle. For each setting, we design information selling mechanisms which are both optimal and simple in the sense that they can be naturally interpreted, have succinct representations, and can be efficiently computed. Notably, though the optimal mechanism exhibits slightly increasing complexity as the setting becomes more general, all our mechanisms share the same format of acting as a consultant who recommends the best action to the buyer but uses different and carefully designed payment rules for different settings. Each of our optimal mechanisms can be easily computed by solving a single polynomial-size linear program. This significantly simplifies exponential-size LPs solved by the Ellipsoid method in the previous work, which computes the optimal mechanisms in the same setting but without budget limit. Such simplification is enabled by our new characterizations of the optimal mechanism in the (more realistic) budget-constrained setting.

Neutral atoms have been observed to survive intense laser pulses in high Rydberg states with surprisingly large probability. Only with this Rydberg-state excitation (RSE) included is the picture of intense-laser-atom interaction complete. Various mechanisms have been proposed to explain the underlying physics. However, neither one can explain all the features observed in experiments and in time-dependent Schr\"{o}dinger equation (TDSE) simulations. Here we propose a fully quantum-mechanical model based on the strong-field approximation (SFA). It well reproduces the intensity dependence of RSE obtained by the TDSE, which exhibits a series of modulated peaks. They are due to recapture of the liberated electron and the fact that the pertinent probability strongly depends on the position and the parity of the Rydberg state. We also present measurements of RSE in xenon at 800 nm, which display the peak structure consistent with the calculations., Comment: 11 pages, 8 figures

Persuasion studies how a principal can influence agents' decisions via strategic information revelation --- often described as a signaling scheme --- in order to yield the most desirable equilibrium outcome. Recently, there has been a large body of algorithmic study of designing optimal public signaling schemes, a.k.a., public persuasion, which however is rifle with computational intractability results. In this paper, we design efficient and tight algorithms for public persuasion, and focus on a fundamental multi-agent persuasion model with no inter-agent externalities and binary actions introduced by Arieli and Babichenko. En route, we develop new algorithmic techniques which may be of independent interests. First, we prove that optimal public persuasion is fixed parameter tractable. Our main result here relies on an interesting connection to a basic question in combinatorial geometry: how many cells can $n$ hyperplanes divide $R^d$ into? We use this connection to show a new characterization of public persuasion, which then enables efficient algorithm design. Second, we relax agent incentives and show that optimal public persuasion admits a bi-criteria PTAS for monotone submodular objectives and this approximation is tight. To prove this result, we establish an intriguing "noise stability" property of submodular functions which strictly generalizes the key result of Cheraghchi et al., originally motivated by applications of learning submodular functions and differential privacy. Finally, motivated by automated persuasion implemented as software, we consider relaxing the equilibrium concept of the model to coarse correlated equilibrium. Here we use a sophisticated primal-dual analysis to establish the polynomial-time equivalence between optimal public persuasion and the combinatorial problem of directly maximizing the sender's objective minus any linear function., Comment: Appeared at SODA 2020

Motivated by economic applications such as recommender systems, we study the behavior of stochastic bandits algorithms under \emph{strategic behavior} conducted by rational actors, i.e., the arms. Each arm is a \emph{self-interested} strategic player who can modify its own reward whenever pulled, subject to a cross-period budget constraint, in order to maximize its own expected number of times of being pulled. We analyze the robustness of three popular bandit algorithms: UCB, $\varepsilon$-Greedy, and Thompson Sampling. We prove that all three algorithms achieve a regret upper bound $\mathcal{O}(\max \{ B, K\ln T\})$ where $B$ is the total budget across arms, $K$ is the total number of arms and $T$ is length of the time horizon. This regret guarantee holds under \emph{arbitrary adaptive} manipulation strategy of arms. Our second set of main results shows that this regret bound is \emph{tight} -- in fact for UCB it is tight even when we restrict the arms' manipulation strategies to form a \emph{Nash equilibrium}. The lower bound makes use of a simple manipulation strategy, the same for all three algorithms, yielding a bound of $\Omega(\max \{ B, K\ln T\})$. Our results illustrate the robustness of classic bandits algorithms against strategic manipulations as long as $B=o(T)$.

Routine operational use of sensitive data is often governed by law and regulation. For instance, in the medical domain, there are various statues at the state and federal level that dictate who is permitted to work with patients' records and under what conditions. To screen for potential privacy breaches, logging systems are usually deployed to trigger alerts whenever suspicious access is detected. However, such mechanisms are often inefficient because 1) the vast majority of triggered alerts are false positives, 2) small budgets make it unlikely that a real attack will be detected, and 3) attackers can behave strategically, such that traditional auditing mechanisms cannot easily catch them. To improve efficiency, information systems may invoke signaling, so that whenever a suspicious access request occurs, the system can, in real time, warn the user that the access may be audited. Then, at the close of a finite period, a selected subset of suspicious accesses are audited. This gives rise to an online problem in which one needs to determine 1) whether a warning should be triggered and 2) the likelihood that the data request event will be audited. In this paper, we formalize this auditing problem as a Signaling Audit Game (SAG), in which we model the interactions between an auditor and an attacker in the context of signaling and the usability cost is represented as a factor of the auditor's payoff. We study the properties of its Stackelberg equilibria and develop a scalable approach to compute its solution. We show that a strategic presentation of warnings adds value in that SAGs realize significantly higher utility for the auditor than systems without signaling. We illustrate the value of the proposed auditing model and the consistency of its advantages over existing baseline methods.

Cellular micromotors are attractive for locally delivering high concentrations of drug and targeting hard-to-reach disease sites such as cervical cancer and early ovarian cancer lesions by non-invasive means. Spermatozoa are highly efficient micromotors perfectly adapted to traveling up the female reproductive system. Indeed, bovine sperm-based micromotors have recently been reported as a potential candidate for the drug delivery toward gynecological cancers of clinical unmet need. However, due to major differences in the molecular make-up of bovine and human sperm, a key translational bottleneck for bringing this technology closer to the clinic is to transfer this concept to human sperm. Here, we successfully load human sperm with a chemotherapeutic drug and perform treatment of relevant 3D cervical cancer and patient-representative 3D ovarian cancer cell cultures, resulting in strong anti-cancer effects. Additionally, we show the subcellular localization of the chemotherapeutic drug within human sperm heads and assess drug effects on sperm motility and viability over time. Finally, we demonstrate guidance and release of human drug-loaded sperm onto cancer cell cultures by using streamlined microcap designs capable of simultaneously carrying multiple human sperm towards controlled drug dosing by transporting known numbers of sperm loaded with defined amounts of chemotherapeutic drug.

Information uncertainty is one of the major challenges facing applications of game theory. In the context of Stackelberg games, various approaches have been proposed to deal with the leader's incomplete knowledge about the follower's payoffs, typically by gathering information from the leader's interaction with the follower. Unfortunately, these approaches rely crucially on the assumption that the follower will not strategically exploit this information asymmetry, i.e., the follower behaves truthfully during the interaction according to their actual payoffs. As we show in this paper, the follower may have strong incentives to deceitfully imitate the behavior of a different follower type and, in doing this, benefit significantly from inducing the leader into choosing a highly suboptimal strategy. This raises a fundamental question: how to design a leader strategy in the presence of a deceitful follower? To answer this question, we put forward a basic model of Stackelberg games with (imitative) follower deception and show that the leader is indeed able to reduce the loss due to follower deception with carefully designed policies. We then provide a systematic study of the problem of computing the optimal leader policy and draw a relatively complete picture of the complexity landscape; essentially matching positive and negative complexity results are provided for natural variants of the model. Our intractability results are in sharp contrast to the situation with no deception, where the leader's optimal strategy can be computed in polynomial time, and thus illustrate the intrinsic difficulty of handling follower deception. Through simulations we also examine the benefit of considering follower deception in randomly generated games.