Haifeng Xu

TMLR Journal 2026 Journal Article

GenAI vs. Human Creators: Procurement Mechanism Design in Two-/Three-Layer Markets

• Rui Ai
• David Simchi-Levi
• Haifeng Xu

With the rapid advancement of generative AI (GenAI), mechanism design adapted to its unique characteristics poses new theoretical and practical challenges. Unlike traditional goods, content from one domain can enhance the training and performance of GenAI models in other domains. For example, OpenAI’s video generation model Sora (Liu et al., 2024b) relies heavily on image data to improve video generation quality. In this work, we study nonlinear procurement mechanism design under data transferability, where online platforms employ both human creators and GenAI to satisfy cross-domain content demand. We propose optimal mechanisms that maximize either platform revenue or social welfare and identify the specific properties of GenAI that make such high-dimensional design problems tractable. Our analysis further reveals which domains face stronger competitive pressure and which tend to experience overproduction. Moreover, the growing role of data intermediaries, including labeling companies such as Scale AI and creator organizations such as The Wall Street Journal, introduces a third layer into the traditional platform–creator structure. We show that this three-layer market can result in a lose-lose outcome, reducing both platform revenue and social welfare, as large pre-signed contracts distort creators’ incentives and lead to inefficiencies in the data market. These findings suggest a need for government regulation of the GenAI data ecosystem, and our theoretical insights are further supported by numerical simulations.

AAAI Conference 2026 Conference Paper

The Publication Choice Problem

• Haichuan Wang
• Yifan Wu
• Haifeng Xu

Researchers strategically choose where to submit their work in order to maximize its impact, and these publication decisions in turn determine venues' impact factors. To analyze how individual publication choices both respond to and shape venue impact, we introduce a game-theoretic framework - coined the Publication Choice Problem - that captures this two‐way interplay. We show the existence of a pure-strategy equilibrium in the Publication Choice Problem and its uniqueness under binary researcher types. Our characterizations of the equilibrium properties offer insights about what publication behaviors better indicate a researcher's impact level. Through equilibrium analysis, we further investigate how labeling papers with ``spotlight'' affects the impact factor of venues in the research community. Our analysis shows that competitive venue labeling top papers with ``spotlight'' may decrease the overall impact of other venues in the community, while less competitive venues with ``spotlight'' labeling have an opposite impact.

SODA Conference 2025 Conference Paper

A Reduction from Multi-Parameter to Single-Parameter Bayesian Contract Design

• Matteo Castiglioni
• Junjie Chen
• Minming Li
• Haifeng Xu
• Song Zuo

NeurIPS Conference 2025 Conference Paper

Accelerated Distance-adaptive Methods for Hölder Smooth and Convex Optimization

• Yijin Ren
• Haifeng Xu
• Qi Deng

This paper introduces new parameter-free first-order methods for convex optimization problems in which the objective function exhibits Hölder smoothness. Inspired by the recently proposed distance-over-gradient (DOG) technique, we propose an accelerated distance-adaptive method which achieves optimal anytime convergence rates for Hölder smooth problems without requiring prior knowledge of smoothness parameters or explicit parameter tuning. Importantly, our parameter-free approach removes the necessity of specifying target accuracy in advance, addressing a significant limitation found in the universal fast gradient methods(Nesterov, 2015). We further present a parameter-free accelerated method that eliminates the need for line-search procedures and extend it to convex stochastic optimization. Preliminary experimental results highlight the effectiveness of our approach in convex nonsmooth problems and its advantages over existing parameter-free or accelerated methods.

ICML Conference 2025 Conference Paper

An Instrumental Value for Data Production and its Application to Data Pricing

• Rui Ai 0002
• Boxiang Lyu
• Zhaoran Wang 0001
• Zhuoran Yang
• Haifeng Xu

We develop a framework for capturing the instrumental value of data production processes, which accounts for two key factors: (a) the context of the agent’s decision-making; (b) how much data or information the buyer already possesses. We "micro-found" our data valuation function by establishing its connection to classic notions of signals and information design in economics. When instantiated in Bayesian linear regression, our value naturally corresponds to information gain. Applying our proposed data value in Bayesian linear regression for monopoly pricing, we show that if the seller can fully customize data production, she can extract the first-best revenue (i. e. , full surplus) from any population of buyers, i. e. , achieving first-degree price discrimination. If data can only be constructed from an existing data pool, this limits the seller’s ability to customize, and achieving first-best revenue becomes generally impossible. However, we design a mechanism that achieves seller revenue at most $\log(\kappa)$ less than the first-best, where $\kappa$ is the condition number associated with the data matrix. As a corollary, the seller extracts the first-best revenue in the multi-armed bandits special case.

ICLR Conference 2025 Conference Paper

Learning from Imperfect Human Feedback: A Tale from Corruption-Robust Dueling

• Yuwei Cheng
• Fan Yao 0002
• Xuefeng Liu
• Haifeng Xu

This paper studies Learning from Imperfect Human Feedback (LIHF), addressing the potential irrationality or imperfect perception when learning from comparative human feedback. Building on evidences that human's imperfection decays over time (i.e., humans learn to improve), we cast this problem as a concave-utility continuous-action dueling bandit but under a restricted form of corruption: i.e., the corruption scale is decaying over time as $t^{\rho-1}$ for some ``imperfection rate'' $\rho \in [0, 1]$. With $T$ as the total number of iterations, we establish a regret lower bound of $ \Omega(\max\{\sqrt{T}, T^{\rho}\})$ for LIHF, even when $\rho$ is known. For the same setting, we develop the Robustified Stochastic Mirror Descent for Imperfect Dueling (RoSMID) algorithm, which achieves nearly optimal regret $\tilde{\mathcal{O}}(\max\{\sqrt{T}, T^{\rho}\})$. Core to our analysis is a novel framework for analyzing gradient-based algorithms for dueling bandit under corruption, and we demonstrate its general applicability by showing how this framework can be easily applied to obtain corruption-robust guarantees for other popular gradient-based dueling bandit algorithms. Our theoretical results are validated by extensive experiments.

NeurIPS Conference 2025 Conference Paper

Learning Personalized Ad Impact via Contextual Reinforcement Learning under Delayed Rewards

• Yuwei Cheng
• Zifeng Zhao
• Haifeng Xu

Online advertising platforms use automated auctions to connect advertisers with potential customers, requiring effective bidding strategies to maximize profits. Accurate ad impact estimation requires considering three key factors: delayed and long-term effects, cumulative ad impacts such as reinforcement or fatigue, and customer heterogeneity. However, these effects are often not jointly addressed in previous studies. To capture these factors, we model ad bidding as a Contextual Markov Decision Process (CMDP) with delayed Poisson rewards. For efficient estimation, we propose a two-stage maximum likelihood estimator combined with data-splitting strategies, ensuring controlled estimation error based on the first-stage estimator's (in)accuracy. Building on this, we design a reinforcement learning algorithm to derive efficient personalized bidding strategies. This approach achieves a near-optimal regret bound of $\tilde{\mathcal{O}}(dH^2\sqrt{T})$, where $d$ is the contextual dimension, $H$ is the number of rounds, and $T$ is the number of customers. Our theoretical findings are validated by simulation experiments.

IJCAI Conference 2025 Conference Paper

Mechanism Design for Large Language Models (Extended Abstract)

• Paul Dütting
• Vahab Mirrokni
• Renato Paes Leme
• Haifeng Xu
• Song Zuo

We investigate auction mechanisms for AI-generated content, focusing on applications like ad creative generation. In our model, agents' preferences over stochastically generated content are encoded as large language models (LLMs). We propose an auction format that operates on a token-by-token basis, and allows LLM agents to influence content creation through single dimensional bids. We formulate two desirable incentive properties and prove their equivalence to a monotonicity condition on output aggregation. This equivalence enables a second-price rule design, even absent explicit agent valuation functions. Our design is supported by demonstrations on a publicly available LLM.

UAI Conference 2025 Conference Paper

Robust Optimization with Diffusion Models for Green Security

• Lingkai Kong
• Haichuan Wang
• Yuqi Pan
• Cheol Woo Kim
• Mingxiao Song
• Alayna Nguyen
• Tonghan Wang 0001
• Haifeng Xu

In green security, defenders must forecast adversarial behavior-such as poaching, illegal logging, and illegal fishing-to plan effective patrols. These behavior are often highly uncertain and complex. Prior work has leveraged game theory to design robust patrol strategies to handle uncertainty, but existing adversarial behavior models primarily rely on Gaussian processes or linear models, which lack the expressiveness needed to capture intricate behavioral patterns. To address this limitation, we propose a conditional diffusion model for adversary behavior modeling, leveraging its strong distribution-fitting capabilities. To the best of our knowledge, this is the first application of diffusion models in the green security domain. Integrating diffusion models into game-theoretic optimization, however, presents new challenges, including a constrained mixed strategy space and the need to sample from an unnormalized distribution to estimate utilities. To tackle these challenges, we introduce a mixed strategy of mixed strategies and employ a twisted Sequential Monte Carlo (SMC) sampler for accurate sampling. Theoretically, our algorithm is guaranteed to converge to an \(\epsilon\)-equilibrium with high probability using a finite number of iterations and samples. Empirically, we evaluate our approach on both synthetic and real-world poaching datasets, demonstrating its effectiveness.

AAAI Conference 2025 Conference Paper

Sample Complexity of Linear Regression Models for Opinion Formation in Networks

• Haolin Liu
• Rajmohan Rajaraman
• Ravi Sundaram
• Anil Kumar Vullikanti
• Omer Wasim
• Haifeng Xu

Consider public health officials aiming to spread awareness about a new vaccine in a community interconnected by a social network. How can they distribute information with minimal resources, so as to avoid polarization and ensure community-wide convergence of opinion? To tackle such challenges, we initiate the study of sample complexity of opinion formation in networks. Our framework is built on the recognized opinion formation game, where we regard each agent’s opinion as a data-derived model, unlike previous works that treat opinions as data-independent scalars. The opinion model for every agent is initially learned from its local samples and evolves game-theoretically as all agents communicate with neighbors and revise their models towards an equilibrium. Our focus is on the sample complexity needed to ensure that the opinions converge to an equilibrium such that every agent’s final model has low generalization error. Our paper has two main technical results. First, we present a novel polynomial time optimization framework to quantify the total sample complexity for arbitrary networks, when the underlying learning problem is (generalized) linear regression. Second, we leverage this optimization to study the network gain which measures the improvement of sample complexity when learning over a network compared to that in isolation. Towards this end, we derive network gain bounds for various network classes including cliques, star graphs, and random regular graphs. Additionally, our framework provides a method to study sample distribution within the network, suggesting that it is sufficient to allocate samples inversely to the degree. Empirical results on both synthetic and real-world networks strongly support our theoretical findings.

