Counterfactual Regret Minimization (CFR) algorithms are widely used to compute a Nash equilibrium (NE) in two-player zero-sum imperfect-information extensive-form games (IIGs). Among them, Predictive CFR+ (PCFR+) is particularly powerful, achieving an exceptionally fast empirical convergence rate via the prediction in many games. However, the empirical convergence rate of PCFR+ would significantly degrade if the prediction is inaccurate, leading to unstable performance on certain IIGs. To enhance the robustness of PCFR+, we propose Asymmetric PCFR+ (APCFR+), which employs an adaptive asymmetry of step sizes between the updates of implicit and explicit accumulated counterfactual regrets to mitigate the impact of the prediction inaccuracy on convergence. We present a theoretical analysis demonstrating why APCFR+ can enhance the robustness. To the best of our knowledge, we are the first to propose the asymmetry of step sizes, a simple yet novel technique that effectively improves the robustness of PCFR+. Then, to reduce the difficulty of implementing APCFR+ caused by the adaptive asymmetry, we propose a simplified version of APCFR+ called Simple APCFR+ (SAPCFR+), which uses a fixed asymmetry of step sizes to enable only a single-line modification compared to original PCFR+. Experimental results on five standard IIG benchmarks and two heads-up no-limit Texas Hold’em (HUNL) Subagems show that (i) both APCFR+ and SAPCFR+ outperform PCFR+ in most of the tested games, (ii) SAPCFR+ achieves a comparable empirical convergence rate with APCFR+, and (iii) our approach can be generalized to improve other CFR algorithms, e.g., Discount CFR (DCFR).

Urban Network Security Games (UNSGs), which model the strategic allocation of limited security resources on city road networks, are critical for urban safety. However, finding a Nash Equilibrium (NE) in large-scale UNSGs is challenging due to their massive and combinatorial action spaces. One common approach to addressing these games is the Policy-Space Response Oracle (PSRO) framework, which requires computing best responses (BR) at each iteration. However, precisely computing exact BRs is impractical in large-scale games, and employing reinforcement learning to approximate BRs inevitably introduces errors that limit the overall effectiveness of the PSRO methods. Recent advancements in leveraging non-convex stochastic optimization to approximate an NE offer a promising alternative to the burdensome BR computation. However, utilizing existing stochastic optimization techniques with an unbiased loss function for UNSGs remains challenging because the action spaces are too vast to be effectively represented by neural networks. To address these issues, we introduce Tree-based Stochastic Optimization (TSO), a framework that bridges the gap between the stochastic optimization paradigm for NE-finding and the demands of UNSGs. Specifically, we employ the tree-based action representation that maps the whole action space onto a tree structure, addressing the challenge faced by neural networks in representing actions when the action space cannot be enumerated. We then incorporate this representation into the loss function and theoretically demonstrate its equivalence to the unbiased loss function. To further enhance the quality of the converged solution, we introduce a sample-and-prune mechanism that reduces the risk of being trapped in suboptimal local optima. Extensive experimental results indicate the superiority of TSO over other baseline algorithms in addressing the UNSGs.

With the construction of intelligent agents, coordinating a collection of agents to optimize long-term cumulative global reward is becoming increasingly important. To align individual agent actions with global rewards, the contribution of individual actions to global rewards needs to be determined, which is known as the structural credit assignment (SCA). Conventional SCA mechanisms are primarily based on neural networks, which lack theoretical foundations and preclude their application to model-based MAP tasks. Leveraging cooperative game theory, the main contribution of this study is to propose a novel Shapley value-based SCA (SV-SCA) that can be generalized to both MAP and MARL. Combining the distributed constraint optimization (DCOP) model and its reward structure, we propose a novel algorithm for computing the Shapley value while ensuring the efficiency and fairness of the SV-SCA. Particularly, based on SV-SCA, we design a coordinated Monte Carlo tree search (MCTS) for model-based MAP tasks and a fully-decentralized method for model-free MARL tasks. Theoretical analyses show that the proposed coordinated MCTS can guarantee the expected value of the global joint action, and that the proposed coordinated MARL is monotonic such that each agent optimizes its own rewards also optimize the system’s global reward. Finally, we conduct extensive experiments in typical sequential multiagent coordination domains. Our results demonstrate that the proposed coordinated MCTS and coordinated MARL outperform existing multiagent MCTS and MARL baselines in terms of solution quality and scalability.

