Applications of Finite Orderings: Fair Division, Electoral Systems, and the Graph Model

这个建议强调了三组开放的问题，都反映了有限排序的相互作用。离散公平分配具有不同偏好的个体何时以及如何共同“公平”分配某些东西？这个古老而又容易理解的数学问题有许多潜在的应用，例如谈判和预算。连续分配问题（“蛋糕分割”）已经得到了很好的研究，但对于分配一组不可分割的物体（如硬糖或绘画）却知之甚少。通常的目标是不嫉妒（没有人会严格喜欢别人的那部分）和帕累托最优（任何其他分配对某人来说都不那么可取）。人工智能算法最近被提出，并与一个定理联系在一起，该定理精确地规定了何时存在一个完整的、帕累托最优的、无嫉妒的两人分配。但是这个定理依赖于嫉妒自由的特定定义，并没有指出当人工智能崩溃时该怎么做。一个想法是通过将人工智能与非同步算法（如削弱）相结合来扩展人工智能。超越两个人是另一个重要的目标。计算研究可以揭示不真诚（不诚实）行为的脆弱性。多赢家选举制度最近选举制度的激增可能是由于互联网，新的选票和计数规则已经被发明和采用。这个项目的一个主题是多赢家选举，在很大程度上是一个“新边疆”。对于这样的选举，赞成投票虽然是为单赢家选举设计的，但却是一个自然的程序；选民被要求为他或她赞成的每一个候选人投票。在《赞成投票手册》中有一篇关于多赢家选举的文章，将提前知道获胜者人数的选举与通过投票决定获胜者人数的选举区分开来。后者的例子包括名人堂和候选名单选举。多赢家批准投票程序的性质，如下两名规则，还没有得到很好的理解，“最优”系统是否存在也是一个悬而未决的问题。另一个研究方向超越了赞成投票，转向了赞成-反对投票，即选民支持、反对或弃权每位候选人。手册文章对该扩展产生了相当大的需求，可以在实际数据集上进行测试。这种对战略冲突进行建模和分析的系统已被应用于环境、政治、经济和军事冲突。它的计算机实现（测试版）被广泛用于理解具有多维含义的交互决策。图模型方法简单而灵活，但又足够细致，可以洞察与许多独立决策者（dm）的冲突。模型总是处于有限多个状态中的一个；dm具有不同的能力和偏好，控制状态的变化。对结果的自然预测是一种平衡，或一种对所有dm都稳定的状态。图模型不是游戏，因为混合策略无法评估，因为偏好是按顺序给出的，但尽管它很简单，但它已被证明非常有用。开发图模型方法的一个计划是解决一个相反的问题：是否有可能填补缺失的偏好信息，从而创建理想的均衡？这个答案将引导“第三方”干预者，比如那些在幼发拉底河流域多次避免战争的国家。第二个项目是探索图模型的结构，其中公共DM与只关心其局部结果的局部DM存在冲突。例如，中国政府在南水北调（长江到黄河）问题上有几个地方冲突。

This proposal highlights three sets of open questions, all reflecting the interactions of finite orderings.Discrete Fair DivisionWhen and how can individuals with different preferences can jointly allocate something “fairly”? This venerable yet easily understood mathematical problem has many potential applications, for example to negotiation and budgeting.The continuous allocation problem (“cake division”) has been well researched, but relatively little is known about allocating a set of indivisible objects, such as hard candies or paintings. The usual objectives are envy-freeness (no-one strictly prefers someone else’s portion) and Pareto-optimality (any other allocation would be less preferable for someone). The AL algorithm was recently proposed and linked to a theorem specifying exactly when a complete, Pareto-optimal, envy-free two-person allocation exists. But this theorem depends on a particular definition of envy-freeness, and does not indicate what to do when AL breaks down. One idea is to extend AL by combining it with a non-simultaneous algorithm like Undercut. Extension beyond two persons is another important goal. Computational studies can reveal vulnerabilities to insincere (untruthful) behaviour.Multi-Winner Electoral SystemsThe recent proliferation of electoral systems is probably due to the internet, where new ballots and counting rules have been invented and adopted. One theme of this program is multi-winner elections, for the most part a “new frontier.” For such elections, approval voting, though designed for single-winner elections, is a natural procedure; the voter is asked to vote for every candidate he or she approves.An article on multi-winner elections in Handbook on Approval Voting distinguished elections in which the number of winners is known in advance from those in which the number of winners is determined from the ballots. Examples of the latter include Hall of Fame and short-listing elections. Properties of multi-winner procedures for approval ballots, such as the Next-Two Rule, are not well understood, and whether "optimal" systems exist is an open question. Another direction of research passes beyond approval ballots to yes-no ballots, in which voters support, oppose, or abstain on each candidate. The Handbook article generated considerable demand for this extension, which can be tested on real datasets.Graph ModelThis system for modelling and analyzing strategic conflicts has been applied to environmental, political, economic, and military conflicts. Its computer implementation (beta version) is widely used to understand interacting decisions with multidimensional implications.The graph model methodology is simple and flexible, yet nuanced enough to give insights into conflicts with many independent decision-makers (DMs). A model is always in one of finitely many states; DMs, who have different capabilities and preferences, control state changes. A natural prediction of outcome is an equilibrium, or a state that is stable for all DMs. A graph model is not a game, as mixed strategies cannot be evaluated since preferences are given as orderings but, despite its simplicity, it has proven surprisingly useful.One plan to develop the graph model methodology is to address an inverse problem: Is it possible to fill in missing preference information so as to create a desired equilibrium? This answer would guide “third party” interveners, such as those who apparently averted war in the Euphrates basin several times. A second project is to explore the structure of graph models with a common DM in conflict with local DMs who care only about their local outcomes. For example, the government of China has several local conflicts over south-north (Yangtze to Yellow) water diversions.