ICLR Conference 2025 Conference Paper

Single-agent Poisoning Attacks Suffice to Ruin Multi-Agent Learning

• Fan Yao 0002
• Yuwei Cheng
• Ermin Wei
• Haifeng Xu

We investigate the robustness of multi-agent learning in strongly monotone games with bandit feedback. While previous research has developed learning algorithms that achieve last-iterate convergence to the unique Nash equilibrium (NE) at a polynomial rate, we demonstrate that all such algorithms are vulnerable to adversaries capable of poisoning even a single agent's utility observations. Specifically, we propose an attacking strategy such that for any given time horizon $T$, the adversary can mislead any multi-agent learning algorithm to converge to a point other than the unique NE with a corruption budget that grows sublinearly in $T$. To further understand the inherent robustness of these algorithms, we characterize the fundamental trade-off between convergence speed and the maximum tolerable total utility corruptions for two example algorithms, including the state-of-the-art one. Our theoretical and empirical results reveal an intrinsic efficiency-robustness trade-off: the faster an algorithm converges, the more vulnerable it becomes to utility poisoning attacks. To the best of our knowledge, this is the first work to identify and characterize such a trade-off in the context of multi-agent learning.

ICML Conference 2025 Conference Paper

Tokenized Bandit for LLM Decoding and Alignment

• Suho Shin 0001
• Chenghao Yang 0001
• Haifeng Xu
• MohammadTaghi Hajiaghayi

We introduce the tokenized linear bandit (TLB) and multi-armed bandit (TMAB), variants of linear and stochastic multi-armed bandit problems inspired by LLM decoding and alignment. In these problems, at each round $t \in [T]$, a user submits a query (context), and the decision maker (DM) sequentially selects a token irrevocably from a token set. Once the sequence is complete, the DM observes a random utility from the user, whose expectation is presented by a sequence function mapping the chosen token sequence to a nonnegative real value that depends on the query. In both problems, we first show that learning is impossible without any structure on the sequence function. We introduce a natural assumption, diminishing distance with more commons (DDMC), and propose algorithms with regret $\tilde{O}(L\sqrt{T})$ and $\tilde{O}(L\sqrt{T^{2/3}})$ for TLB and TMAB, respectively. As a side product, we obtain an (almost) optimality of the greedy decoding for LLM decoding algorithm under DDMC, which justifies the unresaonable effectiveness of greedy decoding in several tasks. This also has an immediate application to decoding-time LLM alignment, when the misaligned utility can be represented as the frozen LLM’s utility and a linearly realizable latent function. We finally validate our algorithm’s performance empirically as well as verify our assumptions using synthetic and real-world datasets.

AIJ Journal 2024 Journal Article

An extensive study of security games with strategic informants

• Weiran Shen
• Minbiao Han
• Weizhe Chen
• Taoan Huang
• Rohit Singh
• Haifeng Xu
• Fei Fang

Over the past years, game-theoretic modeling for security and public safety issues (also known as security games) have attracted intensive research attention and have been successfully deployed in many real-world applications for fighting, e. g. , illegal poaching, fishing and urban crimes. However, few existing works consider how information from local communities would affect the structure of these games. In this paper, we systematically investigate how a new type of players – strategic informants who are from local communities and may observe and report upcoming attacks – affects the classic defender-attacker security interactions. Characterized by a private type, each informant has a utility structure that drives their strategic behaviors. For situations with a single informant, we capture the problem as a 3-player extensive-form game and develop a novel solution concept, Strong Stackelberg-perfect Bayesian equilibrium, for the game. To find an optimal defender strategy, we establish that though the informant can have infinitely many types in general, there always exists an optimal defense plan using only a linear number of patrol strategies; this succinct characterization then enables us to efficiently solve the game via linear programming. For situations with multiple informants, we show that there is also an optimal defense plan with only a linear number of patrol strategies that admits a simple structure based on plurality voting among multiple informants. Finally, we conduct extensive experiments to study the effect of the strategic informants and demonstrate the efficiency of our algorithm. Our experiments show that the existence of such informants significantly increases the defender's utility. Even though the informants exhibit strategic behaviors, the information they supply holds great value as defensive resources. Compared to existing works, our study leads to a deeper understanding on the role of informants in such defender-attacker interactions.

AAMAS Conference 2024 Conference Paper

Attacking Multi-Player Bandits and How to Robustify Them

• Shivakumar Mahesh
• Anshuka Rangi
• Haifeng Xu
• Long Tran-Thanh

Motivated by cognitive radios, stochastic Multi-Player Multi-Armed Bandits has been extensively studied in recent years. In this setting, each player pulls an arm, and receives a reward corresponding to the arm if there is no collision, namely the arm was selected by one single player. Otherwise, the player receives no reward if collision occurs. In this paper, we consider the presence of malicious players (or attackers) who obstruct the cooperative players (or defenders) from maximizing their rewards, by deliberately colliding with them. We provide the first decentralized and robust algorithm RESYNC for defenders whose performance deteriorates gracefully as ˜ 𝑂(𝐶) as the number of collisions 𝐶 from the attackers increases. We show that this algorithm is order-optimal by proving a lower bound which scales as Ω(𝐶). This algorithm is agnostic to the algorithm used by the attackers and agnostic to the number of collisions 𝐶 faced from attackers.

ICLR Conference 2024 Conference Paper

Bandits Meet Mechanism Design to Combat Clickbait in Online Recommendation

• Thomas Kleine Buening
• Aadirupa Saha
• Christos Dimitrakakis
• Haifeng Xu

We study a strategic variant of the multi-armed bandit problem, which we coin the strategic click-bandit. This model is motivated by applications in online recommendation where the choice of recommended items depends on both the click-through rates and the post-click rewards. Like in classical bandits, rewards follow a fixed unknown distribution. However, we assume that the click-rate of each arm is chosen strategically by the arm (e.g., a host on Airbnb) in order to maximize the number of times it gets clicked. The algorithm designer does not know the post-click rewards nor the arms' actions (i.e., strategically chosen click-rates) in advance, and must learn both values over time. To solve this problem, we design an incentive-aware learning algorithm, UCB-S, which achieves two goals simultaneously: (a) incentivizing desirable arm behavior under uncertainty; (b) minimizing regret by learning unknown parameters. We approximately characterize all Nash equilibria of the arms under UCB-S and show a $\tilde{\mathcal{O}} (\sqrt{KT})$ regret bound uniformly in every equilibrium. We also show that incentive-unaware algorithms generally fail to achieve low regret in the strategic click-bandit. Finally, we support our theoretical results by simulations of strategic arm behavior which confirm the effectiveness and robustness of our proposed incentive design.

ECAI Conference 2024 Conference Paper

Escape Sensing Games: Detection-vs-Evasion in Security Applications

• Niclas Boehmer
• Minbiao Han
• Haifeng Xu
• Milind Tambe

Traditional game-theoretic research for security applications primarily focuses on the allocation of external protection resources to defend targets. This work puts forward the study of a new class of games centered around strategically arranging targets to protect them against a constrained adversary, with motivations from varied domains such as peacekeeping resource transit and cybersecurity. Specifically, we introduce Escape Sensing Games (ESGs). In ESGs, a blue player manages the order in which targets pass through a channel, while her opponent tries to capture the targets using a set of sensors that need some time to recharge after each activation. We present a thorough computational study of ESGs. Among others, we show that it is NP-hard to compute best responses and equilibria. Nevertheless, we propose a variety of effective (heuristic) algorithms whose quality we demonstrate in extensive computational experiments.

ICML Conference 2024 Conference Paper

Human vs. Generative AI in Content Creation Competition: Symbiosis or Conflict?

• Fan Yao 0002
• Chuanhao Li 0002
• Denis Nekipelov
• Hongning Wang
• Haifeng Xu

The advent of generative AI (GenAI) technology produces a transformative impact on the content creation landscape, offering alternative approaches to produce diverse, good-quality content across media, thereby reshaping online ecosystems but also raising concerns about market over-saturation and the potential marginalization of human creativity. Our work introduces a competition model generalized from the Tullock contest to analyze the tension between human creators and GenAI. Our theory and simulations suggest that despite challenges, a stable equilibrium between human and AI-generated content is possible. Our work contributes to understanding the competitive dynamics in the content creation industry, offering insights into the future interplay between human creativity and technological advancements in GenAI.

ICLR Conference 2024 Conference Paper

Incentivized Truthful Communication for Federated Bandits

• Zhepei Wei
• Chuanhao Li 0002
• Tianze Ren
• Haifeng Xu
• Hongning Wang

To enhance the efficiency and practicality of federated bandit learning, recent advances have introduced incentives to motivate communication among clients, where a client participates only when the incentive offered by the server outweighs its participation cost. However, existing incentive mechanisms naively assume the clients are truthful: they all report their true cost and thus the higher cost one participating client claims, the more the server has to pay. Therefore, such mechanisms are vulnerable to strategic clients aiming to optimize their own utility by misreporting. To address this issue, we propose an incentive compatible (i.e., truthful) communication protocol, named Truth-FedBan, where the incentive for each participant is independent of its self-reported cost, and reporting the true cost is the only way to achieve the best utility. More importantly, Truth-FedBan still guarantees the sub-linear regret and communication cost without any overhead. In other words, the core conceptual contribution of this paper is, for the first time, demonstrating the possibility of simultaneously achieving incentive compatibility and nearly optimal regret in federated bandit learning. Extensive numerical studies further validate the effectiveness of our proposed solution.

NeurIPS Conference 2024 Conference Paper

Intrinsic Robustness of Prophet Inequality to Strategic Reward Signaling

• Wei Tang
• Haifeng Xu
• Ruimin Zhang
• Derek Zhu