In real-world information retrieval scenarios, addressing data incompleteness is crucial for providing accurate similarity scores and ensuring reliable results for downstream tasks. Previous Similarity Matrix Completion (SMC) methods aim to estimate a similarity matrix that exhibits positive semi-definiteness (PSD) from an inaccurate one. However, these methods are inadequate in cases where the initial similarity matrix$S^{0}$exhibits PSD. In this paper, we propose a novel SMC framework that simultaneously explores the symmetric, positive semi-definiteness (PSD), and low-rank properties to provide an accurate and efficient solution for similarity search tasks. Specifically, we exploit the low-rank property and introduce an efficient specialized Cholesky factorization (CF) technique into the conventional SMC framework, which is implemented via a regularizer. It improves computational efficiency by learning a smaller factorized matrix instead of the entire similarity matrix. Moreover, to enhance the optimality guarantees of SMC, we introduce a novel lower-rank matrix property and design two corresponding regularizers. Building upon these meticulous designs, our novel SMC framework, for the first time, ensures both efficiency and accuracy with theoretical guarantees. Consequently, we propose two novel algorithms, i.e., SMCFN/SMCRN, to implement the SMC framework. Theoretical analysis verifies the effectiveness and fast convergence speed of SMCFN/SMCRN. Extensive experiments on five real-world datasets validate our theoretical analysis: SMCFN/SMCRN achieves up to 42% lower RMSE (e.g., 0.34 vs. 0.59 on ImageNet) and 15% higher Recall than state-of-the-art baselines, while being the most efficient among all baseline methods.

Large language models (LLMs) are widely used in real-world applications, raising concerns about their safety and trustworthiness. While red-teaming with jailbreak prompts exposes the vulnerabilities of LLMs, current efforts focus primarily on single-turn attacks, overlooking the multi-turn strategies used by real-world adversaries. Existing multi-turn methods rely on static patterns or predefined logical chains, failing to account for the dynamic strategies during attacks. We propose Siren, a learning-based multi-turn attack framework designed to simulate real-world human jailbreak behaviors. Siren consists of three stages: (1) MiniMax-driven training set construction utilizing Turn-Level LLM feedback, (2) post-training attackers with supervised fine-tuning (SFT) and direct preference optimization (DPO), and (3) interactions between the attacking and target LLMs. Experiments demonstrate that Siren achieves an attack success rate (ASR) of 90% with LLaMA-3-8B as the attacker against Gemini-1.5-Pro as the target model, and 70% with Mistral-7B against GPT-4o, significantly outperforming single-turn baselines. Moreover, Siren with a 7B-scale model achieves performance comparable to a multi-turn baseline that leverages GPT-4o as the attacker, while requiring fewer turns and employing decomposition strategies that are better semantically aligned with attack goals. We hope Siren inspires the development of stronger defenses against advanced multi-turn jailbreak attacks under realistic scenarios. Code is available at https://github.com/YiyiyiZhao/siren. Warning: This paper contains potentially harmful text.

Nash equilibrium (NE) plays an important role in game theory. How to efficiently compute an NE in NFGs is challenging due to its complexity and non-convex optimization property. Machine Learning (ML), the cornerstone of modern artificial intelligence, has demonstrated remarkable empirical performance across various applications including non-convex optimization. To leverage non-convex stochastic optimization techniques from ML for approximating an NE, various loss functions have been proposed. Among these, only one loss function is unbiased, allowing for unbiased estimation under the sampled play. Unfortunately, this loss function suffers from high variance, which degrades the convergence rate. To improve the convergence rate by mitigating the high variance associated with the existing unbiased loss function, we propose a novel surrogate loss function named Nash Advantage Loss (NAL). NAL is theoretically proved unbiased and exhibits significantly lower variance than the existing unbiased loss function. Experimental results demonstrate that the algorithm minimizing NAL achieves a significantly faster empirical convergence rates compared to other algorithms, while also reducing the variance of estimated loss value by several orders of magnitude.

