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
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=588165
• 关键词: 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崩溃时该怎么做。一种想法是通过将AL与非同步算法相结合来扩展AL，例如底切算法。另一个重要的目标是扩大到两个人以上。计算研究可以揭示虚假(不诚实)行为的脆弱性。 多赢家选举制度 最近选举系统的激增可能是由于互联网，在互联网上发明并采用了新的选票和计票规则。该节目的一个主题是多赢家选举，在很大程度上是一种“新边疆”。对于这样的选举，虽然批准投票是为单一赢家选举而设计的，但这是一个自然的程序；选民被要求投票给他或她批准的每一位候选人。 《批准投票手册》中关于多赢家选举的一篇文章。在区别选举中，获胜者的数量是预先知道的，而获胜者的数量是根据选票确定的。后者的例子包括名人堂选举和入围选举。批准投票的多赢家程序的性质，如下两个规则，还没有得到很好的理解，是否存在“最佳”制度是一个悬而未决的问题。另一个研究方向从赞成票转向赞成票-反对票，即选民对每个候选人表示支持、反对或弃权。手册的文章产生了对此扩展的相当大的需求，可以在真实的数据集上进行测试。 图形模型 这一战略冲突建模和分析系统已应用于环境、政治、经济和军事冲突。它的计算机实现(测试版)被广泛用于理解具有多维影响的交互决策。 图表模型方法简单而灵活，但足够细微，足以洞察与许多独立决策者(DM)的冲突。模型始终处于有限多个状态之一；具有不同功能和首选项的DM控制状态更改。对结果的自然预测是一种均衡，或对所有DM来说都是稳定的状态。图表模型不是游戏，因为混合策略不能被评估，因为偏好是以排序的形式给出的，尽管它很简单，但事实证明它出人意料地有用。 开发图形模型方法的一个计划是解决一个逆问题：是否有可能填补缺失的偏好信息，从而创建所需的均衡？这一答案将指导“第三方”干预者，比如那些几次明显避免了幼发拉底河流域战争的人。第二个项目是探索具有公共DM的图模型的结构，这些图模型与只关心其本地结果的本地DM冲突。例如，中国政府在南水北调(长江调黄)问题上有几次地方冲突。