Prophet inequality concerns a basic optimal stopping problem and states that simple threshold stopping policies --- i. e. , accepting the first reward larger than a certain threshold --- can achieve tight $\frac{1}{2}$-approximation to the optimal prophet value. Motivated by its economic applications, this paper studies the robustness of this approximation to natural strategic manipulations in which each random reward is associated with a self-interested player who may selectively reveal his realized reward to the searcher in order to maximize his probability of being selected. We say a threshold policy is $\alpha$(-strategically)-robust if it (a) achieves the $\alpha$-approximation to the prophet value for strategic players; and (b) meanwhile remains a $\frac{1}{2}$-approximation in the standard non-strategic setting. Starting with a characterization of each player's optimal information revealing strategy, we demonstrate the intrinsic robustness of prophet inequalities to strategic reward signaling through the following results: (1) for arbitrary reward distributions, there is a threshold policy that is $\frac{1-\frac{1}{e}}{2}$-robust, and this ratio is tight; (2) for i. i. d. reward distributions, there is a threshold policy that is $\frac{1}{2}$-robust, which is tight for the setting; and (3) for log-concave (but non-identical) reward distributions, the $\frac{1}{2}$-robustness can also be achieved under certain regularity assumptions.

AAAI Conference 2024 Conference Paper

Learning in Online Principal-Agent Interactions: The Power of Menus

• Minbiao Han
• Michael Albert
• Haifeng Xu

We study a ubiquitous learning challenge in online principal-agent problems during which the principal learns the agent's private information from the agent's revealed preferences in historical interactions. This paradigm includes important special cases such as pricing and contract design, which have been widely studied in recent literature. However, existing work considers the case where the principal can only choose a single strategy at every round to interact with the agent and then observe the agent's revealed preference through their actions. In this paper, we extend this line of study to allow the principal to offer a menu of strategies to the agent and learn additionally from observing the agent's selection from the menu. We provide a thorough investigation of several online principal-agent problem settings and characterize their sample complexities, accompanied by the corresponding algorithms we have developed. We instantiate this paradigm to several important design problems — including Stackelberg (security) games, contract design, and information design. Finally, we also explore the connection between our findings and existing results about online learning in Stackelberg games, and we offer a solution that can overcome a key hard instance of previous work.

ICML Conference 2024 Conference Paper

Multi-Sender Persuasion: A Computational Perspective

• Safwan Hossain
• Tonghan Wang 0001
• Tao Lin 0013
• Yiling Chen 0001
• David C. Parkes
• Haifeng Xu

We consider multiple senders with informational advantage signaling to convince a single self-interested actor to take certain actions. Generalizing the seminal Bayesian Persuasion framework, such settings are ubiquitous in computational economics, multi-agent learning, and machine learning with multiple objectives. The core solution concept here is the Nash equilibrium of senders’ signaling policies. Theoretically, we prove that finding an equilibrium in general is PPAD-Hard; in fact, even computing a sender’s best response is NP-Hard. Given these intrinsic difficulties, we turn to finding local Nash equilibria. We propose a novel differentiable neural network to approximate this game’s non-linear and discontinuous utilities. Complementing this with the extra-gradient algorithm, we discover local equilibria that Pareto dominates full-revelation equilibria and those found by existing neural networks. Broadly, our theoretical and empirical contributions are of interest to a large class of economic problems.

NeurIPS Conference 2024 Conference Paper

Strategic Linear Contextual Bandits

• Thomas Kleine Buening
• Aadirupa Saha
• Christos Dimitrakakis
• Haifeng Xu

Motivated by the phenomenon of strategic agents gaming a recommender system to maximize the number of times they are recommended to users, we study a strategic variant of the linear contextual bandit problem, where the arms can strategically misreport privately observed contexts to the learner. We treat the algorithm design problem as one of mechanism design under uncertainty and propose the Optimistic Grim Trigger Mechanism (OptGTM) that incentivizes the agents (i. e. , arms) to report their contexts truthfully while simultaneously minimizing regret. We also show that failing to account for the strategic nature of the agents results in linear regret. However, a trade-off between mechanism design and regret minimization appears to be unavoidable. More broadly, this work aims to provide insight into the intersection of online learning and mechanism design.

NeurIPS Conference 2024 Conference Paper

Unveiling User Satisfaction and Creator Productivity Trade-Offs in Recommendation Platforms

• Fan Yao
• Yiming Liao
• Jingzhou Liu
• Shaoliang Nie
• Qifan Wang
• Haifeng Xu
• Hongning Wang

On User-Generated Content (UGC) platforms, recommendation algorithms significantly impact creators' motivation to produce content as they compete for algorithmically allocated user traffic. This phenomenon subtly shapes the volume and diversity of the content pool, which is crucial for the platform's sustainability. In this work, we demonstrate, both theoretically and empirically, that a purely relevance-driven policy with low exploration strength boosts short-term user satisfaction but undermines the long-term richness of the content pool. In contrast, a more aggressive exploration policy may slightly compromise user satisfaction but promote higher content creation volume. Our findings reveal a fundamental trade-off between immediate user satisfaction and overall content production on UGC platforms. Building on this finding, we propose an efficient optimization method to identify the optimal exploration strength, balancing user and creator engagement. Our model can serve as a pre-deployment audit tool for recommendation algorithms on UGC platforms, helping to align their immediate objectives with sustainable, long-term goals.

SODA Conference 2023 Conference Paper

Competitive Information Design for Pandora's Box

• Bolin Ding
• Yiding Feng 0001
• Chien-Ju Ho
• Wei Tang
• Haifeng Xu

We study a natural competitive-information-design variant for the Pandora's Box problem [31], where each box is associated with a strategic information sender who can design what information about the box's prize value to be revealed to the agent when she inspects the box. This variant with strategic boxes is motivated by a wide range of real-world economic applications for Pandora's box. The main contributions of this article are two-fold: (1) we study informational properties of Pandora's Box by analyzing how a box's partial information revelation affects the search agent's optimal decisions; and (2) we fully characterize the pure symmetric equilibrium for the boxes' competitive information revelation, which reveals various insights regarding information competition and the resultant agent utility at equilibrium.

EAAI Journal 2023 Journal Article

Deep stacked pinball transfer matrix machine with its application in roller bearing fault diagnosis

• Haiyang Pan
• Li Sheng
• Haifeng Xu
• Jinde Zheng
• Jinyu Tong
• Limin Niu

At present, the matrix-based classification methods have played an extremely important role to mechanical fault diagnosis. However, the traditional matrix-based classification methods are mostly shallow classifiers, which are difficult to obtain the deep-seated sensitive features of vibration signals. To learn and extract low-rank structure information, a new deep stacked pinball transfer matrix machine (DSPTMM) is proposed to enhance the performance of traditional shallow matrix-based classifiers, which takes the stacking generalization principle as the main idea. In DSPTMM, a pinball transfer module (PTM) is constructed as the basic module of deep stacking network, in which the pinball loss is used to achieve an enhanced noise robustness. Specifically, PTM performs the function to obtain the weak prediction of the previous module, and the original results of previous weak prediction are modified by random projection and then will be input as a new feature set in the next module. Therefore, DSPTMM has a better classification performance and can modeled without enough annotation samples. Extensive experiments are carried out on two different datasets of roller bearing, and the results of experiment show that the proposed DSPTMM can use limited samples to establish the accurate model.

NeurIPS Conference 2023 Conference Paper

Follow-ups Also Matter: Improving Contextual Bandits via Post-serving Contexts

• Chaoqi Wang
• Ziyu Ye
• Zhe Feng
• Ashwinkumar Badanidiyuru Varadaraja
• Haifeng Xu

Standard contextual bandit problem assumes that all the relevant contexts are observed before the algorithm chooses an arm. This modeling paradigm, while useful, often falls short when dealing with problems in which additional valuable contexts can be observed after arm selection. For example, content recommendation platforms like Youtube, Instagram, Tiktok receive much additional features about a user's reward after the user clicks a content (e. g. , how long the user stayed, what is the user's watch speed, etc. ). To improve online learning efficiency in these applications, we study a novel contextual bandit problem with post-serving contexts and design a new algorithm, poLinUCB, that achieves tight regret under standard assumptions. Core to our technical proof is a robustified and generalized version of the well-known Elliptical Potential Lemma (EPL), which can accommodate noise in data. Such robustification is necessary for tackling our problem, though we believe it could also be of general interest. Extensive empirical tests on both synthetic and real-world datasets demonstrate the significant benefit of utilitzing post-serving contexts as well as the superior performance of our algorithm over the state-of-the-art approaches.

ICML Conference 2023 Conference Paper

How Bad is Top-K Recommendation under Competing Content Creators?

• Fan Yao 0002
• Chuanhao Li 0002
• Denis Nekipelov
• Hongning Wang
• Haifeng Xu

This study explores the impact of content creators’ competition on user welfare in recommendation platforms, as well as the long-term dynamics of relevance-driven recommendations. We establish a model of creator competition, under the setting where the platform uses a top-$K$ recommendation policy, user decisions are guided by the Random Utility model, and creators, in absence of explicit utility functions, employ arbitrary no-regret learning algorithms for strategy updates. We study the user welfare guarantee through the lens of Price of Anarchy and show that the fraction of user welfare loss due to creator competition is always upper bounded by a small constant depending on $K$ and randomness in user decisions; we also prove the tightness of this bound. Our result discloses an intrinsic merit of the relevance-driven recommendation policy, as long as users’ decisions involve randomness and the platform provides reasonably many alternatives to its users.

NeurIPS Conference 2023 Conference Paper

Incentivized Communication for Federated Bandits

• Zhepei Wei
• Chuanhao Li
• Haifeng Xu
• Hongning Wang

Most existing works on federated bandits take it for granted that all clients are altruistic about sharing their data with the server for the collective good whenever needed. Despite their compelling theoretical guarantee on performance and communication efficiency, this assumption is overly idealistic and oftentimes violated in practice, especially when the algorithm is operated over self-interested clients, who are reluctant to share data without explicit benefits. Negligence of such self-interested behaviors can significantly affect the learning efficiency and even the practical operability of federated bandit learning. In light of this, we aim to spark new insights into this under-explored research area by formally introducing an incentivized communication problem for federated bandits, where the server shall motivate clients to share data by providing incentives. Without loss of generality, we instantiate this bandit problem with the contextual linear setting and propose the first incentivized communication protocol, namely, Inc-FedUCB, that achieves near-optimal regret with provable communication and incentive cost guarantees. Extensive empirical experiments on both synthetic and real-world datasets further validate the effectiveness of the proposed method across various environments.