To establish last-iterate convergence for Counterfactual Regret Minimization (CFR) algorithms in learning a Nash equilibrium (NE) of extensive-form games (EFGs), recent studies reformulate learning an NE of the original EFG as learning the NEs of a sequence of (perturbed) regularized EFGs. Hence, proving last-iterate convergence in solving the original EFG reduces to proving last-iterate convergence in solving (perturbed) regularized EFGs. However, these studies only establish last-iterate convergence for Online Mirror Descent (OMD)-based CFR algorithms instead of Regret Matching (RM)-based CFR algorithms in solving perturbed regularized EFGs, resulting in a poor empirical convergence rate, as RM-based CFR algorithms typically outperform OMD-based CFR algorithms. In addition, as solving multiple perturbed regularized EFGs is required, fine-tuning across multiple perturbed regularized EFGs is infeasible, making parameter-free algorithms highly desirable. This paper show that CFR$^+$, a classical parameter-free RM-based CFR algorithm, achieves last-iterate convergence in learning an NE of perturbed regularized EFGs. This is the first parameter-free last-iterate convergence for RM-based CFR algorithms in perturbed regularized EFGs. Leveraging CFR$^+$ to solve perturbed regularized EFGs, we get Reward Transformation CFR$^+$ (RTCFR$^+$). Importantly, we extend prior work on the parameter-free property of CFR$^+$, enhancing its stability, which is vital for the empirical convergence of RTCFR$^+$. Experiments show that RTCFR$^+$ exhibits a significantly faster empirical convergence rate than existing algorithms that achieve theoretical last-iterate convergence. Interestingly, RTCFR$^+$ show performance no worse than average-iterate convergence CFR algorithms. It is the first last-iterate convergence algorithm to achieve such performance. Our code is available at https://github.com/menglinjian/NeurIPS-2025-RTCFR.

Regret Matching$^+$ (RM$^+$) variants are widely used to build superhuman Poker AIs, yet few studies investigate their last-iterate convergence in learning a Nash equilibrium (NE). Although their last-iterate convergence is established for games satisfying the Minty Variational Inequality (MVI), no studies have demonstrated that these algorithms achieve such convergence in the broader class of games satisfying the weak MVI. A key challenge in proving last-iterate convergence for RM$^+$ variants in games satisfying the weak MVI is that even if the game's loss gradient satisfies the weak MVI, RM$^+$ variants operate on a transformed loss feedback which does not satisfy the weak MVI. To provide last-iterate convergence for RM$^+$ variants, we introduce a concise yet novel proof paradigm that involves: (i) transforming an RM$^+$ variant into an Online Mirror Descent (OMD) instance that updates within the original strategy space of the game to recover the weak MVI, and (ii) showing last-iterate convergence by proving the distance between accumulated regrets converges to zero via the recovered weak MVI of the feedback. Inspired by our proof paradigm, we propose Smooth Optimistic Gradient Based RM$^+$ (SOGRM$^+$) and show that it achieves last-iterate and finite-time best-iterate convergence in learning an NE of games satisfying the weak MVI, the weakest condition among all known RM$^+$ variants. Experiments show that SOGRM$^+$ significantly outperforms other algorithms. Our code is available at https://github.com/menglinjian/NeurIPS-2025-SOGRM.

How might reinforcement-learning based covert social influence operations (CSIOs) be run, given that the CSIO agent wants to maximize influence and minimize discoverability of malicious accounts? And how successful can they be, given that both social platform bot detectors and humans might report them to the social platform? To answer these questions, we propose RL_CSIO, a methodology based on reinforcement learning (RL) for running CSIOs. We ran 4 CSIOs with IRB-approval over a period of 5 days using a panel of 225 human subjects. We explore 8 research questions based on the data collected. The results show that RL_CSIO agents successfully trade off influence and discoverability - but in ways that are nuanced and unexpected.

