研究两党政策竞争中的稳定策略，证明存在性并提出高效求解算法。
Computing Pure-Strategy Nash Equilibria in a Two-Party Policy Competition: Existence and Algorithmic Approaches
- 将政策竞争建模为非合作博弈，用内积表示选民偏好与政策匹配度。
- 证明一维和多维情况下均存在纯策略纳什均衡，实验显示算法快速收敛。
- 提出网格搜索法可多项式时间求解ε近似解，适合关注政治模型与博弈算法的研究者。
我们将两党政策竞争建模为双人非合作博弈，推广了林等（2021）的工作。每方从欧氏空间的紧子集选择实值政策向量作为策略，选民对政策的效用由其偏好向量与政策的内积决定。为捕捉竞争不确定性，假设政策获胜概率随全体选民总效用单调递增，并通过仿射保序函数形式化。玩家收益为其支持者获得的期望效用。本文首先通过投票模拟验证保序性假设；其次在单维和多维情形下证明纯策略纳什均衡的存在性。尽管构造反例表明博弈不具单调性，但实验显示基于梯度的分布式算法通常快速收敛至近似均衡。最后，提出一种网格搜索算法，在输入规模和1/ε的多项式时间内找到ε-近似纳什均衡。
原文摘要 · Abstract (English)
We formulate two-party policy competition as a two-player non-cooperative game, generalizing Lin et al.'s work (2021). Each party selects a real-valued policy vector as its strategy from a compact subset of Euclidean space, and a voter's utility for a policy is given by the inner product with their preference vector. To capture the uncertainty in the competition, we assume that a policy's winning probability increases monotonically with its total utility across all voters, and we formalize this via an affine isotonic function. A player's payoff is defined as the expected utility received by its supporters. In this work, we first test and validate the isotonicity hypothesis through voting simulations. Next, we prove the existence of a pure-strategy Nash equilibrium (PSNE) in both one- and multi-dimensional settings. Although we construct a counterexample demonstrating the game's non-monotonicity, our experiments show that a decentralized gradient-based algorithm typically converges rapidly to an approximate PSNE. Finally, we present a grid-based search algorithm that finds an $ε$-approximate PSNE of the game in time polynomial in the input size and $1/ε$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。