We propose a combinatorial optimisation model called Limited Query Graph Connectivity Test.  We consider a graph whose edges have two possible states (On/Off).  The edges' states are hidden initially. We could query an edge to reveal its state.  Given a source s and a destination t, we aim to test s-t connectivity by identifying either a path (consisting of only On edges) or a cut (consisting of only Off edges). We are limited to B queries, after which we stop regardless of whether graph connectivity is established.  We aim to design a query policy that minimizes the expected number of queries.

Our model is mainly motivated by a cyber security use case where we need to establish whether an attack path exists in a network, between a source (i.e., a compromised user node) and a destination (i.e., a high-privilege admin node).  Edge query is resolved by manual effort from the IT admin, which is the motivation behind query minimization.

Our model is highly related to monotone Stochastic Boolean Function Evaluation (SBFE).  There are two existing exact algorithms for SBFE that are prohibitively expensive.  We propose a significantly more scalable exact algorithm.  While previous exact algorithms only scale for trivial graphs (i.e., past works experimented on at most 20 edges), we empirically demonstrate that our algorithm is scalable for a wide range of much larger practical graphs (i.e., Windows domain network graphs with tens of thousands of edges).

We propose three heuristics. Our best-performing heuristic is via reducing the search horizon of the exact algorithm. The other two are via reinforcement learning (RL) and Monte Carlo tree search (MCTS).  We also derive an anytime algorithm for computing the performance lower bound. Experimentally, we show that all our heuristics are near optimal.  The exact algorithm based heuristic outperforms all, surpassing RL, MCTS and 8 existing heuristics ported from SBFE and related literature.

Limited Query Graph Connectivity Test | VIDEO

We study worst-case VCG redistribution mechanism design for the public project problem.  The mechanism design task comes down to designing a payment function that maximizes the worst-case allocative efficiency ratio.

We use a multilayer perceptron (MLP) with ReLU activation to model the payment function and use mixed integer programming (MIP) to solve for the worst-case type profiles that maximally violate the mechanism design constraints. We collect these worst-case type profiles and use them as training samples to train toward better worst-case mechanisms.

In practice, we require a tiny neural network structure for the above approach to scale.  The Lottery Ticket Hypothesis states that a large network is likely to contain a "winning ticket" -- a much smaller subnetwork that "won the initialization lottery", which makes its training particularly effective.  Motivated by this hypothesis, we train a large network and prune it into a tiny subnetwork.  We run MIP-based worst-case training on the drawn subnetwork and evaluate the resulting mechanism's worst-case performance.  If the subnetwork does not achieve good worst-case performance, then we record the type profiles that cause the current draw to be bad.  To draw again, we restore the large network to its initial weights and prune using recorded type profiles from earlier draws, therefore avoiding drawing the same ticket twice.  We expect to eventually encounter a tiny subnetwork that leads to effective training for our worst-case mechanism design task.  Lastly, a by-product of multiple ticket draws is an ensemble of mechanisms with different worst cases, which improves the worst-case performance further.

Using our approach, we find previously unknown optimal mechanisms for up to 5 agents. Our results confirm the tightness of existing theoretical upper bounds.  For up to 20 agents, we derive significantly improved worst-case mechanisms, surpassing a long list of existing manual results.

Worst-Case VCG Redistribution Mechanism Design Based on the Lottery Ticket Hypothesis | VIDEO

Active Directory (AD) is the default security management system for Windows domain networks.  An AD environment naturally describes an attack graph where nodes represent computers/accounts/security groups, and edges represent existing accesses/known exploits that allow the attacker to gain access from one node to another.  Motivated by practical AD use cases, we study a Stackelberg game between one attacker and one defender.  There are multiple entry nodes for the attacker to choose from and there is a single target (Domain Admin).  Every edge has a failure rate.  The attacker chooses the attack path with the maximum success rate.  The defender can block a limited number of edges (i.e., revoke accesses) from a set of blockable edges, limited by budget. The defender's aim is to minimize the attacker's success rate.

We exploit the tree-likeness of practical AD graphs to design scalable algorithms.  We propose two novel methods that combine theoretical fixed parameter analysis and practical optimisation techniques.

For graphs with small tree widths, we propose a tree decomposition based dynamic program.  We then propose a general method for converting tree decomposition based dynamic programs to reinforcement learning environments, which leads to an anytime algorithm that scales better, but loses the optimality guarantee.

For graphs with small numbers of non-splitting paths (a parameter we invent specifically for AD graphs), we propose a kernelization technique that significantly downsizes the model, which is then solved via mixed-integer programming.

Experimentally, our algorithms scale to handle synthetic AD graphs with tens of thousands of nodes.

Scalable Edge Blocking Algorithms for Defending Active Directory Style Attack Graphs