Many works recently have focused on computing optimal solutions for the ex ante coordination of a team for solving sequential adversarial team games, where a team of players coordinate against an opponent (or a team of players) in a zero-sum extensive-form game. However, it is challenging to directly compute such an optimal solution because the team’s coordinated strategy space is exponential in the size of the game tree due to the asymmetric information of team members. Column Generation (CG) algorithms have been proposed to overcome this challenge by iteratively expanding the team’s coordinated strategy space via a Best Response Oracle (BRO). More recently, more compact representations (particularly, the Team Belief Directed Acyclic Graph (TB-DAG)) of the team’s coordinated strategy space have been proposed, but the TB-DAG-based algorithms only outperform the CG-based algorithms in games with a small TB-DAG. Unfortunately, it is inefficient to directly apply CG to the TB-DAG because the size of the TB-DAG is still exponential in the size of the game tree and then makes the BRO unscalable. To this end, we develop our novel TB-DAG CG (DCG) algorithm framework by computing a coordinated best response in the original game first and then transforming this strategy into the TB-DAG form. To further improve the scalability, we propose a more suitable BRO for DCG to reduce the cost of the transformation at each iteration. We theoretically show that our algorithm converges exponentially faster than the state-of-the-art CG algorithms, and experimental results show that our algorithm is at least two orders of magnitude faster than the state-of-the-art baselines.

Sharpness-Aware Minimization (SAM), which performs gradient descent on adversarially perturbed weights, can improve generalization by identifying flatter minima. However, recent studies have shown that SAM may suffer from convergence instability and oscillate around saddle points, resulting in slow convergence and inferior performance. To address this problem, we propose the use of a lookahead mechanism to gather more information about the landscape by looking further ahead, and thus find a better trajectory to converge. By examining the nature of SAM, we simplify the extrapolation procedure, resulting in a more efficient algorithm. Theoretical results show that the proposed method converges to a stationary point and is less prone to saddle points. Experiments on standard benchmark datasets also verify that the proposed method outperforms the SOTAs, and converge more effectively to flat minima.

The similarity matrix is at the core of similarity search problems. However, incomplete observations are ubiquitous in real scenarios leading to a less accurate similarity matrix. To alleviate this problem, in this paper, based on the key insight that the similarity matrix enjoys both the symmetric and positive semi-definiteness (PSD) properties, we propose a novel similarity matrix calibration method, which is scalable, effective, and sound. Specifically, we establish the PSD property as a constraint for the similarity matrix calibration problem and propose a novel similarity matrix calibration method to estimate the similarity matrix, which approximates the unknown complete ground-truth similarity matrix. To enable a fast optimization process, we further develop a general approximated algorithm that bypasses the computation of singular values. Theoretical analysis ensures stable calibration performance and convergence speed. Extensive experiments of similarity matrix calibration on real-world datasets demonstrate that our proposed method outperforms baseline methods in terms of both accuracy and speed.

Fake reviews are having a devastating negative influence on online shopping sites. The proliferation of fake reviews is exacerbated by the presence of SockFarms, companies that create and operate huge sets of sockpuppet accounts to promote their customers’ products by posting fake reviews. Our proposed SockAttack algorithm allows such companies to optimize their actions to maximize profits. We show that SockAttack compromises the F1-score of four well-known review fraud detection engines on real-world datasets (up to 27.1% more than baselines). We then propose a defense algorithm called SockDef and show that it mitigates the impact of SockAttack (up to 69.2% with respect to F1-score).

There are many applications where an autonomous agent can perform many sets of actions. It must choose one set of actions based on some behavioral constraints on the agent. Past work has used deontic logic to declaratively express such constraints in logic, and developed the concept of a feasible status set (FSS), a set of actions that satisfy these constraints. However, multiple FSSs may exist and an agent needs to choose one in order to act. As there may be many different objective functions to evaluate status sets, we propose the novel concept of Pareto-optimal FSSs or POSS. We show that checking if a status set is a POSS is co-NP-hard. We develop an algorithm to find a POSS and in special cases when the objective functions are monotonic (or anti-monotonic), we further develop more efficient algorithms. Finally, we conduct experiments to show the efficacy of our approach and we discuss possible ways to handle multiple Pareto-optimal Status Sets.

