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

有限排序的应用：公平划分、选举系统和图模型

• 批准号: RGPIN-2014-05023
• 负责人: Kilgour, DMarc
• 金额: $ 1.68万
• 依托单位: Wilfrid Laurier University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=655535
• 关键词: Applications; Finite; Orderings; Fair; Division

This proposal highlights three sets of open questions, all reflecting the interactions of finite orderings.**Discrete Fair Division*When 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 Systems*The 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 Model*This 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.

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