摘要 Abstract
给定一个有限点集 \( S \subset \mathbb{R}^d \),将其视为选民在 \( d \)-维政治“频谱”上的位置,两名候选人(爱丽丝和鲍勃)分别选择 \(\mathbb{R}^d\) 中的一个点,试图争取尽可能多的选票。爱丽丝先选,鲍勃后选,然后每位选民根据欧几里得距离选择离自己更近的候选人投票。如果某位选民到两位候选人的距离相等,则该选民不投票。我们给出了在爱丽丝平局时获胜的情况下,使每位候选人获胜的点集 \( S \) 的几何特征刻画。此外,我们还证明了,若所有选民不位于同一条直线上,则当爱丽丝有获胜策略时,她的获胜点是唯一的。同时,我们提供了一种算法,能够在有限(事实上是多项式)时间内判断爱丽丝是否有获胜点,并确定该点的位置。
Given a finite set $S$ of points in $\mathbb{R}^d$, which we regard as the locations of voters on a $d$-dimensional political `spectrum', two candidates (Alice and Bob) select one point in $\mathbb{R}^d$ each, in an attempt to get as many votes as possible. Alice goes first and Bob goes second, and then each voter simply votes for the candidate closer to them in terms of Euclidean distance. If a voter's distance from the two candidates is the same, they vote for nobody. We give a geometric characterization of the sets $S$ for which each candidate wins, assuming that Alice wins if they get an equal number of votes. We also show that, if not all the voters lie on a single line, then, whenever Alice has a winning strategy, there is a unique winning point for her. We also provide an algorithm which decides whether Alice has a winning point, and determines the location of that point, both in finite (in fact polynomial) time.