Months may pass before the victim of IP theft even knows they have been compromised. During this time, the attacker can exfiltrate large amounts of data. Recent work has proposed the idea of injecting a set of believable fake versions of a real document into a network so that the attacker has to expend time and effort to identify the real document from a sea of similar documents. In this paper, we consider the problem of an attacker who is smart and breaks a technical document down into small, bit-sized “units” and inspects them one by one so as to defeat the fake document defense. If a unit in a document is determined to be fake, the adversary does not need to look further at the same document. He can also immediately identify as fake, any other document that contains the same unit. In this paper, we consider the problem of a smart attacker using this strategy. Our proposed defensive algorithm, called${\sf GAIT}$, is shown to be successful in mitigating such attacks.${\sf GAIT}$can work in conjunction with any NLP-based generative method to create fake technical documents.

Drone based terrorist attacks are increasing daily. It is not expected to be long before drones are used to carry out terror attacks in urban areas. We have developed the DUCK multi-agent testbed that security agencies can use to simulate drone-based attacks by diverse actors and develop a combination of surveillance camera, drone, and cyber defenses against them.

Pursuit-evasion games on graphs model the coordination of police forces chasing a fleeing felon in real-world urban settings, using the standard framework of imperfect-information extensive-form games (EFGs). In recent years, solving EFGs has been largely dominated by the Policy-Space Response Oracle (PSRO) methods due to their modularity, scalability, and favorable convergence properties. However, even these methods quickly reach their limits when facing large combinatorial strategy spaces of the pursuit-evasion games. To improve their efficiency, we integrate the pre-training and fine-tuning paradigm into the core module of PSRO -- the repeated computation of the best response. First, we pre-train the pursuer's policy base model against many different strategies of the evader. Then we proceed with the PSRO loop and fine-tune the pre-trained policy to attain the pursuer's best responses. The empirical evaluation shows that our approach significantly outperforms the baselines in terms of speed and scalability, and can solve even games on street maps of megalopolises with tens of thousands of crossroads -- a scale beyond the effective reach of previous methods.

Designing efficient algorithms to compute a Nash Equilibrium (NE) in multiplayer games is still an open challenge. In this paper, we focus on computing an NE that optimizes a given objective function. For example, when there is a team of players independently playing against an adversary in a game (e.g., several groups in a forest trying to interdict illegal loggers in green security games), these team members may need to find an NE minimizing the adversary’s utility. Finding an optimal NE in multiplayer games can be formulated as a mixed-integer bilinear program by introducing auxiliary variables to represent bilinear terms, leading to a huge number of bilinear terms, making it hard to solve. To overcome this challenge, we first propose a general framework for this formulation based on a set of correlation plans. We then develop a novel algorithm called CRM based on this framework, which uses correlation plans with their relations to strictly reduce the feasible solution space after the convex relaxation of bilinear terms while minimizing the number of correlation plans to significantly reduce the number of bilinear terms. We show that our techniques can significantly reduce the time complexity and CRM can be several orders of magnitude faster than the state-of-the-art baseline.

Efficient algorithms computing a Nash equilibrium have been successfully applied to large zero- sum two-player extensive-form games (e.g., poker). However, in multiplayer games, computing a Nash equilibrium is generally hard, and the equilibria are not exchangeable, which makes players face the problem of selecting one of many different Nash equilibria. In this paper, we focus on an alternative solution concept in zero-sum multiplayer extensive-form games called Team-Maxmin Equilibrium (TME). It is a Nash equilibrium that maximizes each team member’s utility. As TME is unique in general, it avoids the equilibrium selection problem. However, it is still difficult (FNP- hard) to find a TME. Computing it can be formulated as a non-convex program, but existing algorithms are capable of solving this program for only very small games. In this paper, we first refine the complexity result for computing a TME by using a correlation plan to show that a TME can be found in polynomial time in a specific class of games according to our boundary for complexity. Second, we propose an efficient correlation-based algorithm to solve the non-convex program for TME in games not belonging to this class. The algorithm combines two special correlation plans based on McCormick envelopes for convex relaxation and von Stengel-Forges polytope for correlated equilibria. We show that restricting the feasible solution space to von Stengel-Forges polytope will strictly reduce the feasible solution space after convex re- laxation of nonlinear terms. Finally, experiments show that our algorithm is about four orders of magnitude faster than the prior state of the art and can solve many previously unsolvable games.

