VLDB 2026 Research / reviewers in the wild / expert
Christopher Kiekintveld
dblp:95/1694 · also Christopher D. Kiekintveld
· DBLP profile ↗
41ranked-venue papers
3as first author
8since 2021 · last 2025
0000-0003-0615-9584ORCID · verified
Domains — the database's venue-derived domains; a paper can count in several
Artificial intelligence and machine learning · 30 · 2 first-author · 1 since 2021Graphics, computer vision, multimedia, augmented reality and games · 19 · 1 first-authorSecurity and privacy · 6 · 1 first-author · 2 since 2021Computer networks · 3 · 3 since 2021Theory of computation · 3 · 1 first-authorApplied, interdisciplinary, general and emerging computing · 2
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2025 | MAD-OOD: A Deep Learning Cluster-Driven Framework for an Out-of-Distribution Malware Detection and ClassificationabstractOut-of-distribution (OOD) detection in malware classification remains a significant challenge due to the high intra-class variability among malware variants within the same family. Existing deep learning approaches often overlook this intra-family variation, resulting in suboptimal detection performance. This research proposes a two-stage framework that addresses this limitation by incorporating Gaussian discriminant analysis (GDA) into deep neural networks to model spherical decision boundaries around malware families in the embedding space. The first stage employs unsupervised cluster analysis to determine whether a test sample is in-distribution or out-of-distribution, using z-score-based statistical analysis for reliable outlier detection. The second stage introduces a deep learning model trained on refined embeddings from the initial stage, using predictions from both the cluster analysis and a primary classifier to enhance final prediction accuracy. Evaluation on a dataset comprising 25 malware families and novel OOD samples demonstrates superior performance, achieving an AUC of 0.911 for OOD detection. This approach significantly improves the distinguishability of OOD samples and offers a scalable and statistically grounded method for robust out-of-distribution malware classification and anomaly detection in security contexts. Tosin Ige, Christopher Kiekintveld, Aritran Piplai, Asif Rahman, Olukunle Kolade, Sasidhar Kunapuli |
TrustCom | 2 |
| 2024 | Towards an in-Depth Evaluation of the Performance, Suitability and Plausibility of Few-Shot Meta Transfer Learning on An Unknown Out-of-Distribution Cyber-attack DetectionabstractThe emergence of few-shot learning as a potential approach to address the problem of data scarcity by learning underlying pattern from a few training sample had so far given a mix-result especially on the suitability of model-agnostic meta learning, transfer learning, and optimization strategy to rapidly learn valid information from few sample. In this research, we did an in-depth evaluation of meta- learning to determine their plausibility and suitability for previously unknown cyberattack detection by first retrieving the original research artifacts of current state of the art meta learning to repeat the experiment with original dataset before replicating the experiment with two different malware dataset which had not been previously done with meta-transfer learning. On each of the experiments, meta-transfer learning gave good results on digital character recognition dataset but abysmal result on Malimg and Malevis malware images datasets thereby indicating its unreliability for detecting cyberattacks and the need for an improvement to the state-of-the-art meta transfer learning towards a better attack detection. Transfer learning performance is independent on imbalance and hence does not influence its performance since both malware dataset used for this experiment result in high validation loss and balancing the dataset doesn't result in reduced validation loss,the successful learning transfer seen on digital character recognition dataset is not unconnected to the fact that several languages have similar characters and digits thereby enhancing the successful learning transfer unlike malware datasets, and more importantly the finding that current meta-learning transfer approach doesn't generalize well on malware dataset and hence not suitable for detecting previously unseen out-of-distribution attack. Tosin Ige, Christopher Kiekintveld, Aritran Piplai, Amy Wagler, Olukunle Kolade, Bolanle Hafiz Matti |
ISNCC | 2 |
| 2024 | An in-Depth Investigation Into the Performance of State-of-the-Art Zero-Shot, Single-Shot, and Few-Shot Learning Approaches on an Out-of-Distribution Zero-Day Malware Attack DetectionabstractN-shot learning has emerge in recent year as poten-tial learning approach to solve the problem of data scarcity by learning underlying pattern from a few training sample. Despite recent state-of-the-art research on model-agnostic metal learning, transfer learning, and optimization strategy to rapidly learn valid information from few sample, there remains a big challenge on an actual out-of-distribution zero-day without any similarity to previously known malware family or new variant of an existing malware family. This ultimately questions the effectiveness of cur-rent state-of-the-art few-shot learning approach. In this research, we did an in-depth investigation into the performance of state-of-the-art Zero-shot, Single-shot, and few-shot learning approaches on zero-day out-of-distribution malware attack detection based on their static properties using Malimg and Malevis mal ware dataset. We ensure our model was aware of an out-of-distribution class during training while varying the number of samples in the out-of-distribution class accordingly zero-shot(no sample), single-shot (1 sample), few-shot(S samples) while using confusion matrix to get the actual number of correct prediction on out-of-distribution mal ware validation samples. we assert that the model should be smart enough to detect and classify previously unseen data into an empty family as an out-of-distribution considering that the model was made to be aware of the existence of such distribution during training. Result shows 0, 0, and 3 correct out-of-distribution predictions on Zero-shot, single-shot, and few-shot experiments respectively, thereby showing limitation of the current state-of-the-art N-shot approaches on out-of-distribution attack. Tosin Ige, Christopher Kiekintveld, Aritran Piplai, Amy Wagler, Olukunle Kolade, Bolanle Hafiz Matti |
ISNCC | 2 |
| 2023 | A Systematic Approach for Temporal Traffic Selection Across Various ApplicationsabstractThe paper presents a framework that analyzes temporal traffic in applications, with a focus on statistical analysis and traffic classification. The framework utilizes time-based sampling and traffic flow selection to identify the characteristics of idle time, continuous traffic and burst threshold. It also includes time-based feature selection to improve the accuracy and efficiency of predictive models by removing irrelevant or redundant features. Our study involves exploratory data analysis and machine learning-based classification, and we found that our method improves application analysis in both statistical analysis and the precision of encrypted application traffic. We compared our approach to various state-of-the-art methods and consistently outperformed them in terms of performance. By focusing on traffic classification, our framework can benefit various domains such as Quality of Service (QoS) and security. For example, it can help network administrators identify and analyze various application characteristics, which can lead to better security measures. Overall, our approach offers a promising solution for improving temporal traffic analysis. Nazia Sharmin, Jaime C. Acosta, Christopher Kiekintveld |
ICCCN | 3 |
| 2023 | Optimizing Crop Recommendations for Sustainable Agriculture: Leveraging Bayesian Networks in a Smart Crop Recommendation SystemabstractAgriculture faces challenges in terms of productivity and sustainability, particularly in developing countries. This paper presents a smart crop recommendation system that utilizes a Bayesian model to provide personalized recommendations based on site-specific parameters. The model incorporates Bayesian Belief Network (BBN) which incorporates climate data, soil characteristics, and historical yield data, enabling probabilistic reasoning and the evaluation of parameter impacts. The model takes uncertainties into account and dynamically adjusts recommendations, considering farmers’ preferences and constraints. Our model demonstrates both high predictive accuracy and the ability to adapt to existing structures and learning algorithms, resulting in an overall enhanced performance. By leveraging data learning and Bayesian networks, this approach enhances agricultural productivity, sustainability, and personalized decision-making. Nazia Sharmin, Christopher Kiekintveld |
SECON | 2 |
| 2023 | Solving zero-sum one-sided partially observable stochastic games
Karel Horák 0002, Branislav Bosanský, Vojtech Kovarík, Christopher Kiekintveld |
Artif. Intell. | 4 |
| 2022 | Honeypot Allocation for Cyber Deception Under UncertaintyabstractCyber deception aims to misrepresent the state of the network to mislead the attackers, falsify their reconnaissance conclusions, and deflect them away from their goals. Honeypots serve as decoy devices inside networks that can capture adversaries for monitoring purposes. We propose a two-phase deception approach based on honeypot allocation. In the first phase, we develop a proactive deceptive honeypot allocation policy, the second phase proposes a reactive deception approach that dynamically allocates honeypots according to IDS updates. Considering a practical scenario, the defender partially monitors the adversary’s activities. To this end, we develop our deception approach using a combination of game-theoretic and reinforcement learning models. We cast the problem of reactive deception as a partially observable Markov decision process (POMDP) based on a game-theoretic dynamic model to accommodate the imperfect monitoring of the actions taken by the attacker. We solve this combined partially observable game model using Monte-Carlo tree search to overcome the game model complexity. We give a game-theoretic analysis to explain the attack-defense policies at equilibrium. Finally, we present numerical results to validate the effectiveness of the proposed deception approach. Ahmed H. Anwar, Charles A. Kamhoua, Nandi Leslie, Christopher Kiekintveld |
IEEE Trans. Netw. Serv. Manag. | 4 |
| 2021 | Lightweight On-Demand Honeypot Deployment for Cyber Deception
Jaime C. Acosta, Anjon Basak, Christopher Kiekintveld, Charles A. Kamhoua |
ICDF2C | 3 |
| 2020 | Local Context Normalization: Revisiting Local NormalizationabstractNormalization layers have been shown to improve convergence in deep neural networks, and even add useful inductive biases. In many vision applications the local spatial context of the features is important, but most common normalization schemes including Group Normalization (GN), Instance Normalization (IN), and Layer Normalization (LN) normalize over the entire spatial dimension of a feature. This can wash out important signals and degrade performance. For example, in applications that use satellite imagery, input images can be arbitrarily large; consequently, it is nonsensical to normalize over the entire area. Positional Normalization (PN), on the other hand, only normalizes over a single spatial position at a time. A natural compromise is to normalize features by local context, while also taking into account group level information. In this pa- per, we propose Local Context Normalization (LCN): a normalization layer where every feature is normalized based on a window around it and the filters in its group. We propose an algorithmic solution to make LCN efficient for arbitrary window sizes, even if every point in the image has a unique window. LCN outperforms its Batch Normalization (BN), GN, IN, and LN counterparts for object detection, semantic segmentation, and instance segmentation applications in several benchmark datasets, while keeping performance in- dependent of the batch size and facilitating transfer learning. Anthony Ortiz, Caleb Robinson, Dan Morris 0001, Olac Fuentes, Christopher Kiekintveld, Mahmudulla Hassan, Nebojsa Jojic |
CVPR | 5 |
| 2020 | Cybersecurity Methodology for Specialized Behavior Analysis
Edgar Padilla, Jaime C. Acosta, Christopher Kiekintveld |
ICDF2C | 3 |
| 2020 | Game-Theoretic Perspectives and Algorithms for CybersecurityabstractInformation plays a key role in many games, and game theory includes reasoning about how agents should perceive signals, and how they should strategically decide what signals to send. This can involve complex tradeoffs about how revealing certain information will affect the beliefs and actions of other players. I will overview some basic approaches for modeling information in game theory, such as signaling games, and applications to games such as Poker. The second part of the talk with focus on our work applying game theoretic models and algorithms in cybersecurity. I will discuss how we apply game theory to optimize strategies for deception in cybersecurity, including honeypots, honey traffic, and other deceptive objects. I will also cover work that considers dynamic deception using sequential models that capture uncertainty. Finally, I will discuss some recent work in adversarial learning and connections between this area and game theory. Christopher Kiekintveld |
IH&MMSec | 1 |
| 2019 | Evaluating Models of Human Behavior in an Adversarial Multi-Armed Bandit Problem
Marcus Paul Gutierrez, Jakub Cerný, Noam Ben-Asher, Efrat Aharonov-Majar, Branislav Bosanský, Christopher Kiekintveld, Cleotilde Gonzalez |
CogSci | 6 |
| 2019 | Compact Representation of Value Function in Partially Observable Stochastic GamesabstractValue methods for solving stochastic games with partial observability model the uncertainty of the players as a probability distribution over possible states, where the dimension of the belief space is the number of states. For many practical problems, there are exponentially many states which causes scalability problems. We propose an abstraction technique that addresses this curse of dimensionality by projecting the high-dimensional beliefs onto characteristic vectors of significantly lower dimension (e.g., marginal probabilities). Our main contributions are (1) a novel compact representation of the uncertainty in partially observable stochastic games and (2) a novel algorithm using this representation that is based on existing state-of-the-art algorithms for solving stochastic games with partial observability. Experimental evaluation confirms that the new algorithm using the compact representation dramatically increases scalability compared to the state of the art. Karel Horák 0002, Branislav Bosanský, Christopher Kiekintveld, Charles A. Kamhoua |
IJCAI | 3 |
| 2019 | Hardening networks against strategic attackers using attack graph games
Karel Durkota, Viliam Lisý, Branislav Bosanský, Christopher Kiekintveld, Michal Pechoucek |
Comput. Secur. | 4 |
| 2019 | Optimizing honeypot strategies against dynamic lateral movement using partially observable stochastic games
Karel Horák 0002, Branislav Bosanský, Petr Tomásek, Christopher Kiekintveld, Charles A. Kamhoua |
Comput. Secur. | 4 |
| 2018 | Bidding in Periodic Double Auctions Using Heuristics and Dynamic Monte Carlo Tree SearchabstractIn a Periodic Double Auction (PDA), there are multiple discrete trading periods for a single type of good. PDAs are commonly used in real-world energy markets to trade energy in specific time slots to balance demand on the power grid. Strategically, bidding in a PDA is complicated because the bidder must predict and plan for future auctions that may influence the bidding strategy for the current auction. We present a general bidding strategy for PDAs based on forecasting clearing prices and using Monte Carlo Tree Search (MCTS) to plan a bidding strategy across multiple time periods. In addition, we present a fast heuristic strategy that can be used either as a standalone method or as an initial set of bids to seed the MCTS policy. We evaluate our bidding strategies using a PDA simulator based on the wholesale market implemented in the Power Trading Agent Competition (PowerTAC) competition. We demonstrate that our strategies outperform state-of-the-art bidding strategies designed for that competition. Moinul Morshed Porag Chowdhury, Christopher Kiekintveld, Son Tran, William Yeoh 0001 |
IJCAI | 2 |
| 2018 | Stackelberg Security Games: Looking Beyond a Decade of SuccessabstractThe Stackelberg Security Game (SSG) model has been immensely influential in security research since it was introduced roughly a decade ago. Furthermore, deployed SSG-based applications are one of most successful examples of game theory applications in the real world. We present a broad survey of recent technical advances in SSG and related literature, and then look to the future by highlighting the new potential applications and open research problems in SSG. Arunesh Sinha, Fei Fang 0001, Bo An 0001, Christopher Kiekintveld, Milind Tambe |
IJCAI | 4 |
| 2018 | Incremental Strategy Generation for Stackelberg Equilibria in Extensive-Form GamesabstractDynamic interaction appears in many real-world scenarios where players are able to observe (perhaps imperfectly) the actions of another player and react accordingly. We consider the baseline representation of dynamic games - the extensive form - and focus on computing Stackelberg equilibrium (SE), where the leader commits to a strategy to which the follower plays a best response. For one-shot games (e.g., security games), strategy-generation (SG) algorithms offer dramatic speed-up by incrementally expanding the strategy spaces. However, a direct application of SG to extensive-form games (EFGs) does not bring a similar speed-up since it typically results in a nearly-complete strategy space. Our contributions are twofold: (1) for the first time we introduce an algorithm that allows us to incrementally expand the strategy space to find a SE in EFGs; (2) we introduce a heuristic variant of the algorithm that is theoretically incomplete, but in practice allows us to find exact (or close-to optimal) Stackelberg equilibrium by constructing a significantly smaller strategy space. Our experimental evaluation confirms that we are able to compute SE by considering only a fraction of the strategy space that often leads to a significant speed-up in computation times. Jakub Cerný, Branislav Bosanský, Christopher Kiekintveld |
EC | 3 |
| 2017 | Comparing Strategic Secrecy and Stackelberg Commitment in Security GamesabstractThe Strong Stackelberg Equilibrium (SSE) has drawn extensive attention recently in several security domains. However, the SSE concept neglects the advantage of defender's strategic revelation of her private information, and overestimates the observation ability of the adversaries. In this paper, we overcome these restrictions and analyze the tradeoff between strategic secrecy and commitment in security games. We propose a Disguised-resource Security Game (DSG) where the defender strategically disguises some of her resources. We compare strategic information revelation with public commitment and formally show that they have different advantages depending the payoff structure. To compute the Perfect Bayesian Equilibrium (PBE), several novel approaches are provided, including a novel algorithm based on support set enumeration, and an approximation algorithm for \epsilon-PBE. Extensive experimental evaluation shows that both strategic secrecy and Stackelberg commitment are critical measures in security domain, and our approaches can efficiently solve PBEs for realistic-sized problems. Qingyu Guo, Bo An 0001, Branislav Bosanský, Christopher Kiekintveld |
IJCAI | 4 |
| 2017 | Don't Bury your Head in Warnings: A Game-Theoretic Approach for Intelligent Allocation of Cyber-security AlertsabstractIn 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. Aaron Schlenker, Mina Guirguis, Christopher Kiekintveld, Arunesh Sinha, Milind Tambe, Solomon Y. Sonya, Darryl Balderas, Noah Dunstatter |
IJCAI | 4 |
| 2016 | Using Correlated Strategies for Computing Stackelberg Equilibria in Extensive-Form GamesabstractStrong Stackelberg Equilibrium (SSE) is a fundamental solution concept in game theory in which one player commits to a strategy, while the other player observes this commitment and plays a best response. We present a new algorithm for computing SSE for two-player extensive-form general-sum games with imperfect information (EFGs) where computing SSE is an NP-hard problem. Our algorithm is based on a correlated version of SSE, known as Stackelberg Extensive-Form Correlated Equilibrium (SEFCE). Our contribution is therefore twofold: (1) we give the first linear program for computing SEFCE in EFGs without chance, (2) we repeatedly solve and modify this linear program in a systematic search until we arrive to SSE. Our new algorithm outperforms the best previous algorithms by several orders of magnitude. Jiri Cermak, Branislav Bosanský, Karel Durkota, Viliam Lisý, Christopher Kiekintveld |
AAAI | 5 |
| 2016 | Preventing Illegal Logging: Simultaneous Optimization of Resource Teams and Tactics for SecurityabstractGreen security — protection of forests, fish and wildlife — is a critical problem in environmental sustainability. We focus on the problem of optimizing the defense of forests againstillegal logging, where often we are faced with the challenge of teaming up many different groups, from national police to forest guards to NGOs, each with differing capabilities and costs. This paper introduces a new, yet fundamental problem: SimultaneousOptimization of Resource Teams and Tactics (SORT). SORT contrasts with most previous game-theoretic research for green security — in particular based onsecurity games — that has solely focused on optimizing patrolling tactics, without consideration of team formation or coordination. We develop new models and scalable algorithms to apply SORT towards illegal logging in large forest areas. We evaluate our methods on a variety of synthetic examples, as well as a real-world case study using data from our on-going collaboration in Madagascar. Sara Marie McCarthy, Milind Tambe, Christopher Kiekintveld, Meredith L. Gore, Alex Killion |
AAAI | 3 |
| 2016 | Teaching Automated Strategic Reasoning Using Capstone TournamentsabstractCourses in artificial intelligence and related topics often cover methods for reasoning under uncertainty, decision theory, and game theory. However, these methods can seem very abstract when students first encounter them, and they are often taught using simple “toy” problems. Our goal is to help students to operationalize this knowledge by designing sophisticated autonomous agents that must make complex decisions in games that capture their interest. We describe a tournament-based pedagogy that we have used in two different courses with two different games based on current research topics in artificial intelligence to engage students in designing agents that use strategic reasoning. Many students find this structure very engaging, and we find that students develop a deeper understanding of the abstract strategic reasoning concepts introduced in the courses. Oscar Veliz, Marcus Paul Gutierrez, Christopher Kiekintveld |
AAAI | 3 |
| 2016 | Optimizing Personalized Email Filtering Thresholds to Mitigate Sequential Spear Phishing AttacksabstractHighly targeted spear phishing attacks are increasingly common, and have been implicated in many major security breeches. Email filtering systems are the first line of defense against such attacks. These filters are typically configured with uniform thresholds for deciding whether or not to allow a message to be delivered to a user. However, users have very significant differences in both their susceptibility to phishing attacks as well as their access to critical information and credentials that can cause damage. Recent work has considered setting personalized thresholds for individual users based on a Stackelberg game model. We consider two important extensions of the previous model. First, in our model user values can be substitutable, modeling cases where multiple users provide access to the same information or credential. Second, we consider attackers who make sequential attack plans based on the outcome of previous attacks. Our analysis starts from scenarios where there is only one credential and then extends to more general scenarios with multiple credentials. For single-credential scenarios, we demonstrate that the optimal defense strategy can be found by solving a binary combinatorial optimization problem called PEDS. For multiple-credential scenarios, we formulate it as a bilevel optimization problem for finding the optimal defense strategy and then reduce it to a single level optimization problem called PEMS using complementary slackness conditions. Experimental results show that both PEDS and PEMS lead to significant higher defender utilities than two existing benchmarks in different parameter settings. Also, both PEDS and PEMS are more robust than the existing benchmarks considering uncertainties. Mengchen Zhao, Bo An 0001, Christopher Kiekintveld |
AAAI | 3 |
| 2015 | Combining Compact Representation and Incremental Generation in Large Games with Sequential StrategiesabstractMany search and security games played on a graph can be modeled as normal-form zero-sum games with strategies consisting of sequences of actions. The size of the strategy space provides a computational challenge when solving these games. This complexity is tackled either by using the compact representation of sequential strategies and linear programming, or by incremental strategy generation of iterative double-oracle methods. In this paper, we present novel hybrid of these two approaches: compact-strategy double-oracle (CS-DO) algorithm that combines the advantages of the compact representation with incremental strategy generation. We experimentally compare CS-DO with the standard approaches and analyze the impact of the size of the support on the performance of the algorithms. Results show that CS-DO dramatically improves the convergence rate in games with non-trivial support Branislav Bosanský, Albert Xin Jiang, Milind Tambe, Christopher Kiekintveld |
AAAI | 4 |
| 2015 | Optimal Network Security Hardening Using Attack Graph Games
Karel Durkota, Viliam Lisý, Branislav Bosanský, Christopher Kiekintveld |
IJCAI | 4 |
| 2014 | An extended study on multi-objective security games
Matthew Brown 0002, Bo An 0001, Christopher Kiekintveld, Fernando Ordóñez, Milind Tambe |
Auton. Agents Multi Agent Syst. | 3 |
| 2014 | An Exact Double-Oracle Algorithm for Zero-Sum Extensive-Form Games with Imperfect InformationabstractDeveloping scalable solution algorithms is one of the central problems in computational game theory. We present an iterative algorithm for computing an exact Nash equilibrium for two-player zero-sum extensive-form games with imperfect information. Our approach combines two key elements: (1) the compact sequence-form representation of extensive-form games and (2) the algorithmic framework of double-oracle methods. The main idea of our algorithm is to restrict the game by allowing the players to play only selected sequences of available actions. After solving the restricted game, new sequences are added by finding best responses to the current solution using fast algorithms. We experimentally evaluate our algorithm on a set of games inspired by patrolling scenarios, board, and card games. The results show significant runtime improvements in games admitting an equilibrium with small support, and substantial improvement in memory use even on games with large support. The improvement in memory use is particularly important because it allows our algorithm to solve much larger game instances than existing linear programming methods. Our main contributions include (1) a generic sequence-form double-oracle algorithm for solving zero-sum extensive-form games; (2) fast methods for maintaining a valid restricted game model when adding new sequences; (3) a search algorithm and pruning methods for computing best-response sequences; (4) theoretical guarantees about the convergence of the algorithm to a Nash equilibrium; (5) experimental analysis of our algorithm on several games, including an approximate version of the algorithm. Branislav Bosanský, Christopher Kiekintveld, Viliam Lisý, Michal Pechoucek |
J. Artif. Intell. Res. | 2 |
| 2013 | Improving resource allocation strategies against human adversaries in security games: An extended study
Rong Yang 0001, Christopher Kiekintveld, Fernando Ordóñez, Milind Tambe, Richard John |
Artif. Intell. | 2 |
| 2012 | Security Games with Limited SurveillanceabstractRandomized first-mover strategies of Stackelberg games are used in several deployed applications to allocate limited resources for the protection of critical infrastructure. Stackelberg games model the fact that a strategic attacker can surveil and exploit the defender's strategy, and randomization guards against the worst effects by making the defender less predictable. In accordance with the standard game-theoretic model of Stackelberg games, past work has typically assumed that the attacker has perfect knowledge of the defender's randomized strategy and will react correspondingly. In light of the fact that surveillance is costly, risky, and delays an attack, this assumption is clearly simplistic: attackers will usually act on partial knowledge of the defender's strategies. The attacker's imperfect estimate could present opportunities and possibly also threats to a strategic defender.In this paper, we therefore begin a systematic study of security games with limited surveillance. We propose a natural model wherein an attacker forms or updates a belief based on observed actions, and chooses an optimal response. We investigate the model both theoretically and experimentally. In particular, we give mathematical programs to compute optimal attacker and defender strategies for a fixed observation duration, and show how to use them to estimate the attacker's observation durations. Our experimental results show that the defender can achieve significant improvement in expected utility by taking the attacker's limited surveillance into account, validating the motivation of our work. Bo An 0001, David Kempe 0001, Christopher Kiekintveld, Eric Anyung Shieh, Satinder Singh 0001, Milind Tambe, Yevgeniy Vorobeychik |
AAAI | 3 |
| 2012 | TRUSTS: Scheduling Randomized Patrols for Fare Inspection in Transit SystemsabstractIn proof-of-payment transit systems, passengers are legally required to purchase tickets before entering but are not physically forced to do so. Instead, patrol units move about the transit system, inspecting the tickets of passengers, who face fines if caught fare evading. The deterrence of such fines depends on the unpredictability and effectiveness of the patrols. In this paper, we present TRUSTS, an application for scheduling randomized patrols for fare inspection in transit systems. TRUSTS models the problem of computing patrol strategies as a leader-follower Stackelberg game where the objective is to deter fare evasion and hence maximize revenue. This problem differs from previously studied Stackelberg settings in that the leader strategies must satisfy massive temporal and spatial constraints; moreover, unlike in these counterterrorism-motivated Stackelberg applications, a large fraction of the ridership might realistically consider fare evasion, and so the number of followers is potentially huge. A third key novelty in our work is deliberate simplification of leader strategies to make patrols easier to be executed. We present an efficient algorithm for computing such patrol strategies and present experimental results using real-world ridership data from the Los Angeles Metro Rail system. The Los Angeles County Sheriff’s department has begun trials of TRUSTS. Zhengyu Yin, Albert Xin Jiang, Matthew P. Johnson 0001, Christopher Kiekintveld, Kevin Leyton-Brown, Tuomas Sandholm, Milind Tambe, John P. Sullivan |
IAAI | 4 |
| 2011 | Refinement of Strong Stackelberg Equilibria in Security GamesabstractGiven the real-world deployments of attacker-defender Stackelberg security games, robustness to deviations from expected attacker behaviors has now emerged as a critically important issue. This paper provides four key contributions in this context. First, it identifies a fundamentally problematic aspect of current algorithms for security games. It shows that there are many situations where these algorithms face multiple equilibria, and they arbitrarily select one that may hand the defender a significant disadvantage, particularly if the attacker deviates from its equilibrium strategies due to unknown constraints. Second, for important subclasses of security games, it identifies situations where we will face such multiple equilibria. Third, to address these problematic situations, it presents two equilibrium refinement algorithms that can optimize the defender's utility if the attacker deviates from equilibrium strategies. Finally, it experimentally illustrates that the refinement approach achieved significant robustness in consideration of attackers' deviation due to unknown constraints. Bo An 0001, Milind Tambe, Fernando Ordóñez, Eric Anyung Shieh, Christopher Kiekintveld |
AAAI | 5 |
| 2011 | GUARDS - Innovative Application of Game Theory for National Airport Security
James Pita, Milind Tambe, Christopher Kiekintveld, Shane Cullen, Erin Steigerwald |
IJCAI | 3 |
| 2011 | Improving Resource Allocation Strategy against Human Adversaries in Security GamesabstractRecent real-world deployments of Stackelberg se-curity games make it critical that we address hu-man adversaries ’ bounded rationality in comput-ing optimal strategies. To that end, this paper provides three key contributions: (i) new efficient algorithms for computing optimal strategic solu-tions using Prospect Theory and Quantal Response Equilibrium; (ii) the most comprehensive experi-ment to date studying the effectiveness of different models against human subjects for security games; and (iii) new techniques for generating representa-tive payoff structures for behavioral experiments in generic classes of games. Our results with human subjects show that our new techniques outperform the leading contender for modeling human behav-ior in security games. 1 Rong Yang 0001, Christopher Kiekintveld, Fernando Ordóñez, Milind Tambe, Richard John |
IJCAI | 2 |
| 2011 | Stackelberg vs. Nash in Security Games: An Extended Investigation of Interchangeability, Equivalence, and UniquenessabstractThere has been significant recent interest in game-theoretic approaches to security, with much of the recent research focused on utilizing the leader-follower Stackelberg game model. Among the major applications are the ARMOR program deployed at LAX Airport and the IRIS program in use by the US Federal Air Marshals (FAMS). The foundational assumption for using Stackelberg games is that security forces (leaders), acting first, commit to a randomized strategy; while their adversaries (followers) choose their best response after surveillance of this randomized strategy. Yet, in many situations, a leader may face uncertainty about the followers surveillance capability. Previous work fails to address how a leader should compute her strategy given such uncertainty. We provide five contributions in the context of a general class of security games. First, we show that the Nash equilibria in security games are interchangeable, thus alleviating the equilibrium selection problem. Second, under a natural restriction on security games, any Stackelberg strategy is also a Nash equilibrium strategy; and furthermore, the solution is unique in a class of security games of which ARMOR is a key exemplar. Third, when faced with a follower that can attack multiple targets, many of these properties no longer hold. Fourth, we show experimentally that in most (but not all) games where the restriction does not hold, the Stackelberg strategy is still a Nash equilibrium strategy, but this is no longer true when the attacker can attack multiple targets. Finally, as a possible direction for future research, we propose an extensive-form game model that makes the defenders uncertainty about the attackers ability to observe explicit. Dmytro Korzhyk, Zhengyu Yin, Christopher Kiekintveld, Vincent Conitzer, Milind Tambe |
J. Artif. Intell. Res. | 3 |
| 2010 | Security Games with Arbitrary Schedules: A Branch and Price ApproachabstractSecurity games, and important class of Stackelberg games, are used in deployed decision-support tools in use by LAX police and the Federal Air Marshals Service. The algorithms used to solve these games find optimal randomized schedules to allocate security resources for infrastructure protection. Unfortunately, the state of the art algorithms either fail to scale or to provide a correct solution for large problems with arbitrary scheduling constraints. We introduce ASPEN, a branch-and-price approach that overcomes these limitations based on two key contributions: (i) A column-generation approach that exploits a novel network flow representation, avoiding a combinatorial explosion of schedule allocations; (ii) A branch-and-bound algorithm that generates bounds via a fast algorithm for solving security games with relaxed scheduling constraints. ASPEN is the first known method for efficiently solving massive security games with arbitrary schedules. Erim Kardes, Christopher Kiekintveld, Fernando Ordóñez, Milind Tambe |
AAAI | 3 |
| 2010 | Urban Security: Game-Theoretic Resource Allocation in Networked DomainsabstractLaw enforcement agencies frequently must allocate limited resources to protect targets embedded in a network, such as important buildings in a city road network. Since intelligent attackers may observe and exploit patterns in the allocation, it is crucial that the allocations be randomized. We cast this problem as an attacker-defender Stackelberg game: the defender’s goal is to obtain an optimal mixed strategy for allocating resources. The defender’s strategy space is exponential in the number of resources, and the attacker’s exponential in the network size. Existing algorithms are therefore useless for all but the smallest networks. We present a solution approach based on two key ideas: (i) A polynomial-sized game model obtained via an approximation of the strategy space, solved efficiently using a linear program; (ii) Two efficient techniques that map solutions from the approximate game to the original, with proofs of correctness under certain assumptions. We present in-depth experimental results, including an evaluation on part of the Mumbai road network. Jason Tsai, Zhengyu Yin, Jun-young Kwak, David Kempe 0001, Christopher Kiekintveld, Milind Tambe |
AAAI | 5 |
| 2007 | Empirical Game-Theoretic Methods for Strategy Design and Analysis in Complex Games
Christopher Kiekintveld |
AAAI | 1 |
| 2006 | Controlling a supply chain agent using value-based decompositionabstractWe present and evaluate the design of Deep Maize, our entry in the 2005 Trading Agent Competition Supply Chain Management scenario. The central idea is to decompose the problem by estimating the value of key resources in the game. We first create a high-level production schedule that considers cross-cutting constraints and future decisions, but abstracts aways from the details of sales and purchasing. We then make specific sales and purchasing decisions separately, coordinating these decisions with the high-level schedule using resource values derived from the schedule. All of these decisions are made using approximate optimization techniques and make use of explicit predictions about market conditions. Deep Maize was one of the most successful agents in the 2005 tournament, both in overall performance and on specific measures that emphasize coordination. Christopher Kiekintveld, Patrick R. Jordan, Michael P. Wellman |
EC | 1 |
| 2006 | Empirical mechanism design: methods, with application to a supply-chain scenarioabstractOur proposed methods employ learning and search techniques to estimate outcome features of interest as a function of mechanism parameter settings. We illustrate our approach with a design task from a supply-chain trading competition. Designers adopted several rule changes in order to deter particular procurement behavior, but the measures proved insufficient. Our empirical mechanism analysis models the relation between a key design parameter and outcomes, confirming the observed behavior and indicating that no reasonable parameter settings would have been likely to achieve the desired effect. More generally, we show that under certain conditions, the estimator of optimal mechanism parameter setting based on empirical data is consistent. Yevgeniy Vorobeychik, Christopher Kiekintveld, Michael P. Wellman |
EC | 2 |
| 2005 | Strategic Interactions in a Supply Chain GameabstractThe TAC 2003 supply-chain game presented automated trading agents with a challenging strategic problem. Embedded within a high-dimensional stochastic environment was a pivotal strategic decision about initial procurement of components. Early evidence suggested that the entrant field was headed toward a self-destructive, mutually unprofitable equilibrium. Our agent, Deep Maize, introduced a preemptive strategy designed to neutralize aggressive procurement, perturbing the field to a more profitable equilibrium; it worked. Not only did preemption improve Deep Maize's profitability, it improved profitability for the whole field. Whereas it is perhaps counterintuitive that action designed to prevent others from achieving their goals actually helps them, strategic analysis employing an empirical game-theoretic methodology verifies and provides insight about this outcome. Michael P. Wellman, Joshua Estelle, Satinder Singh 0001, Yevgeniy Vorobeychik, Christopher Kiekintveld, Vishal Soni |
Comput. Intell. | 5 |