关于安全博弈的研究近年来广受重视，许多基于安全博弈论的系统已在现实世界中得到了成功应用。在该研究的理论框架中，博弈双方为安保部门和不法分子。其中安保部门首先确定一种策略，并根据该策略执行安保任务。不法分子可通过观测等方式完全知晓安保部门的策略，并根据该策略采取对自己最有利的行动。虽然第一代安全博弈研究成功的对于多种安全问题进行了基于斯塔克伯格博弈的建模，并提出了高效的算法进行相关模型的求解，但其存在三项局限，制约了该研究在更广泛领域中的应用。第一，大部分第一代安全博弈研究都假设可能被攻击的目标，也即需要被保护的目标，其价值是相互独立的，且不法分子最终只能攻击一个目标。这个假设在保护选举进行等领域并不成立。第二，此前研究大都假设目标的重要程度是固定不变的。这个假设在重大赛事安保、城市安保等领域不能成立。第三，第一代研究通常认为博弈参与方仅需选择目标进行保护或攻击，而不考虑他们如何到达这些目标，也不考虑安保部门可在不法分子到达目标的路途中对其进行拦截。该假设使得在研究海洋保护区巡逻等基于图的安全博弈时不能计算出最优的安保策略。针对这三项局限，本文研究了目标非独立、攻击目标不唯一的安全博弈，动态收益安全博弈以及图安全博弈，对每种博弈下的代表性问题进行建模和均衡求解算法设计。本文的主要创新点如下。　　1.本文基于保障选举进行的实际问题研究了目标价值不独立、攻击目标不唯一的安全博弈。本文考虑了选举中可能面临的破坏性攻击（不法分子的目标是阻止最初的赢家获胜）和建设性攻击（不法分子的目标是使得某个原本不能获胜的候选人获胜）两种攻击方式。本文首先分别分析了这两种攻击方式的复杂度和抵制这两种攻击以保障选举进行的复杂度。随后，本文利用斯塔克伯格博弈模型，对保障选举进行，抵制两种攻击的问题进行建模。针对抵制破坏性攻击，本文提出了一种线性规划算法，求解抵制攻击，保护选民的最优策略。又提出了一种基于Double Oracle框架的更高效的算法，在大多数情况下能够在避免遍历策略空间的情况下即求得最优解。针对抵制建设性攻击，本文提出了一种混合整数线性规划算法以求解抵制攻击的最优策略。本文还提出了一种启发式算法，能够在一部分情况下在多项式时间内求出最优策略。此外，本文还提出了一种近似算法以求解一般问题中“足够好”的策略，该算法能够在绝大多数情况下返回最优解。本文在真实数据集和模拟数据集上进行试验，验证了模型和算法的有效性。　　2.本文研究了动态收益安全博弈，考虑了重大赛事安保与城市安保两个场景，以分别探索动态收益安全博弈中纯策略均衡和混合策略均衡的计算。在两种场景下本文均考虑了博弈参与双方具有连续策略空间的情形。针对重大赛事安保问题，本文首先关注了资源的转移时间远小于赛事的进行时间的情形，并提出算法SCOUT-A来求解此情形下安保方的最优策略。然后，本文又研究了更具一般性的资源转移时间不可忽略的情况。针对这种情形，本文从离散时间假设着手，提出算法SCOUT-D来求解在离散时间假设下的安保方最优策略，又在此基础上设计出算法SCOUT-C，以求解连续策略空间，资源转移时间不可忽略的情形下的安保方最优策略。针对城市安保问题，本文首先设计算法COCO来求解安保资源转移时间可忽略情形下的紧凑表示的最优混合策略。基于COCO计算出的紧凑表示的最优混合策略，本文提出一种采样方法，以确定每次安保任务的具体执行情况。对于混合策略均衡模型下资源转移时间不能忽略的情况，本文提出算法ADEN，其能够在多项式时间内求出∈近似解。实验证明COCO和ADEN均取得了比现存算法更好的效果。　　3.本文基于海洋保护区巡逻问题，研究基于图的安全博弈。图中的每个节点表示一个时间和地点的二元组，图中的任一条路线均为安保部门或不法分子的可行策略。本文利用网络流的方式来紧凑的表示安保部门的混合策略，并提出一种线性规划算法CLP求解安保部门的最优巡航策略。此外，本文还将网络流思想和Double Oracle框架相结合，提出CDOG算法，高效求解最优策略。实验结果表明CLP和CDOG均取得了明显好于现存算法的效果，CDOG的可扩展性也明显好于已知的最好算法。　　综上所述，本文研究了三种复杂收益安全博弈以及这三种博弈下的四个代表性问题。针对每一个问题，本文均采用了新的建模方式，以解决此前研究工作中模型的局限性。本文提出了高效的算法以求解各模型中的最优安保策略。实验证明本文所提出的模型和算法取得了比现有研究成果更好的效果。