Computational game theory has many applications in the modern world in both adversarial situations and the optimization of social good. While there exist many algorithms for computing solutions in two-player interactions, finding optimal strategies in multiplayer interactions efficiently remains an open challenge. This paper focuses on computing the multiplayer Team-Maxmin Equilibrium with Coordination device (TMECor) in zero-sum extensive-form games. TMECor models scenarios when a team of players coordinates ex ante against an adversary. Such situations can be found in card games (e.g., in Bridge and Poker), when a team works together to beat a target player but communication is prohibited; and also in real world, e.g., in forest-protection operations, when coordinated groups have limited contact during interdicting illegal loggers. The existing algorithms struggle to find a TMECor efficiently because of their high computational costs. To compute a TMECor in larger games, we make the following key contributions: (1) we propose a hybrid-form strategy representation for the team, which preserves the set of equilibria; (2) we introduce a column-generation algorithm with a guaranteed finite-time convergence in the infinite strategy space based on a novel best-response oracle; (3) we develop an associated-representation technique for the exact representation of the multilinear terms in the best-response oracle; and (4) we experimentally show that our algorithm is several orders of magnitude faster than prior state-of-the-art algorithms in large games.

In many real-world scenarios, a team of agents must coordinate with each other to compete against an opponent. The challenge of solving this type of game is that the team's joint action space grows exponentially with the number of agents, which results in the inefficiency of the existing algorithms, e.g., Counterfactual Regret Minimization (CFR). To address this problem, we propose a new framework of CFR: CFR-MIX. Firstly, we propose a new strategy representation that represents a joint action strategy using individual strategies of all agents and a consistency relationship to maintain the cooperation between agents. To compute the equilibrium with individual strategies under the CFR framework, we transform the consistency relationship between strategies to the consistency relationship between the cumulative regret values. Furthermore, we propose a novel decomposition method over cumulative regret values to guarantee the consistency relationship between the cumulative regret values. Finally, we introduce our new algorithm CFR-MIX which employs a mixing layer to estimate cumulative regret values of joint actions as a non-linear combination of cumulative regret values of individual actions. Experimental results show that CFR-MIX outperforms existing algorithms on various games significantly.

Securing networked infrastructures is important in the real world. The problem of deploying security resources to protect against an attacker in networked domains can be modeled as Network Security Games (NSGs). Unfortunately, existing approaches, including the deep learning-based approaches, are inefficient to solve large-scale extensive-form NSGs. In this paper, we propose a novel learning paradigm, NSG-NFSP, to solve large-scale extensive-form NSGs based on Neural Fictitious Self-Play (NFSP). Our main contributions include: i) reforming the best response (BR) policy network in NFSP to be a mapping from action-state pair to action-value, to make the calculation of BR possible in NSGs; ii) converting the average policy network of an NFSP agent into a metric-based classifier, helping the agent to assign distributions only on legal actions rather than all actions; iii) enabling NFSP with high-level actions, which can benefit training efficiency and stability in NSGs; and iv) leveraging information contained in graphs of NSGs by learning efficient graph node embeddings. Our algorithm significantly outperforms state-of-the-art algorithms in both scalability and solution quality.

