Decomposition of probability marginals for security games in abstract networks

DOI10.1007/978-3-031-32726-1_22MaRDI QIDQ6086010zbMATH OpenOpenAlexFDO

Authors Jannik Matuschke

Publication date 9 November 2023

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2211.04922

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Games involving graphs (91A43)

Abstract: Given a set system $(E,mathcalP)$, let $piin[0,1{]}^{mathcalP}$ be a vector of requirement values on the sets and let $hoin[0,1{]}^E$ be a vector of probability marginals with $su{m}_{einP}h{o}_{e}geqp{i}_P$ for all $PinmathcalP$. We study the question under which conditions the marginals $ho$ can be decomposed into a probability distribution on the subsets of $E$ such that the resulting random set intersects each $PinmathcalP$ with probability at least $p{i}_P$. Extending a result by Dahan, Amin, and Jaillet (MOR 2022) motivated by a network security game in directed acyclic graphs, we show that such a distribution exists if $mathcalP$ is an abstract network and the requirements are of the form $p{i}_P=1-su{m}_{einP}m{u}_e$ for some $muin[0,1{]}^E$. Our proof yields an explicit description of a feasible distribution that can be computed efficiently. As a consequence, equilibria for the security game studied by Dahan et al. can be efficiently computed even when the underlying digraph contains cycles. As a subroutine of our algorithm, we provide a combinatorial algorithm for computing shortest paths in abstract networks, answering an open question by McCormick (SODA 1996). We further show that a conservation law proposed by Dahan et al. for requirement functions in partially ordered sets can be reduced to the setting of affine requirements described above.

Recommendations

• Probability Distributions on Partially Ordered Sets and Network Interdiction Games
• Security games on matroids
• A game on a distributed network.
• Faster algorithms for security games on matroids
• A network game with attackers and a defender

Cites work

• A generalization of max flow—min cut
• A note on two problems in connexion with graphs
• A Polynomial Algorithm for Weighted Abstract Flow
• Abstract flows over time: a first step towards solving dynamic packing problems
• Abstract network flow with intermediate storage for evacuation planning
• Fare evasion in transit networks
• scientific article; zbMATH DE number 871948 (Why is no real title available?)
• Integrated line planning and passenger routing: connectivity and transfers
• Maximal Flow Through a Network
• On the power of randomization in network interdiction
• Probability Distributions on Partially Ordered Sets and Network Interdiction Games
• Security and Game Theory
• Security games on matroids
• The complexity of computing a robust flow
• The Shortest Path Interdiction Problem with Randomized Interdiction Strategies: Complexity and Algorithms

Cited in

(4)

• Interdependent Security Games on Networks Under Behavioral Probability Weighting
• Probability Distributions on Partially Ordered Sets and Network Interdiction Games
• Decomposition of probability marginals for security games in max-flow/min-cut systems
• A linear time algorithm for linearizing quadratic and higher-order shortest path problems

This page was built for publication: Decomposition of probability marginals for security games in abstract networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6086010)