JMLR Journal 2023 Journal Article

PAC-learning for Strategic Classification

• Ravi Sundaram
• Anil Vullikanti
• Haifeng Xu
• Fan Yao

The study of strategic or adversarial manipulation of testing data to fool a classifier has attracted much recent attention. Most previous works have focused on two extreme situations where any testing data point either is completely adversarial or always equally prefers the positive label. In this paper, we generalize both of these through a unified framework by considering strategic agents with heterogenous preferences, and introduce the notion of strategic VC-dimension (SVC) to capture the PAC-learnability in our general strategic setup. SVC provably generalizes the recent concept of adversarial VC-dimension (AVC) introduced by Cullina et al. (2018). We instantiate our framework for the fundamental strategic linear classification problem. We fully characterize: (1) the statistical learnability of linear classifiers by pinning down its SVC; (2) its computational tractability by pinning down the complexity of the empirical risk minimization problem. Interestingly, the SVC of linear classifiers is always upper bounded by its standard VC-dimension. This characterization also strictly generalizes the AVC bound for linear classifiers in (Cullina et al., 2018). Finally, we briefly investigate the power of randomization in our strategic classification setup. We show that randomization may strictly increase the accuracy in general, but will not help in the special case of adversarial classification with zero-manipulation-cost. [abs] [ pdf ][ bib ] &copy JMLR 2023. ( edit, beta )

NeurIPS Conference 2023 Conference Paper

Rethinking Incentives in Recommender Systems: Are Monotone Rewards Always Beneficial?

• Fan Yao
• Chuanhao Li
• Karthik Abinav Sankararaman
• Yiming Liao
• Yan Zhu
• Qifan Wang
• Hongning Wang
• Haifeng Xu

The past decade has witnessed the flourishing of a new profession as media content creators, who rely on revenue streams from online content recommendation platforms. The reward mechanism employed by these platforms creates a competitive environment among creators which affects their production choices and, consequently, content distribution and system welfare. It is thus crucial to design the platform's reward mechanism in order to steer the creators' competition towards a desirable welfare outcome in the long run. This work makes two major contributions in this regard: first, we uncover a fundamental limit about a class of widely adopted mechanisms, coined \emph{Merit-based Monotone Mechanisms}, by showing that they inevitably lead to a constant fraction loss of the optimal welfare. To circumvent this limitation, we introduce \emph{Backward Rewarding Mechanisms} (BRMs) and show that the competition game resultant from BRMs possesses a potential game structure. BRMs thus naturally induce strategic creators' collective behaviors towards optimizing the potential function, which can be designed to match any given welfare metric. In addition, the class of BRM can be parameterized so that it allows the platform to directly optimize welfare within the feasible mechanism space even when the welfare metric is not explicitly defined.

IJCAI Conference 2023 Conference Paper

The Economics of Machine Learning

• Haifeng Xu

This survey overviews a new research agenda on the economics of machine learning, pursued at the Strategic IntelliGence for Machine Agent (SIGMA) Lab at UChicago. This overall research agenda has two themes: machine learning for economics and, conversely, economics for machine learning (ML). The first theme focuses on designing and analyzing ML algorithms for economic problems, ranging from foundational economic models to influential real-world applications such as recommender systems and national security. The second theme employs economic principles to study machine learning itself, such as the valuation and pricing of data, information and ML models, and designing incentive mechanisms to improve large-scale ML research peer reviews. While our research focuses primarily on developing methodologies, in each theme we also highlight some real-world impacts of these works, including ongoing large-scale live experiments and potential deployments for various applications.

NeurIPS Conference 2022 Conference Paper

CS-Shapley: Class-wise Shapley Values for Data Valuation in Classification

• Stephanie Schoch
• Haifeng Xu
• Yangfeng Ji

Data valuation, or the valuation of individual datum contributions, has seen growing interest in machine learning due to its demonstrable efficacy for tasks such as noisy label detection. In particular, due to the desirable axiomatic properties, several Shapley value approximations have been proposed. In these methods, the value function is usually defined as the predictive accuracy over the entire development set. However, this limits the ability to differentiate between training instances that are helpful or harmful to their own classes. Intuitively, instances that harm their own classes may be noisy or mislabeled and should receive a lower valuation than helpful instances. In this work, we propose CS-Shapley, a Shapley value with a new value function that discriminates between training instances’ in-class and out-of-class contributions. Our theoretical analysis shows the proposed value function is (essentially) the unique function that satisfies two desirable properties for evaluating data values in classification. Further, our experiments on two benchmark evaluation tasks (data removal and noisy label detection) and four classifiers demonstrate the effectiveness of CS-Shapley over existing methods. Lastly, we evaluate the “transferability” of data values estimated from one classifier to others, and our results suggest Shapley-based data valuation is transferable for application across different models.

AAAI Conference 2022 Conference Paper

First-Order Convex Fitting and Its Application to Economics and Optimization

• Quinlan Dawkins
• Minbiao Han
• Haifeng Xu

This paper studies a function fitting problem which we coin first-order convex fitting (FCF): given any two vector sequences {xi}i∈[T ] and {pi}i∈[T ] in Rd, when is it possible to efficiently construct a convex function f(x) that “fits” the two sequences in the first-order sense, i. e, its (sub)gradient ∇f(xi) equals pi for all i ∈ [T] = {1, · · ·, T}? Despite a basic question of convex analysis, FCF has surprisingly been overlooked in the past literature. With an efficient constructive proof, we provide a clean answer to this question: FCF is possible if and only if the two sequences are permutation stable: PT i=1 xi · pi ≥ PT i=1 xi · pσ(i) for any permutation σ of [T]. We demonstrate the usefulness of FCF in two applications. First, we study how it can be used as an empirical risk minimization procedure to learn the original convex function. We provide efficient PAC-learnability bounds for special classes of convex functions learned via FCF, and demonstrate its application to multiple economic problems where only function gradients (as opposed to function values) can be observed. Second, we empirically show how it can be used as a surrogate to significantly accelerate the minimization of the original convex function.

NeurIPS Conference 2022 Conference Paper

Incrementality Bidding via Reinforcement Learning under Mixed and Delayed Rewards

• Ashwinkumar Badanidiyuru Varadaraja
• Zhe Feng
• Tianxi Li
• Haifeng Xu

Incrementality, which measures the causal effect of showing an ad to a potential customer (e. g. a user in an internet platform) versus not, is a central object for advertisers in online advertising platforms. This paper investigates the problem of how an advertiser can learn to optimize the bidding sequence in an online manner \emph{without} knowing the incrementality parameters in advance. We formulate the offline version of this problem as a specially structured episodic Markov Decision Process (MDP) and then, for its online learning counterpart, propose a novel reinforcement learning (RL) algorithm with regret at most $\widetilde{O}(H^2\sqrt{T})$, which depends on the number of rounds $H$ and number of episodes $T$, but does not depend on the number of actions (i. e. , possible bids). A fundamental difference between our learning problem from standard RL problems is that the realized reward feedback from conversion incrementality is \emph{mixed} and \emph{delayed}. To handle this difficulty we propose and analyze a novel pairwise moment-matching algorithm to learn the conversion incrementality, which we believe is of independent interest.

UAI Conference 2022 Conference Paper

Information design for multiple independent and self-interested defenders: Work less, pay off more

• Chenghan Zhou
• Andrew Spivey
• Haifeng Xu
• Thanh Hong Nguyen

This paper studies the problem of information design in a general security game setting in which multiple independent self-interested defenders attempt to provide protection simultaneously on the same set of important targets against an unknown attacker. A principal, who can be one of the defenders, has access to certain private information (i. e. , attacker type) whereas other defenders do not. We investigate the question of how that principal, with additional private information, can influence the decisions of the defenders by partially and strategically revealing her information. We focus on the algorithmic study of information design for private signaling in this game setting. In particular, we develop a polynomial-time ellipsoid algorithm to compute an optimal private signaling scheme. Our key finding is that the separation oracle in the ellipsoid approach can be carefully reduced to bipartite matching. Furthermore, we introduce a compact representation of any ex-ante persuasive signaling schemes by exploiting intrinsic security resource allocation structures, enabling us to compute an optimal scheme significantly faster. Our experiment results show that by strategically revealing private information, the principal can significantly enhance the protection effectiveness on the targets.

NeurIPS Conference 2022 Conference Paper

Inverse Game Theory for Stackelberg Games: the Blessing of Bounded Rationality

• Jibang Wu
• Weiran Shen
• Fei Fang
• Haifeng Xu

Optimizing strategic decisions (a. k. a. computing equilibrium) is key to the success of many non-cooperative multi-agent applications. However, in many real-world situations, we may face the exact opposite of this game-theoretic problem --- instead of prescribing equilibrium of a given game, we may directly observe the agents' equilibrium behaviors but want to infer the underlying parameters of an unknown game. This research question, also known as inverse game theory, has been studied in multiple recent works in the context of Stackelberg games. Unfortunately, existing works exhibit quite negative results, showing statistical hardness and computational hardness, assuming follower's perfectly rational behaviors. Our work relaxes the perfect rationality agent assumption to the classic quantal response model, a more realistic behavior model of bounded rationality. Interestingly, we show that the smooth property brought by such bounded rationality model actually leads to provably more efficient learning of the follower utility parameters in general Stackelberg games. Systematic empirical experiments on synthesized games confirm our theoretical results and further suggest its robustness beyond the strict quantal response model.

ICML Conference 2022 Conference Paper

Learning from a Learning User for Optimal Recommendations

• Fan Yao 0002
• Chuanhao Li 0002
• Denis Nekipelov
• Hongning Wang
• Haifeng Xu