The study of finding the equilibrium for multiplayer games is challenging. This paper focuses on computing Team-Maxmin Equilibria (TMEs) in zero-sum multiplayer Extensive-Form Games (EFGs), which describes the optimal strategies for a team of players who share the same goal but they take actions independently against an adversary. TMEs can capture many realistic scenarios, including: 1) a team of players play against a target player in poker games; and 2) defense resources schedule and patrol independently in security games. However, the study of efficiently finding TMEs within any given accuracy in EFGs is almost completely unexplored. To fill this gap, we first study the inefficiency caused by computing the equilibrium where team players correlate their strategies and then transforming it into the mixed strategy profile of the team and show that this inefficiency can be arbitrarily large. Second, to efficiently solve the non-convex program for finding TMEs directly, we develop the Associated Recursive Asynchronous Multiparametric Disaggregation Technique (ARAMDT) to approximate multilinear terms in the program with two novel techniques: 1) an asynchronous precision method to reduce the number of constraints and variables for approximation by using different precision levels to approximate these terms; and 2) an associated constraint method to reduce the feasible solution space of the mixed-integer linear program resulting from ARAMDT by exploiting the relation between these terms. Third, we develop a novel iterative algorithm to efficiently compute TMEs within any given accuracy based on ARAMDT. Our algorithm is orders of magnitude faster than baselines in the experimental evaluation.

Efficiently computing equilibria for multiplayer games is still an open challenge in computational game theory. This paper focuses on computing Team-Maxmin Equilibria (TMEs), which is an important solution concept for zero-sum multiplayer games where players in a team having the same utility function play against an adversary independently. Existing algorithms are inefficient to compute TMEs in large games, especially when the strategy space is too large to be represented due to limited memory. In two-player games, the Incremental Strategy Generation (ISG) algorithm is an efficient approach to avoid enumerating all pure strategies. However, the study of ISG for computing TMEs is completely unexplored. To fill this gap, we first study the properties of ISG for multiplayer games, showing that ISG converges to a Nash Equilibrium (NE) but may not converge to a TME. Second, we design an ISG variant for TMEs (ISGT) by exploiting that a TME is an NE maximizing the team’s utility and show that ISGT converges to a TME and the impossibility of relaxing conditions in ISGT. Third, to further improve the scalability, we design an ISGT variant (CISGT) by using the strategy space for computing an equilibrium that is close to a TME but is easier to be computed as the initial strategy space of ISGT. Finally, extensive experimental results show that CISGT is orders of magnitude faster than ISGT and the state-of-the-art algorithm to compute TMEs in large games.

Most violent crimes happen in urban and suburban cities. With emerging tracking techniques, law enforcement officers can have real-time location information of the escaping criminals and dynamically adjust the security resource allocation to interdict them. Unfortunately, existing work on urban network security games largely ignores such information. This paper addresses this omission. First, we show that ignoring the real-time information can cause an arbitrarily large loss of efficiency. To mitigate this loss, we propose a novel NEtwork purSuiT game (NEST) model that captures the interaction between an escaping adversary and a defender with multiple resources and real-time information available. Second, solving NEST is proven to be NP-hard. Third, after transforming the non-convex program of solving NEST to a linear program, we propose our incremental strategy generation algorithm, including: (i) novel pruning techniques in our best response oracle; and (ii) novel techniques for mapping strategies between subgames and adding multiple best response strategies at one iteration to solve extremely large problems. Finally, extensive experiments show the effectiveness of our approach, which scales up to realistic problem sizes with hundreds of nodes on networks including the real network of Manhattan.

Preventing crimes or terrorist attacks in urban areas is challenging. Law enforcement officers need to respond quickly to catch the attacker on his escape route, which is subject to time-dependent traffic conditions on transportation networks. The attacker can strategically choose his escape path and driving speed to avoid being captured. Existing work on security resource allocation has not considered such scenarios with time-dependent strategies for both players. Therefore, in this paper, we study the problem of efficiently scheduling security resources for interdicting the escaping attacker. We propose: 1) a new defender-attacker security game model for escape interdiction on transportation networks; and 2) an efficient double oracle algorithm to compute the optimal defender strategy, which combines mixed-integer linear programming formulations for best response problems and effective approximation algorithms for improving the scalability of the algorithms. Experimental evaluation shows that our approach significantly outperforms baselines in solution quality and scales up to realistic-sized transportation networks with hundreds of intersections.

Psychological experiment studies reveal that human interaction behaviors are often not the same as what game theory predicts. One of important reasons is that they did not put relevant constraints into consideration when the players choose their best strategies. However, in real life, games are often played in certain contexts where players are constrained by their capabilities, law, culture, custom, and so on. For example, if someone wants to drive a car, he/she has to have a driving license. Therefore, when a human player of a game chooses a strategy, he/she should consider not only the material payoff or monetary reward from taking his/her best strategy and others' best responses but also how feasible to take the strategy in that context where the game is played. To solve such a game, this paper establishes a model of fuzzily constrained games and introduces a solution concept of constrained equilibrium for the games of this kind. Our model is consistent with psychological experiment results of ultimatum games. We also discuss what will happen if Prisoner's Dilemma and Stag Hunt are played under fuzzy constraints. In general, after putting constraints into account, our model can reflect well the human behaviors of fairness, altruism, self-interest, and so on, and thus can predict the outcomes of some games more accurate than conventional game theory.

Bayesian games can handle the incomplete information about players' types. However, in real life, the information could be not only incomplete but also ambiguous for lack of sufficient evidence, i.e., a player cannot have a probability precisely about each type of the other players. To address this issue, we extend the Bayesian games to ambiguous Bayesian games. We also illustrate and analyse our game model.

Nowadays, decisions in estate investment are made by a group of investors with different demands and then how to find an agreement among them become an essential issue. Thus, this paper introduces a fuzzy logic based bargaining model to solve such problems. Moreover, we also do lots of simulation experiments to reveal how bargainers risk attitude, patience and regret degree influence the outcome of a game, and benchmark our model with the previous one. From these experiments, we can conclude that our model can reflect the human intuitions well, has a higher success rate, and bargains more efficiently than the previous one.

In this paper, we develop a fuzzy dynamic belief revision logic system. In our system, propositions take truth values in a set of multiple fuzzy linguistic terms, which people use in everyday life. And we use a uninorm operator to aggregate the linguistic truth values of the same proposition but drawn from two different rules because uninorms can reflect well that the aggregated result of two somehow negative truth values of the same proposition should be more negative, the aggregated result of two somehow positive ones should be more positive, and the result of a negative one and a positive one is a compromise. In this system, the belief on a proposition is the linguistic truth of the proposition in the most possible world according to the current preference over all possible worlds. In the light of new information, the preference degrees of possible worlds will be updated. Accordingly, the most possible world will be changed to another and thus an old belief on a propositional formula will be changed to the linguistic truth of the proposition in the new most possible world. Moreover, we prove the soundness and completeness of our fuzzy dynamic belief revision system. In addition, we also prove that our belief revision method in fuzzy environment satisfies some relevant ones of standard AGM postulates (named after the names of their proponents, Alchourrón, Gärdenfors, and Makinson).

Bayesian games can handle the incomplete information about players' types. However, in real life, the information could be not only incomplete but also ambiguous for lack of sufficient evidence, i.e., a player cannot have a precise probability about each type of the other players. To address this issue, this paper firstly extends the Bayesian games to ambiguous Bayesian games. Then, we introduce the concept of a solution to this kind of games and discuss their properties, especially about solution existence, how the ambiguity degree and players' ambiguity attitude influence the outcomes of an ambiguous Bayesian game, the case of lower boundary probability, and the missing situation. We also illustrate our game model, especially in the public security domain.

This paper proposes a fuzzy approach for reasoning about action and change in timed domains. In our method, actions and world states are modeled as fuzzy sets over time axis. Thus, their temporal relations and time constraints can be modeled as fuzzy rules. So, our method handles well the issue that action happens at an approximate time and then the states also change at an approximate time, which has not been solved well in the existing work. Finally, our method is used to solve the classic problem of rail-road crossing control in a fuzzy environment. The theoretical and simulation analysis shows that the controller using our method works well.