英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料
在杯赛和循环赛中操纵比赛
Tyrel Russell1 and Toby Walsh2
1Cheriton School of Computer Science, University of Waterloo, Waterloo, Canada tcrussel@cs.uwaterloo.ca
2 NICTA and UNSW, Sydney, Australia
toby.walsh@nicta.com.au
摘要：在体育比赛中，球队可以通过例如投掷游戏等手段操纵比赛结果。我们证明了我们可以决定如何操纵循环赛和杯赛这两种在多项式时间内最受欢迎的体育赛事。此外，我们还证明了在多项式时间内也可以找到操纵结果所需的最小对策数。最后，我们展示了几种不同的标准杯赛的操纵保持多项式。
1引言
Gibbard-Satterthwait定理证明，在某些适度的假设下，投票系统总是可以操纵的。 Bartholdi，Tovey和Trick提出的一种可能的解释是，这种操纵从计算上讲是非常难找到的 [2]（但是请参阅[13]，以讨论是否不仅在最坏的情况下很难操纵）。与选举一样，体育比赛也可能被操纵。例如，一个团队联盟可能会有策略地抛出一些游戏，以确保某个期望的团队获胜或某个团队失败。我们在这里考虑计算这种操纵的计算复杂性。我们证明，对于几种常见的比赛类型，确定联盟何时可以操纵结果是多项式的。我们的结果调整了选举的操纵程序，能够使选民歪曲他们的偏好。我们考虑用两种最常用的方法来决定体育比赛，即杯赛和循环赛。这些分别对应于使用连续多数投票（也称为杯赛规则）和科普兰计分法进行的选举。
操纵体育比赛与操纵选举略有不同，因为在体育比赛中，选民也是候选人。竞赛图描述了对手之间所有公平竞赛的结果。因此，操纵比赛并不直接修改选票，而是直接修改竞赛图。由于没有贿赂或类似的机制，一个团队很难比它所能发挥的更好，所以我们考虑联盟中的团队只能进行游戏的操纵。相比之下，在选举中，操纵联盟的选民可能以他们选择的任何方式误报其偏好。Tang、Shoham和Lin [11]通过提供球员实力的真实报告的方式，解决了团体赛中这种类型的比赛操纵。他们的方法试图鼓励各队诚实地对他们的球员进行排名，这样，当球队在比赛时，一个队中最好的球员在另一队中发挥最好，第二个最好的球员在相对的第二个上发挥作用，依此类推。戴维斯杯网球赛就是这类比赛的一个例子。
Conitzer、Sandholm和Lang [3]给出了一种算法来确定联盟是否可以操纵杯赛规则。 我们修改了该算法，以直接操纵竞赛图，而不是投票。Bartholdi、Tovey和Trick [2]讨论了在二阶Copeland下对锦标赛的直接操纵，Copeland是一种类似于循环赛的规则，会出现二次平局。利用Kern和Paulusma [7]的工作，我们证明了在体育问题中，循环赛的操纵与获胜者的决胜的问题直接相关 Altman、Procaccia和Tenneholtz [1]构建了一个单调的、成对的、不可操纵的和非强制性的社会选择规则。循环赛和杯赛都是单调的，一个球队输掉一场比赛也没有什么好处。成对的不可操纵性意味着没有任何两支球队通过操纵比赛而变得更好。 我们的结果表明，循环赛和杯赛是成对的可操作的，并且可以在多项式时间内计算出操作。
我们修改了算法以计算所需的最少操作次数。对于杯赛，我们在Conitzer、Sandholm和Lang的算法中添加了动态编程 对于循环赛，我们修改了用于解决获胜者确定的流程网络，包括操纵权重，并计算出最小成本的可行流程。Vu、Altman和Shoham [12]使用了类似的方法来计算一个队赢得比赛的概率。Vu等人的 [12]提供了一些确定球队在种子期的比赛中获胜概率的结论。Hazon等人的 [6]表明，确定一支球队是否以给定的概率赢得杯赛是NP完全的。这类似于在随机重新播种的情况下确定一个可能的赢家，只是把比赛中的优势用概率标记。我们研究了确定性情况下重播操作的复杂性。最后，我们看看双重淘汰杯的复杂性。
2背景
在许多体育比赛中，比赛的最终获胜者是由一个称为杯的树状结构决定的。最常见的类型是单个淘汰赛杯，这是一种树状结构，其中根节点和内部节点代表比赛，叶子节点代表锦标赛中的球队。一个杯赛可以包括一场再见比赛，一个球队跳过一场比赛来重新平衡赛程的比赛。通常情况下，排名靠前的队伍会得到一场轮次赛，而排名靠后的队伍则不会，因此下一轮的队伍数量严格按照2的幂次计算。杯赛需要通过种子队来决定哪支队伍在每一轮比赛中对阵。一种播种方法是按等级播种。排播或重排最常见的方法是让最优秀的队和最差的队比赛，第二名的队和第二差的队比赛，以此类推。美国国家篮球协会就是使用这种方法进行种子排名的一个例子。另一种确定播种的方法是随机抽签。一个例子是欧洲冠军联赛，进入四分之一决赛的球队在剩下的比赛中随机配对。播种也可能更加复杂（例如，它可能基于团队所属的组或其他一些标准）。杯赛的另一种修改方式是固定杯和非固定杯。固定杯是在杯赛的开头有一个种子的比赛。例如，美国国家篮球协会和世界杯足球赛。非固定杯是指不仅在开始之前，而且在任何一轮之间都有可能进行播种的杯赛。国家冰球联盟和欧洲冠军联赛就是非固定杯的例子。
杯子不一定是单淘汰赛。设计双淘汰赛，这样一队可以输掉两场比赛而不是一场比赛。如果一支球队输了，他们将与其他同样输掉的球队进行比赛，直到他们再次输掉比赛或赢得最后一场比赛。这些比赛以两杯的形式组织，输家根据输掉第一场比赛的时间在不同的阶段进入第二杯。最后，循环赛是指每支球队与其他球队进行给定次数的比赛。在单循环赛中，每队与其他队比赛一次。另一种常见的变体是两队进行两轮循环赛，每队与其他每队比赛两次，通常是在主场和客场。
3操纵比赛
比赛是一个有向图G =（V，E），其中底层无向图是一个完整图。我们假设锦标赛可在本文的其余部分中使用。每条有向边（vi，vj）isin;E代表vi对vj的胜利。比赛中的球队数量| V | =m。我们将比赛的操纵定义为用边（vj，vi）替换图中的边（vi，vj）。这相当于操纵选票，但这里我们直接改变获胜者，而不仅仅是改变投票。请注意，就像在假定选举投票已知的选举操纵中一样，我们假设通过预言知道球队的相对实力，并且可以在比赛图中表示比赛的获胜者。如果候选vi是联盟的成员，我们仅允许对边（vi，vj）进行操纵，从而限制操作。这就限制了操纵者的行为，使他们只能把游戏扔到本可以赢的地方。这一限制是由于这样一个事实:表现差很简单，但表现好就难了。我们考虑两种不同类型的操纵。一种有建设性的操作是确保特定团队在比赛中获胜。破坏性操纵是确保特定团队输掉比赛。对于循环赛，我们将比赛的概念从简单的胜负计分模型推广到一个完整的图形，其中边（vi，vj）具有非负权重wij，表示vi在公平比赛中与vj比赛时所能获得的分数。在这种情况下，我们将操纵定义比赛中获得的分数与比赛真正给出的分数不同的结果。然而，操纵是受限制的，因此，操纵者没有获得更多的分数，被操纵的团队没有获得更少的分数。
在本节中，我们将自己限制在具有已知种子的固定杯中。我们也只看单循环赛，虽然结果概括到多循环赛。
3.1杯赛
对于杯赛，找出一个有建设性或破坏性的操纵是多项式的。我们的结果利用了[3]中的结果，该结果表明在O（m3n）时间可以找到使用杯赛规则对选举的操纵，其中m是候选人的数量，n是选民的数量。
定理1.确定杯赛是否可以通过对比赛的操纵构造性地操作，需要花费多项式时间。
证明：该证明是自下而上的版本，它是Conitzer、Sandholm和Lang（CSL）[3]给出的定理2的证明，但是用比赛的操纵代替了投票的操纵。基本的CSL算法是一种递归方法，它将树（不是叶）中的每个节点视为子选择（请参见算法CSL）。 Conitzer等人在[3]指出，一个团队赢得次选举，当且仅当他们必须赢得其中一个子选择，他们可以击败另一边的潜在赢家之一。从自底向上的角度理解这个算法可能更简单。注意，如果我们有两个叶子节点vi和vj，并且比赛中存在一个弧（vi，vj），那么vi将赢得比赛，并且在vi和vj之间的子选择成为潜在的赢家。现在假设vi是联盟的成员，所以他们有可能在比赛中用（vj，vi）代替（vi，vj），因此vj也是通过操纵获得亚选的潜在赢家。假设我们在比赛中进行了次选举，有两组潜在的获胜者A和B。如果B中存在一支可以击败的球队，或者如果A在B中存在一支球队，则A中的任何一支球队都是该次比赛的潜在获胜者。对B中的团队也是如此。因此，如果期望的获胜者是杯状树顶部节点上潜在获胜者的成员，则可以进行有建设性的操作。
原始算法着眼于O（m2）对对手，因为没有两支球队进行过次比较。 请注意，最初的分析对比较的数量提供了一个更宽松的O(m3)界限，但是可以通过Vu等人的观察来收紧这个界限。[12]。直接操纵比赛与Conitzer、Sandholm和Lang的方法之间的区别在于，确定一支球队是否可以击败另一支球队意味着要在直接操纵比赛的同时，将需要O（n）时间的n个选民的所有价值相加。
算法：CSL（vw，c，T，C）
input：团队vw，杯状树c，比赛图T和团队联盟C
output：如果vw可以通过操纵获胜，则返回true，否则返回false
winnerslarr;PossibleWinners（c，T，C）;
if vwisin;winners then
return true;
else
return false;
算法：PossibleWinners（c，T，C）
input：杯状树c，比赛图T和团队联盟C
output：通过联盟操纵比赛，返回杯状树的可能赢家集合
if leaf( c) then
return {c};
else
winnerslarr;{};
LeftWinnerslarr;PossibleWinners（left（c），T，C）;
RightWinnerslarr;PossibleWinners（right（c），T，C）;
forall viisin;LeftWinners do
if exist;vjisin;RightWinners 使得（vi，vj）isin;Eor;vjisin;C then
add(winners,vi);
forall vjisin;RightWinners do
if exist;viisin;LeftWinners 使得（vj，vi）isin;Eor;viisin;C then
add(winners,vj);
return winners ;
这可以在固定时间内完成.因此，在杯赛规则下建设性地操纵比赛只需要O(m2)时间。
我们观察到,使用比赛操纵对竞赛的破坏性操作是相似的，因为这仅仅需要通过操纵确定是否存在至少一个其他可能的比赛获胜者。
定理2.确定杯赛是否可以用比赛操纵进行破坏性操作需要花费多项式时间。
证明：我们只是确定我们是否可以建设性地操纵彼此的比赛而不是希望输掉的比赛。
3.2循环赛
对于循环赛，可以使用有限类评分模型在多项式时间内计算比赛的操纵次数。 我们定义一个计分模型是给出游戏可能结果的元组集合。科普兰记分有一个简单的赢-输({(0,1)，(1,0)})记分模型，赢的队得1分，输的队得0分。Bartholdi、Tovey和Trick[2]指出，对于国际象棋计分模型({(0,1)，(1,2,1,2)，(1,0)})，可以在多项式时间内确定构造性操作。 Faliszewski等人的 [4]表明，对于一系列计分模型，操纵科普兰投票是np完全的。
首先，我们讨论了决定哪些游戏需要被操纵以确保给定的团队vw赢得比赛的问题。显然，有些游戏是不受联盟影响的，并且已经被修复了。其他的游戏都是可操纵的。 联盟成员之间的游戏可以获得得分模型允许的任何可能得分。我们只允许操纵者赚取更少的积分，而非会员赚取更多的积分，从而限制针对非联盟会员的游戏。确定一个给定的团队是否可以成为赢家，类似于确定一个团队是否赢得了一个循环赛，当固定的游戏已经玩了，而可操纵的游戏还没有玩。联盟成员与非联盟成员之间的博弈结果限制要求博弈结果只在得分模型的一个子集内。利用这一观察，我们得到以下定理。
定理3.如果标准化评分模型的形式为S= {(i，n-i) | 0le; i le; n }和 np-完全形式，则判定循环竞赛是否存在构造性操作是多项式的。
证明：这个证明使用了判断一个队是否能赢得比赛的等价性，以及判断一组固定和可操作的对策是否存在构造性操作的等价性。注意，非联盟成员 vi 和联盟成员 vj 之间的博弈是不固定的，但是可以分配的分数是有限的。当得分模型为 S= {(i，n-i) | 0le; i le; n }，且博弈的初始结果为(ci，cj)时，可分配的剩余有效分数为(ci，cj)到(n，0)之间的有效分数。通过对这个新模型进行标准化，我们得到了一个非联盟成员默认获得ci分，并且博弈结果从以S={(i，n-i) | 0le; i le; n }为形式的模型{(0，cj) ，... ，(n-ci，0)}中得分的模型。Kern和Paulusma [7]证明，如果标准化得分模型是 S={(i，n-i) | 0le; i le; n }且是 np-完全的，则判定一个队是否能赢得比赛(即不被淘汰)
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[409480]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