Active Directory is the default security management system for Windows domain networks. We study the shortest path edge interdiction problem for defending Active Directory style attack graphs. The problem is formulated as a Stackelberg game between one defender and one attacker. The attack graph contains one destination node and multiple entry nodes. The attacker's entry node is chosen by nature. The defender chooses to block a set of edges limited by his budget. The attacker then picks the shortest unblocked attack path. The defender aims to maximize the expected shortest path length for the attacker, where the expectation is taken over entry nodes.
 
 We observe that practical Active Directory attack graphs have small maximum attack path length and are structurally close to trees. We first show that even if the maximum attack path length is a constant, the problem is still w[1]-hard with respect to the defender's budget. Having a small maximum attack path length and a small budget is not enough to design fixed-parameter algorithms. If we further assume that the number of entry nodes is small, then we derive a fixed-parameter tractable algorithm.
 
 We then propose two other fixed-parameter algorithms by exploiting the tree-like features. One is based on tree decomposition and requires a small tree width. The other assumes a small number of splitting nodes (nodes with multiple out-going edges). Finally, the last algorithm is converted into a graph convolutional neural network based heuristic, which scales to larger graphs with more splitting nodes.

Practical Fixed-Parameter Algorithms for Defending Active Directory Style Attack Graphs

We study mechanism design for nonexcludable and excludable binary public project problems. We aim to maximize the expected number of consumers and the expected agents' welfare. For the nonexcludable public project model, we identify a sufficient condition on the prior distribution for the conservative equal costs mechanism to be the optimal strategy-proof and individually rational mechanism. For general distributions, we propose a dynamic program that solves for the optimal mechanism. For the excludable public project model, we identify a similar sufficient condition for the serial cost sharing mechanism to be optimal for 2 and 3 agents. We derive a numerical upper bound. Experiments show that for several common distributions, the serial cost sharing mechanism is close to optimality.

Mechanism Design for Public Projects via Neural Networks

Main Track - Search and Optimisation

technical paper

We are pleased to announce the Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24), which will be held in Vancouver, British Columbia at the Vancouver Convention Centre – West Building from 20-27 February, 2024.

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-24 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and a range of other activities to be announced.

We expect for AAAI-24 to be an in-person conference – one author of all accepted papers will be expected to present work in person unless there are exceptional circumstances that prevent this.

In order to access the AAAI-24 event page you need to register [here](https://aaai.org/aaai-conference/registration/)

AAAI 2024

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. 

Main Track - Game Theory and Economic Paradigms

GTEP: Game Theory and Economic Paradigms / MAS: Multiagent Systems

poster

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-23 is the Thirty-Seventh AAAI Conference on Artificial Intelligence. The theme of this conference is to create collaborative bridges within and beyond AI. Like previous AAAI conferences, AAAI-23 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and two new activities: a Bridge Program and a Lab Program. Many of these activities are tailored to the theme of bridges and all are selected according to the highest standards, with additional programs for students and young researchers. 
AAAI is providing you with a conference planner, which you can use to help organize your itinerary of activities. This includes talks to attend in person, talks to attend remotely, breaks with colleagues and your site seeing activities. To access this conference planner, please go to [https://aaai-2023.takemobi.io](https://aaai-2023.takemobi.io).

In order to access this site, you need to register. If you haven't already, please register [here](https://aaai.org/Conferences/AAAI-23/registration/).


AAAI 2023

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines.

Main_Track

The purpose of the AAAI conference is to promote research in artificial intelligence (AI) and scientific exchange among AI researchers, practitioners, scientists, and engineers in affiliated disciplines. 

AAAI 2022

S2: Game Theory 2

AAMAS is the largest and most influential conference in the area of agents and multiagent systems, bringing together researchers and practitioners in all areas of agent technology and providing and internationally renowned high-profile forum for publishing and finding out about the latest developments in the field. AAMAS is the flagship conference of the non-profit International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).  

![](https://assets.underline.io/uploads/markdown_image/1/image/ce4604bd54468a006164d16e080204fb.jpg)

Please click on the button below to register for this event.

If you are registered and see this page please check the account email you are logged in with. It must be the same as for the registration.

If you still have trouble accessing the contact please contact support at aamas2021@underline.io 

Mingyu Guo

5

4

SHORT BIO

Presentations

Limited Query Graph Connectivity Test | VIDEO

Worst-Case VCG Redistribution Mechanism Design Based on the Lottery Ticket Hypothesis | VIDEO

Scalable Edge Blocking Algorithms for Defending Active Directory Style Attack Graphs

Practical Fixed-Parameter Algorithms for Defending Active Directory Style Attack Graphs

Mechanism Design for Public Projects via Neural Networks

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES