论文标题
Max-Flow/min-CUT系统中安全游戏的概率边缘分解
Decomposition of Probability Marginals for Security Games in Max-Flow/Min-Cut Systems
论文作者
论文摘要
给定一个设置系统$（e，\ nathcal {p}）$，$ρ\ in [0，1]^e $和$π\ in [0,1]^{\ Mathcal {p}} $，我们的目标是为随机的$ s \ subsetee $ $ \ operation $ \ operate $ \ pr pr in In than of than of In In In In In In In。 \在e $和$ \ operatatorName {pr} [p \ cap s \ neq \ emptyset] \ geq qou_p $ for in \ mathcal {p} $中的所有$ p \。我们扩展了Dahan，Amin和Jaillet（MOR 2022）的结果，他们研究了这一问题，该问题是由有指示的无环图（DAG）中的安全游戏激励的。 我们专注于设置，其中$π$是仿射形式的$π_p= 1 - \ sum_ {e \ in p}μ_e$ for $μ\ in [0，1]^e $。存在所需分布的必要条件是$ \ sum_ {e \ in p}ρ_e\ geqπ_p$ in \ mathcal {p} $中的所有$ p \ geqπ_p$。我们表明，只有$ \ nathcal {p} $具有弱的max-flow/min-cut属性，就足够了。我们进一步提供了一种有效的组合算法，用于在特殊情况下计算相应的分布，其中$（e，\ mathcal {p}）$是一个抽象网络。结果，Dahan等人的安全游戏的平衡。可以在各种设置（包括任意挖掘物）中有效计算。 作为我们算法的子例程，我们提供了一种用于计算抽象网络中最短路径的组合算法，部分回答了麦考密克（Soda 1996）的一个开放问题。我们进一步表明，Dahan等人提出的保护法。对于需求，$π$ in DAGS可以减少到上述仿射要求的设置。
Given a set system $(E, \mathcal{P})$ with $ρ\in [0, 1]^E$ and $π\in [0,1]^{ \mathcal{P}}$, our goal is to find a probability distribution for a random set $S \subseteq E$ such that $\operatorname{Pr}[e \in S] = ρ_e$ for all $e \in E$ and $\operatorname{Pr}[P \cap S \neq \emptyset] \geq π_P$ for all $P \in \mathcal{P}$. We extend the results of Dahan, Amin, and Jaillet (MOR 2022) who studied this problem motivated by a security game in a directed acyclic graph (DAG). We focus on the setting where $π$ is of the affine form $π_P = 1 - \sum_{e \in P} μ_e$ for $μ\in [0, 1]^E$. A necessary condition for the existence of the desired distribution is that $\sum_{e \in P} ρ_e \geq π_P$ for all $P \in \mathcal{P}$. We show that this condition is sufficient if and only if $\mathcal{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, \mathcal{P})$ is an abstract network. As a consequence, equilibria for the security game by Dahan et al. 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 (SODA 1996). We further show that a conservation law proposed by Dahan et al. for the requirement vector $π$ in DAGs can be reduced to the setting of affine requirements described above.