In real-world recommendation problems, especially those with a formidably large item space, users have to gradually learn to estimate the utility of any fresh recommendations from their experience about previously consumed items. This in turn affects their interaction dynamics with the system and can invalidate previous algorithms built on the omniscient user assumption. In this paper, we formalize a model to capture such ”learning users” and design an efficient system-side learning solution, coined Noise-Robust Active Ellipsoid Search (RAES), to confront the challenges brought by the non-stationary feedback from such a learning user. Interestingly, we prove that the regret of RAES deteriorates gracefully as the convergence rate of user learning becomes worse, until reaching linear regret when the user’s learning fails to converge. Experiments on synthetic datasets demonstrate the strength of RAES for such a contemporaneous system-user learning problem. Our study provides a novel perspective on modeling the feedback loop in recommendation problems.

AAAI Conference 2022 Conference Paper

Learning the Optimal Recommendation from Explorative Users

• Fan Yao
• Chuanhao Li
• Denis Nekipelov
• Hongning Wang
• Haifeng Xu

We propose a new problem setting to study the sequential interactions between a recommender system and a user. Instead of assuming the user is omniscient, static, and explicit, as the classical practice does, we sketch a more realistic user behavior model, under which the user: 1) rejects recommendations if they are clearly worse than others; 2) updates her utility estimation based on rewards from her accepted recommendations; 3) withholds realized rewards from the system. We formulate the interactions between the system and such an explorative user in a K-armed bandit framework and study the problem of learning the optimal recommendation on the system side. We show that efficient system learning is still possible but is more difficult. In particular, the system can identify the best arm with probability at least 1 − δ within O(1/δ) interactions, and we prove this is tight. Our finding contrasts the result for the problem of best arm identification with fixed confidence, in which the best arm can be identified with probability 1 − δ within O(log(1/δ)) interactions. This gap illustrates the inevitable cost the system has to pay when it learns from an explorative user’s revealed preferences on its recommendations rather than from the realized rewards.

AAAI Conference 2022 Conference Paper

Saving Stochastic Bandits from Poisoning Attacks via Limited Data Verification

• Anshuka Rangi
• Long Tran-Thanh
• Haifeng Xu
• Massimo Franceschetti

This paper studies bandit algorithms under data poisoning attacks in a bounded reward setting. We consider a strong attacker model in which the attacker can observe both the selected actions and their corresponding rewards, and can contaminate the rewards with additive noise. We show that any bandit algorithm with regret O(log T) can be forced to suffer a regret Ω(T) with an expected amount of contamination O(log T). This amount of contamination is also necessary, as we prove that there exists an O(log T) regret bandit algorithm, specifically the classical Upper Confidence Bound (UCB), that requires Ω(log T) amount of contamination to suffer regret Ω(T). To combat such poisoning attacks, our second main contribution is to propose verification based mechanisms, which use limited verification to access a limited number of uncontaminated rewards. In particular, for the case of unlimited verifications, we show that with O(log T) expected number of verifications, a simple modified version of the Explore-then-Commit type bandit algorithm can restore the order optimal O(log T) regret irrespective of the amount of contamination used by the attacker. We also provide a UCB-like verification scheme, called Secure- UCB, that also enjoys full recovery from any attacks, also with O(log T) expected number of verifications. To derive a matching lower bound on the number of verifications, we also prove that for any order-optimal bandit algorithm, this number of verifications Ω(log T) is necessary to recover the order-optimal regret. On the other hand, when the number of verifications is bounded above by a budget B, we propose a novel algorithm, Secure-BARBAR, which provably achieves Õ(min{C, T/ √ B}) regret with high probability against weak attackers (i. e. , attackers who have to place the contamination before seeing the actual pulls of the bandit algorithm), where C is the total amount of contamination by the attacker, which breaks the known Ω(C) lower bound of the non-verified setting if C is large.

ICML Conference 2022 Conference Paper

Selling Data To a Machine Learner: Pricing via Costly Signaling

• Junjie Chen
• Minming Li
• Haifeng Xu

We consider a new problem of selling data to a machine learner who looks to purchase data to train his machine learning model. A key challenge in this setup is that neither the seller nor the machine learner knows the true quality of data. When designing a revenue-maximizing mechanism, a data seller faces the tradeoff between the cost and precision of data quality estimation. To address this challenge, we study a natural class of mechanisms that price data via costly signaling. Motivated by the assumption of i. i. d. data points as in classic machine learning models, we first consider selling homogeneous data and derive an optimal selling mechanism. We then turn to the sale of heterogeneous data, motivated by the sale of multiple data sets, and show that 1) on the negative side, it is NP-hard to approximate the optimal mechanism within a constant ratio e/(e+1) + o(1); while 2) on the positive side, there is a 1/k-approximate algorithm, where k is the number of the machine learner’s private types.

AAAI Conference 2022 Conference Paper

The Strange Role of Information Asymmetry in Auctions—Does More Accurate Value Estimation Benefit a Bidder?

• Haifeng Xu
• Ruggiero Cavallo

We study the second-price auction in which bidders have asymmetric information regarding the item’s value. Each bidder’s value for the item depends on a private component and a public component. While each bidder observes their own private component, they hold different and asymmetric information about the public component. We characterize the equilibrium of this auction game and study how the asymmetric bidder information affects their equilibrium bidding strategies. We also discover multiple surprisingly counter-intuitive equilibrium phenomena. For instance, a bidder may be better off if she is less informed regarding the public component. Conversely, a bidder may sometimes be worse off if she obtains more accurate estimation about the auctioned item. Our results suggest that efforts devoted by bidders to improve their value estimations, as widely seen in today’s online advertising auctions, may not always be to their benefit.

IJCAI Conference 2022 Conference Paper

Understanding the Limits of Poisoning Attacks in Episodic Reinforcement Learning

• Anshuka Rangi
• Haifeng Xu
• Long Tran-Thanh
• Massimo Franceschetti

To understand the security threats to reinforcement learning (RL) algorithms, this paper studies poisoning attacks to manipulate any order-optimal learning algorithm towards a targeted policy in episodic RL and examines the potential damage of two natural types of poisoning attacks, i. e. , the manipulation of reward or action. We discover that the effect of attacks crucially depends on whether the rewards are bounded or unbounded. In bounded reward settings, we show that only reward manipulation or only action manipulation cannot guarantee a successful attack. However, by combining reward and action manipulation, the adversary can manipulate any order-optimal learning algorithm to follow any targeted policy with \Theta(\sqrt{T}) total attack cost, which is order-optimal, without any knowledge of the underlying MDP. In contrast, in unbounded reward settings, we show that reward manipulation attacks are sufficient for an adversary to successfully manipulate any order-optimal learning algorithm to follow any targeted policy using \tilde{O}(\sqrt{T}) amount of contamination. Our results reveal useful insights about what can or cannot be achieved by poisoning attacks, and are set to spur more work on the design of robust RL algorithms.

ICML Conference 2022 Conference Paper

When Are Linear Stochastic Bandits Attackable?

• Huazheng Wang
• Haifeng Xu
• Hongning Wang

We study adversarial attacks on linear stochastic bandits: by manipulating the rewards, an adversary aims to control the behaviour of the bandit algorithm. Perhaps surprisingly, we first show that some attack goals can never be achieved. This is in a sharp contrast to context-free stochastic bandits, and is intrinsically due to the correlation among arms in linear stochastic bandits. Motivated by this finding, this paper studies the attackability of a $k$-armed linear bandit environment. We first provide a complete necessity and sufficiency characterization of attackability based on the geometry of the arms’ context vectors. We then propose a two-stage attack method against LinUCB and Robust Phase Elimination. The method first asserts whether the given environment is attackable; and if yes, it poisons the rewards to force the algorithm to pull a target arm linear times using only a sublinear cost. Numerical experiments further validate the effectiveness and cost-efficiency of the proposed attack method.

AAAI Conference 2022 Conference Paper

When Can the Defender Effectively Deceive Attackers in Security Games?

• Thanh Nguyen
• Haifeng Xu

This paper studies defender patrol deception in general Stackelberg security games (SSGs), where a defender attempts to alter the attacker’s perception of the defender’s patrolling intensity so as to influence the attacker’s decision making. We are interested in understanding the complexity and effectiveness of optimal defender deception under different attacker behavior models. Specifically, we consider three different attacker strategies of response (to the defender’s deception) with increasing sophistication, and design efficient polynomial-time algorithms to compute the equilibrium for each. Moreover, we prove formal separation for the effectiveness of patrol deception when facing an attacker of increasing sophistication, until it becomes even harmful to the defender when facing the most intelligent attacker we consider. Our results shed light on when and how deception should be used in SSGs. We conduct extensive experiments to illustrate our theoretical results in various game settings.

NeurIPS Conference 2021 Conference Paper

(Almost) Free Incentivized Exploration from Decentralized Learning Agents

• Chengshuai Shi
• Haifeng Xu
• Wei Xiong
• Cong Shen

Incentivized exploration in multi-armed bandits (MAB) has witnessed increasing interests and many progresses in recent years, where a principal offers bonuses to agents to do explorations on her behalf. However, almost all existing studies are confined to temporary myopic agents. In this work, we break this barrier and study incentivized exploration with multiple and long-term strategic agents, who have more complicated behaviors that often appear in real-world applications. An important observation of this work is that strategic agents' intrinsic needs of learning benefit (instead of harming) the principal's explorations by providing "free pulls". Moreover, it turns out that increasing the population of agents significantly lowers the principal's burden of incentivizing. The key and somewhat surprising insight revealed from our results is that when there are sufficiently many learning agents involved, the exploration process of the principal can be (almost) free. Our main results are built upon three novel components which may be of independent interest: (1) a simple yet provably effective incentive-provision strategy; (2) a carefully crafted best arm identification algorithm for rewards aggregated under unequal confidences; (3) a high-probability finite-time lower bound of UCB algorithms. Experimental results are provided to complement the theoretical analysis.

ICML Conference 2021 Conference Paper

Diffusion Source Identification on Networks with Statistical Confidence

• Quinlan Dawkins
• Tianxi Li
• Haifeng Xu

