Decomposition of probability marginals for security games in max-flow/min-cut systems

• 成果类型: Article
• 署名作者: Matuschke, Jannik
• 署名单位: KU Leuven
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-024-02144-6
• 发表日期: 2025
• 页码: 611-640
• 关键词: polynomial algorithm; network flow

摘要

Given a set system (E,P) with rho is an element of[0,1](E) and pi is an element of[0,1](P), our goal is to find a probability distribution for a random set S subset of E such that Pr[e is an element of S ]= rho e for all e is an element of E and Pr [P boolean AND S not equal empty set] >= pi P for all P is an element of P. We extend the results of Dahan, Amin, and Jaillet [6] who studied this problem motivated by a security game in a directed acyclic graph (DAG). We focus on the setting where pi is of the affine form pi P = 1 - Sigma(e is an element of P)mu(e) for mu is an element of[0,1](E). A necessary condition for the existence of the desired distribution is that Sigma(e is an element of P) rho e >= pi P for all P is an element of P. We show that this condition is sufficient if and only if P has the weak max-flow/min-cut property. We further provide an efficient combinatorial algorithm for computing the corresponding distribution in the special case where (E,P) is an abstract network. As a consequence, equilibria for the security game in [6] can be efficiently computed in a wide variety of settings (including arbitrary digraphs). As a subroutine of our algorithm, we provide a combinatorial algorithm for computing shortest paths in abstract networks, partially answering an open question by McCormick [20]. We further show that a conservation law proposed in [6] for the requirement vector pi in DAGs can be reduced to the setting of affine requirements described above.