Diffusion source identification on networks is a problem of fundamental importance in a broad class of applications, including controlling the spreading of rumors on social media, identifying a computer virus over cyber networks, or identifying the disease center during epidemiology. Though this problem has received significant recent attention, most known approaches are well-studied in only very restrictive settings and lack theoretical guarantees for more realistic networks. We introduce a statistical framework for the study of this problem and develop a confidence set inference approach inspired by hypothesis testing. Our method efficiently produces a small subset of nodes, which provably covers the source node with any pre-specified confidence level without restrictive assumptions on network structures. To our knowledge, this is the first diffusion source identification method with a practically useful theoretical guarantee on general networks. We demonstrate our approach via extensive synthetic experiments on well-known random network models, a large data set of real-world networks as well as a mobility network between cities concerning the COVID-19 spreading in January 2020.

NeurIPS Conference 2021 Conference Paper

Least Square Calibration for Peer Reviews

• Sijun Tan
• Jibang Wu
• Xiaohui Bei
• Haifeng Xu

Peer review systems such as conference paper review often suffer from the issue of miscalibration. Previous works on peer review calibration usually only use the ordinal information or assume simplistic reviewer scoring functions such as linear functions. In practice, applications like academic conferences often rely on manual methods, such as open discussions, to mitigate miscalibration. It remains an important question to develop algorithms that can handle different types of miscalibrations based on available prior knowledge. In this paper, we propose a flexible framework, namely \emph{least square calibration} (LSC), for selecting top candidates from peer ratings. Our framework provably performs perfect calibration from noiseless linear scoring functions under mild assumptions, yet also provides competitive calibration results when the scoring function is from broader classes beyond linear functions and with arbitrary noise. On our synthetic dataset, we empirically demonstrate that our algorithm consistently outperforms the baseline which select top papers based on the highest average ratings.

ICML Conference 2021 Conference Paper

PAC-Learning for Strategic Classification

• Ravi Sundaram
• V. S. Anil Kumar 0001
• Haifeng Xu
• Fan Yao 0002

The study of strategic or adversarial manipulation of testing data to fool a classifier has attracted much recent attention. Most previous works have focused on two extreme situations where any testing data point either is completely adversarial or always equally prefers the positive label. In this paper, we generalize both of these through a unified framework for strategic classification and introduce the notion of strategic VC-dimension (SVC) to capture the PAC-learnability in our general strategic setup. SVC provably generalizes the recent concept of adversarial VC-dimension (AVC) introduced by Cullina et al. (2018). We instantiate our framework for the fundamental strategic linear classification problem. We fully characterize: (1) the statistical learnability of linear classifiers by pinning down its SVC; (2) it’s computational tractability by pinning down the complexity of the empirical risk minimization problem. Interestingly, the SVC of linear classifiers is always upper bounded by its standard VC-dimension. This characterization also strictly generalizes the AVC bound for linear classifiers in (Cullina et al. , 2018).

JBHI Journal 2021 Journal Article

Predicting Recurrence for Patients With Ischemic Cerebrovascular Events Based on Process Discovery and Transfer Learning

• Haifeng Xu
• Jianfei Pang
• Weiliang Zhang
• Xuemeng Li
• Mei Li
• Dongsheng Zhao

The recurrence of Ischemic cerebrovascular events (ICE) often results in a high rate of mortality and disability. However, due to the lack of labeled follow-up data in hospitals, prediction methods using traditional machine learning are usually not available or reliable. Therefore, we propose a new framework for predicting the long-term recurrence risk in patients with ICE after discharge from hospitals based on process mining and transfer learning, to point out high-risk patients for intervention. First, process models are discovered from clinical guidelines for analyzing the similarity of ICE population data collected by different medical institutions, and the control flow found are taken as added characteristics of patients. Then we use the in-hospital data (target domain) and the national stroke screening data (source domain), to develop risk prediction models applying instance filter and weight-based transfer learning method. To verify our method, 205 cases from a tertiary hospital and 2954 cases from the screening cohort (2015-2017) are tested. Experimental results show that our framework can improve the performance of three instance-based transfer algorithms. This study provides a comprehensive and efficient approach for applying transfer learning, to alleviate the limitation of insufficient labeled follow-up data in hospitals.

NeurIPS Conference 2021 Conference Paper

The Limits of Optimal Pricing in the Dark

• Quinlan Dawkins
• Minbiao Han
• Haifeng Xu

A ubiquitous learning problem in today’s digital market is, during repeated interactions between a seller and a buyer, how a seller can gradually learn optimal pricing decisions based on the buyer’s past purchase responses. A fundamental challenge of learning in such a strategic setup is that the buyer will naturally have incentives to manipulate his responses in order to induce more favorable learning outcomes for him. To understand the limits of the seller’s learning when facing such a strategic and possibly manipulative buyer, we study a natural yet powerful buyer manipulation strategy. That is, before the pricing game starts, the buyer simply commits to “imitate” a different value function by pretending to always react optimally according to this imitative value function. We fully characterize the optimal imitative value function that the buyer should imitate as well as the resultant seller revenue and buyer surplus under this optimal buyer manipulation. Our characterizations reveal many useful insights about what happens at equilibrium. For example, a seller with concave production cost will obtain essentially 0 revenue at equilibrium whereas the revenue for a seller with convex production cost is the Bregman divergence of her cost function between no production and certain production. Finally, and importantly, we show that a more powerful class of pricing schemes does not necessarily increase, in fact, may be harmful to, the seller’s revenue. Our results not only lead to an effective prescriptive way for buyers to manipulate learning algorithms but also shed lights on the limits of what a seller can really achieve when pricing in the dark.

NeurIPS Conference 2020 Conference Paper

Collapsing Bandits and Their Application to Public Health Intervention

• Aditya Mate
• Jackson Killian
• Haifeng Xu
• Andrew Perrault
• Milind Tambe

We propose and study Collapsing 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 CollapsingBandits are natural models for many healthcare domains in which health 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. The code is available at: https: //github. com/AdityaMate/collapsing_bandits

AAAI Conference 2020 Conference Paper

Information Shaping for Enhanced Goal Recognition of Partially-Informed Agents

• Sarah Keren
• Haifeng Xu
• Kofi Kwapong
• David Parkes
• Barbara Grosz

We extend goal recognition design to account for partially informed agents. In particular, we consider a two-agent setting in which one agent, the actor, seeks to achieve a goal but has only incomplete information about the environment. The second agent, the recognizer, has perfect information and aims to recognize the actor’s goal from its behavior as quickly as possible. As a one-time offline intervention and with the objective of facilitating the recognition task, the recognizer can selectively reveal information to the actor. The problem of selecting which information to reveal, which we call information shaping, is challenging not only because the space of information shaping options may be large, but also because more information revelation need not make it easier to recognize an agent’s goal. We formally define this problem, and suggest a pruning approach for efficiently searching the search space. We demonstrate the effectiveness and efficiency of the suggested method on standard benchmarks.

SODA Conference 2020 Conference Paper

On the Tractability of Public Persuasion with No Externalities

• Haifeng Xu

SODA Conference 2020 Conference Paper

Selling Information Through Consulting

• Yiling Chen 0001
• Haifeng Xu
• Shuran Zheng

ECAI Conference 2020 Conference Paper

Tackling Imitative Attacker Deception in Repeated Bayesian Stackelberg Security Games

• Thanh Hong Nguyen
• Andrew Butler
• Haifeng Xu

Uncertainty is one of the key challenges in Stackelberg security games (SSGs) — a well known class of games which have been used to solve various real-world problems in security domains such as airport security and wildlife protection. In these domains, security agencies (defender) are generally uncertain about underlying characteristics of attackers such as the attackers’ preference or behavior. Previous work in SSGs has proposed different learning methods to reduce uncertainty about attackers based on historical attack data. However, since these learning algorithms depend on the attack data, a clever attacker can manipulate its attacks to influence the learning outcome. Such deception of the attacker could lead to ineffective defense strategies that favor the attacker. This work studies the strategic deception of the attacker with private type information in a repeated Bayesian Stackelberg security game (RBSSG) setting. We investigate a basic deception strategy, named imitative attacker deception — that is the attacker pretends to have a different type and consistently plays according to that deceptive type throughout the whole time horizon. We provide four main contributions. First, we present a detailed equilibrium computation and analysis of standard RBSSGs with a non-deceptive attacker. To our knowledge, our work is the first to present an exact algorithm to compute an RBSSG equilibrium. Second, we introduce a new counter-deception algorithm, built on our equilibrium computation of standard RBSSGs, to address the attacker’s deception. Third, we introduce two new heuristics to overcome the computational challenge of the exact algorithm: one heuristic limits the number of time steps to look ahead and the other limits the number of observational attack histories in consideration. Fourth, we conduct extensive experiments, showing the significant loss of the defender and benefit of the attacker as a result of the attacker deception. We also show that our counter-deception algorithm can help in substantially diminishing the impact of the attacker’s deception on the players’ utility.

ICML Conference 2020 Conference Paper

The Intrinsic Robustness of Stochastic Bandits to Strategic Manipulation

• Zhe Feng 0004
• David C. Parkes
• Haifeng Xu

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 the running time of the algorithms. This regret guarantee holds for \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}. We do so by characterizing the Nash equilibrium of the game induced by arms’ strategic manipulations and show a regret lower bound of $\Omega(\max \{ B, K\ln T\})$ at the equilibrium.

AAAI Conference 2020 Conference Paper

To Signal or Not To Signal: Exploiting Uncertain Real-Time Information in Signaling Games for Security and Sustainability

• Elizabeth Bondi
• Hoon Oh
• Haifeng Xu
• Fei Fang
• Bistra Dilkina
• Milind Tambe

Motivated by real-world deployment of drones for conservation, this paper advances the state-of-the-art in security games with signaling. The well-known defender-attacker security games framework can help in planning for such strategic deployments of sensors and human patrollers, and warning signals to ward off adversaries. However, we show that defenders can suffer significant losses when ignoring real-world uncertainties despite carefully planned security game strategies with signaling. In fact, defenders may perform worse than forgoing drones completely in this case. We address this shortcoming by proposing a novel game model that integrates signaling and sensor uncertainty; perhaps surprisingly, we show that defenders can still perform well via a signaling strategy that exploits uncertain real-time information. For example, even in the presence of uncertainty, the defender still has an informational advantage in knowing that she has or has not actually detected the attacker; and she can design a signaling scheme to “mislead” the attacker who is uncertain as to whether he has been detected. We provide theoretical results, a novel algorithm, scale-up techniques, and experimental results from simulation based on our ongoing deployment of a conservation drone system in South Africa.

AAMAS Conference 2019 Conference Paper

Broken Signals in Security Games: Coordinating Patrollers and Sensors in the Real World

• Elizabeth Bondi
• Hoon Oh
• Haifeng Xu
• Fei Fang
• Bistra Dilkina
• Milind Tambe

Mobile sensors, e. g. , unmanned aerial vehicles (UAVs), are becoming increasingly important in security domains and can be used for tasks such as searching for poachers in conservation areas. Such mobile sensors augment human patrollers by assisting in surveillance and in signaling potentially deceptive information to adversaries, and their coordinated deployment could be modeled via the well-known security games framework. Unfortunately, real-world uncertainty in the sensor’s detection of adversaries and adversaries’ observation of the sensor’s signals present major challenges in the sensors’ use. This leads to significant detriments in security performance. We first discuss the current shortcomings in more detail, and then propose a novel game model that incorporates uncertainty with sensors. The defender strategy in this game model will consist of three interdependent stages: an allocation stage, a signaling stage, and a reaction stage.

AAMAS Conference 2019 Conference Paper

General-Sum Cyber Deception Games under Partial Attacker Valuation Information

• Omkar Thakoor
• Milind Tambe
• Phebe Vayanos
• Haifeng Xu
• Christopher Kiekintveld

IJCAI Conference 2019 Conference Paper

Imitative Attacker Deception in Stackelberg Security Games

• Thanh Nguyen
• Haifeng Xu

To address the challenge of uncertainty regarding the attacker’s payoffs, capabilities, and other characteristics, recent work in security games has focused on learning the optimal defense strategy from observed attack data. This raises a natural concern that the strategic attacker may mislead the defender by deceptively reacting to the learning algorithms. This paper focuses on understanding how such attacker deception affects the game equilibrium. We examine a basic deception strategy termed imitative deception, in which the attacker simply pretends to have a different payoff assuming his true payoff is unknown to the defender. We provide a clean characterization about the game equilibrium as well as optimal algorithms to compute the equilibrium. Our experiments illustrate significant defender loss due to imitative attacker deception, suggesting the potential side effect of learning from the attacker.

AAMAS Conference 2019 Conference Paper

Using Game Theory in Real Time in the Real World: A Conservation Case Study

• Elizabeth Bondi
• Hoon Oh
• Haifeng Xu
• Fei Fang
• Bistra Dilkina
• Milind Tambe

In the real world, real-time data are now widely available, especially in security domains. Security cameras, aerial imagery, and even social media keep defenders informed when protecting important events, locations, and people. Further, advances in artificial intelligence have led to tools that can interpret these data automatically. Game theoretic models, for example, have shown great success in security. However, most of them ignore real-time information. In this paper, we demonstrate the potential to use real-time information from imagery to better inform our decisions in game theoretic models for security. As a concrete example, a conservation group called Air Shepherd uses conservation drones equipped with thermal infrared cameras to locate poachers at night and alert park rangers. They have also used lights aboard the drones, or signaled, to warn poachers of their presence, which often deters the poachers. We propose a system that (i) allocates drones and humans strategically throughout a protected area, (ii) detects poachers in the thermal infrared videos recorded by the conservation drones flying through the protected area in the predetermined location, and (iii) recommends moving to the location and/or signaling to the poacher that a patroller is nearby depending on real-time detections. View the demonstration: http: //bit. ly/aamas19-demo-bondi-et-al.

AAMAS Conference 2018 Conference Paper

Deceiving Cyber Adversaries: A Game Theoretic Approach

• Aaron Schlenker
• Omkar Thakoor
• Haifeng Xu
• Fei Fang
• Milind Tambe
• Long Tran-Thanh
• Phebe Vayanos
• Yevgeniy Vorobeychik

An important way cyber adversaries find vulnerabilities in modern networks is through reconnaissance, in which they attempt to identify configuration specifics of network hosts. To increase uncertainty of adversarial reconnaissance, the network administrator (henceforth, defender) can introduce deception into responses to network scans, such as obscuring certain system characteristics. We introduce a novel game-theoretic model of deceptive interactions of this kind between a defender and a cyber attacker, which we call the Cyber Deception Game. We consider both a powerful (rational) attacker, who is aware of the defender’s exact deception strategy, and a naive attacker who is not. We show that computing the optimal deception strategy is NP-hard for both types of attackers. For the case with a powerful attacker, we provide a mixed-integer linear program solution as well as a fast and effective greedy algorithm. Similarly, we provide complexity results and propose exact and heuristic approaches when the attacker is naive. Our extensive experimental analysis demonstrates the effectiveness of our approaches.

AAMAS Conference 2018 Conference Paper

Mitigating the Curse of Correlation in Security Games by Entropy Maximization

• Haifeng Xu
• Shaddin Dughmi
• Milind Tambe
• Venil Loyd Noronha

In Stackelberg security games, a defender seeks to randomly allocate limited security resources to protect critical targets from an attack. In this paper, we study a fundamental, yet underexplored, phenomenon in security games, which we term the Curse of Correlation (CoC). Specifically, we observe that there are inevitable correlations among the protection status of different targets. Such correlation is a crucial concern, especially in spatio-temporal domains like conservation area patrolling, where attackers can surveil patrollers at certain areas and then infer their patrolling routes using such correlations. To mitigate this issue, we propose to design entropy-maximizing defending strategies for spatio-temporal security games, which frequently suffer from CoC. We prove that the problem is #P-hard in general. However, it admits efficient algorithms in well-motivated special settings.

AAAI Conference 2018 Conference Paper

Strategic Coordination of Human Patrollers and Mobile Sensors With Signaling for Security Games

• Haifeng Xu
• Kai Wang
• Phebe Vayanos
• Milind Tambe

Traditional security games concern the optimal randomized allocation of human patrollers, who can directly catch attackers or interdict attacks. Motivated by the emerging application of utilizing mobile sensors (e. g. , UAVs) for patrolling, in this paper we propose the novel Sensor-Empowered security Game (SEG) model which captures the joint allocation of human patrollers and mobile sensors. Sensors differ from patrollers in that they cannot directly interdict attacks, but they can notify nearby patrollers (if any). Moreover, SEGs incorporate mobile sensors’ natural functionality of strategic signaling. On the technical side, we first prove that solving SEGs is NP-hard even in zero-sum cases. We then develop a scalable algorithm SEGer based on the branch-and-price framework with two key novelties: (1) a novel MILP formulation for the slave; (2) an efficient relaxation of the problem for pruning. To further accelerate SEGer, we design a faster combinatorial algorithm for the slave problem, which is provably a constantapproximation to the slave problem in zero-sum cases and serves as a useful heuristic for general-sum SEGs. Our experiments demonstrate the significant benefit of utilizing mobile sensors.

SODA Conference 2018 Conference Paper

Targeting and Signaling in Ad Auctions

• Ashwinkumar Badanidiyuru
• Kshipra Bhawalkar
• Haifeng Xu

Modern ad auctions allow advertisers to target more specific segments of the user population. Unfortunately, this is not always in the best interest of the ad platform – partially hiding some information could be more beneficial for the platform's revenue. In this paper, we examine the following basic question in the context of second-price ad auctions: how should an ad platform optimally reveal information about the ad opportunity to the advertisers in order to maximize revenue? We consider a model in which bidders’ valuations depend on a random state of the ad opportunity. Different from previous work, we focus on a more practical, and challenging, situation where the space of possible realizations of ad opportunities is extremely large. We thus focus on developing algorithms whose running time is polynomial in the number of bidders, but is independent of the number of ad opportunity realizations. We assume that the auctioneer can commit to a signaling scheme to reveal noisy information about the realized state of the ad opportunity, and examine the auctioneer's algorithmic question of designing the optimal signaling scheme. We first consider that the auctioneer is restricted to send a public signal to all bidders. As a warm-up, we start with a basic (though less realistic) setting in which the auctioneer knows the bidders’ valuations, and show that an e -optimal scheme can be implemented in time polynomial in the number of bidders and 1/ ∊. We then move to a well-motivated Bayesian valuation setting in which the auctioneer and bidders both have private information, and present two results. First, we exhibit a characterization result regarding approximately optimal schemes and prove that any constant-approximate public signaling scheme must use exponentially many signals. Second, we present a “simple” public signaling scheme that serves as a constant approximation under mild assumptions. Finally, we initiate an exploration on the power of being able to send different signals privately to different bidders. In the basic setting where the auctioneer knows bidders’ valuations, we exhibit a polynomial-time private scheme that extracts almost full surplus even in the worst Bayes Nash equilibrium. This illustrates the surprising power of private signaling schemes in extracting revenue.

IJCAI Conference 2017 Conference Paper

Don't Bury your Head in Warnings: A Game-Theoretic Approach for Intelligent Allocation of Cyber-security Alerts

• Aaron Schlenker
• Haifeng Xu
• Mina Guirguis
• Christopher Kiekintveld
• Arunesh Sinha
• Milind Tambe
• Solomon Sonya
• Darryl Balderas

In recent years, there have been a number of successful cyber attacks on enterprise networks by malicious actors which have caused severe damage. These networks have Intrusion Detection and Prevention Systems in place to protect them, but they are notorious for producing a high volume of alerts. These alerts must be investigated by cyber analysts to determine whether they are an attack or benign. Unfortunately, there are magnitude more alerts generated than there are cyber analysts to investigate them. This trend is expected to continue into the future creating a need for tools which find optimal assignments of the incoming alerts to analysts in the presence of a strategic adversary. We address this challenge with the four following contributions: (1) a cyber screening game (CSG) model for the cyber network protection domain, (2) an NP-hardness proof for computing the optimal strategy for the defender, (3) an algorithm that finds the optimal allocation of experts to alerts in the CSG, and (4) heuristic improvements for computing allocations in CSGs that accomplishes significant scale-up which we show empirically to closely match the solution quality of the optimal algorithm.

IJCAI Conference 2017 Conference Paper

Maximizing Awareness about HIV in Social Networks of Homeless Youth with Limited Information

• Amulya Yadav
• Hau Chan
• Albert Xin Jiang
• Haifeng Xu
• Eric Rice
• Milind Tambe

This paper presents HEALER, a software agent that recommends sequential intervention plans for use by homeless shelters, who organize these interventions to raise awareness about HIV among homeless youth. HEALER's sequential plans (built using knowledge of social networks of homeless youth) choose intervention participants strategically to maximize influence spread, while reasoning about uncertainties in the network. While previous work presents influence maximizing techniques to choose intervention participants, they do not address two real-world issues: (i) they completely fail to scale up to real-world sizes; and (ii) they do not handle deviations in execution of intervention plans. HEALER handles these issues via two major contributions: (i) HEALER casts this influence maximization problem as a POMDP and solves it using a novel planner which scales up to previously unsolvable real-world sizes; and (ii) HEALER allows shelter officials to modify its recommendations, and updates its future plans in a deviation-tolerant manner. HEALER was deployed in the real world in Spring 2016 with considerable success.

STOC Conference 2016 Conference Paper

Algorithmic Bayesian persuasion

• Shaddin Dughmi
• Haifeng Xu

Persuasion, defined as the act of exploiting an informational advantage in order to effect the decisions of others, is ubiquitous. Indeed, persuasive communication has been estimated to account for almost a third of all economic activity in the US. This paper examines persuasion through a computational lens, focusing on what is perhaps the most basic and fundamental model in this space: the celebrated Bayesian persuasion model of Kamenica and Gentzkow. Here there are two players, a sender and a receiver. The receiver must take one of a number of actions with a-priori unknown payoff, and the sender has access to additional information regarding the payoffs of the various actions for both players. The sender can commit to revealing a noisy signal regarding the realization of the payoffs of various actions, and would like to do so as to maximize her own payoff in expectation assuming that the receiver rationally acts to maximize his own payoff. When the payoffs of various actions follow a joint distribution (the common prior), the sender's problem is nontrivial, and its computational complexity depends on the representation of this prior. We examine the sender's optimization task in three of the most natural input models for this problem, and essentially pin down its computational complexity in each. When the payoff distributions of the different actions are i.i.d. and given explicitly, we exhibit a polynomial-time (exact) algorithmic solution, and a ``simple'' (1-1/e)-approximation algorithm. Our optimal scheme for the i.i.d. setting involves an analogy to auction theory, and makes use of Border's characterization of the space of reduced-forms for single-item auctions. When action payoffs are independent but non-identical with marginal distributions given explicitly, we show that it is #P-hard to compute the optimal expected sender utility. In doing so, we rule out a generalized Border's theorem, as defined by Gopalan et al, for this setting. Finally, we consider a general (possibly correlated) joint distribution of action payoffs presented by a black box sampling oracle, and exhibit a fully polynomial-time approximation scheme (FPTAS) with a bi-criteria guarantee. Our FPTAS is based on Monte-Carlo sampling, and its analysis relies on the principle of deferred decisions. Moreover, we show that this result is the best possible in the black-box model for information-theoretic reasons.

AAMAS Conference 2016 Conference Paper

Playing Repeated Security Games with No Prior Knowledge

• Haifeng Xu
• Long Tran-Thanh
• Nicholas R. Jennings

This paper investigates repeated security games with unknown (to the defender) game payoffs and attacker behaviors. As existing work assumes prior knowledge about either the game payoffs or the attacker’s behaviors, they are not suitable for tackling our problem. Given this, we propose the first efficient defender strategy, based on an adversarial online learning framework, that can provably achieve good performance guarantees without any prior knowledge. In particular, we prove that our algorithm can achieve low performance loss against the best fixed strategy on hindsight (i. e. , having full knowledge of the attacker’s moves). In addition, we prove that our algorithm can achieve an efficient competitive ratio against the optimal adaptive defender strategy. We also show that for zero-sum security games, our algorithm achieves efficient results in approximating a number of solution concepts, such as algorithmic equilibria and the minimax value. Finally, our extensive numerical results demonstrate that, without having any prior information, our algorithm still achieves good performance, compared to state-of-the-art algorithms from the literature on security games, such as SUQR [19], which require significant amount of prior knowledge. General Terms Game theory; Security; Theory

AAMAS Conference 2016 Conference Paper

Signaling in Bayesian Stackelberg Games

• Haifeng Xu
• Rupert Freeman
• Vincent Conitzer
• Shaddin Dughmi
• Milind Tambe

Algorithms for solving Stackelberg games are used in an ever-growing variety of real-world domains. Previous work has extended this framework to allow the leader to commit not only to a distribution over actions, but also to a scheme for stochastically signaling information about these actions to the follower. This can result in higher utility for the leader. In this paper, we extend this methodology to Bayesian games, in which either the leader or the follower has payoff-relevant private information or both. This leads to novel variants of the model, for example by imposing an incentive compatibility constraint for each type to listen to the signal intended for it. We show that, in contrast to previous hardness results for the case without signaling [5, 16], we can solve unrestricted games in time polynomial in their natural representation. For security games, we obtain hardness results as well as efficient algorithms, depending on the settings. We show the benefits of our approach in experimental evaluations of our algorithms.

AAMAS Conference 2016 Conference Paper

Using Social Networks to Aid Homeless Shelters: Dynamic Influence Maximization under Uncertainty

• Amulya Yadav
• Hau Chan
• Albert Xin Jiang
• Haifeng Xu
• Eric Rice
• Milind Tambe

IJCAI Conference 2015 Conference Paper

Computing Optimal Mixed Strategies for Security Games with Dynamic Payoffs

• Yue Yin
• Haifeng Xu
• Jiarui Gan
• Bo An
• Albert Xin Jiang

Security agencies in the real world often need to protect targets with time-dependent values, e. g. , tourist sites where the number of travelers changes over time. Since the values of different targets often change asynchronously, the defender can relocate security resources among targets dynamically to make the best use of limited resources. We propose a game-theoretic scheme to develop dynamic, randomized security strategies in consideration of adversary’s surveillance capability. This differs from previous studies on security games by considering varying target values and continuous strategy spaces of the security agency and the adversary. The main challenge lies in the computational intensiveness due to the continuous, hence infinite strategy spaces. We propose an optimal algorithm and an arbitrarily near-optimal algorithm to compute security strategies under different conditions. Experimental results show that both algorithms significantly outperform existing approaches.

AAAI Conference 2015 Conference Paper

Exploring Information Asymmetry in Two-Stage Security Games

• Haifeng Xu
• Zinovi Rabinovich
• Shaddin Dughmi
• Milind Tambe

Stackelberg security games have been widely deployed to protect real-world assets. The main solution concept there is the Strong Stackelberg Equilibrium (SSE), which optimizes the defender’s random allocation of limited security resources. However, solely deploying the SSE mixed strategy has limitations. In the extreme case, there are security games in which the defender is able to defend all the assets “almost perfectly” at the SSE, but she still sustains significant loss. In this paper, we propose an approach for improving the defender’s utility in such scenarios. Perhaps surprisingly, our approach is to strategically reveal to the attacker information about the sampled pure strategy. Specifically, we propose a two-stage security game model, where in the first stage the defender allocates resources and the attacker selects a target to attack, and in the second stage the defender strategically reveals local information about that target, potentially deterring the attacker’s attack plan. We then study how the defender can play optimally in both stages. We show, theoretically and experimentally, that the two-stage security game model allows the defender to achieve strictly better utility than SSE.

IJCAI Conference 2015 Conference Paper

Security Games with Information Leakage: Modeling and Computation

• Haifeng Xu
• Albert Xing Jiang
• Arunesh Sinha
• Zinovi Rabinovich
• Shaddin Dughmi
• Milind Tambe

Most models of Stackelberg security games assume that the attacker only knows the defender’s mixed strategy, but is not able to observe (even partially) the instantiated pure strategy. Such partial observation of the deployed pure strategy – an issue we refer to as information leakage – is a significant concern in practical applications. While previous research on patrolling games has considered the attacker’s real-time surveillance, our settings, therefore models and techniques, are fundamentally different. More specifically, after describing the information leakage model, we start with an LP formulation to compute the defender’s optimal strategy in the presence of leakage. Perhaps surprisingly, we show that a key subproblem to solve this LP (more precisely, the defender oracle) is NP-hard even for the simplest of security game models. We then approach the problem from three possible directions: efficient algorithms for restricted cases, approximation algorithms, and heuristic algorithms for sampling that improves upon the status quo. Our experiments confirm the necessity of handling information leakage and the advantage of our algorithms.

AAAI Conference 2014 Conference Paper

Give a Hard Problem to a Diverse Team: Exploring Large Action Spaces

• Leandro Soriano Marcolino
• Haifeng Xu
• Albert Xin Jiang
• Milind Tambe
• Emma Bowring

Recent work has shown that diverse teams can outperform a uniform team made of copies of the best agent. However, there are fundamental questions that were not asked before. When should we use diverse or uniform teams? How does the performance change as the action space or the teams get larger? Hence, we present a new model of diversity for teams, that is more general than previous models. We prove that the performance of a diverse team improves as the size of the action space gets larger. Concerning the size of the diverse team, we show that the performance converges exponentially fast to the optimal one as we increase the number of agents. We present synthetic experiments that allow us to gain further insights: even though a diverse team outperforms a uniform team when the size of the action space increases, the uniform team will eventually again play better than the diverse team for a large enough action space. We verify our predictions in a system of Go playing agents, where we show a diverse team that improves in performance as the board size increases, and eventually overcomes a uniform team.

AAAI Conference 2014 Conference Paper

Solving Zero-Sum Security Games in Discretized Spatio-Temporal Domains

• Haifeng Xu
• Fei Fang
• Albert Jiang
• Vincent Conitzer
• Shaddin Dughmi
• Milind Tambe

Among the many deployment areas of Stackelberg Security games, a major area involves games played out in space and time, which includes applications in multiple mobile defender resources protecting multiple mobile targets. Previous algorithms for such spatio-temporal security games fail to scale-up and little is known of the computational complexity properties of these problems. This paper provides a novel oracle-based algorithmic framework for a systematic study of different problem variants of computing optimal (minimax) strategies in spatio-temporal security games. Our framework enables efficient computation of a minimax strategy when the problem admits a polynomial-time oracle. Furthermore, for the cases in which efficient oracles are difficult to find, we propose approximations or prove hardness results.