Fair, Manipulation-Robust, and Transparent Sortition

📄 arXiv: 2406.15009v2 📥 PDF

作者: Carmel Baharav, Bailey Flanigan

分类: cs.AI

发布日期: 2024-06-21 (更新: 2024-06-26)

💡 一句话要点

提出Goldilocks目标函数，实现公平、抗操纵和透明的政治代表随机抽选。

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 随机抽选 公平性 抗操纵性 透明性 目标函数 公民大会

📋 核心要点

  1. 现有Minimax和Leximin目标函数在政治代表随机抽选算法中存在公平性和抗操纵性的trade-off。
  2. 提出Goldilocks目标函数，通过限制选择概率的上下界，同时优化公平性和抗操纵性。
  3. 实验表明，Goldilocks在真实数据中能同时实现接近最优的最小和最大选择概率，并具备透明性。

📝 摘要（中文）

本文针对政治代表随机抽选（sortition）算法展开研究，旨在解决公民大会等审议过程中参与者选择的公平性问题。现有算法致力于最大程度地保证志愿者的选择机会均等，但以往研究的Minimax和Leximin目标函数存在缺陷：Minimax抗操纵性强但公平性差，Leximin公平性好但易被操纵。为此，本文提出一种新的目标函数Goldilocks，旨在同时实现公平和抗操纵性，确保志愿者获得的选择机会既不太少也不太多。理论分析表明，Goldilocks在给定实例中能够恢复最佳可用解决方案。此外，本文还将Goldilocks的输出进行转换，以实现第三个目标：透明性。在真实数据上的实验分析表明，Goldilocks在大多数实际案例中能够同时实现接近实例最优的最小和最大选择概率。

🔬 方法详解

问题定义：论文旨在解决政治代表随机抽选（sortition）中，如何选择代表才能同时保证公平性、抗操纵性和透明性的问题。现有方法，如Minimax和Leximin，在公平性和抗操纵性之间存在trade-off。Minimax虽然抗操纵性强，但可能导致极度不公平的结果；Leximin虽然保证了公平性，但容易受到操纵，使得某些群体可以通过策略性地改变其参与意愿来影响最终的选择结果。

核心思路：论文的核心思路是提出一种新的目标函数Goldilocks，该函数的目标是确保每个志愿者被选中的概率既不太高也不太低，从而在公平性和抗操纵性之间取得平衡。这种设计的直觉是，如果每个人的机会都控制在一个合理的范围内，那么极端不公平的情况就会减少，同时操纵的动机也会降低。

技术框架：论文的技术框架主要包括以下几个部分：1) 定义了Goldilocks目标函数，该函数基于对选择概率的上下界约束；2) 提出了优化Goldilocks目标函数的算法；3) 从理论上分析了Goldilocks在公平性和抗操纵性方面的性能；4) 通过实验验证了Goldilocks在真实数据上的有效性。此外，论文还考虑了如何将Goldilocks的输出进行转换，以实现透明性。

关键创新：论文最重要的技术创新点在于提出了Goldilocks目标函数，它与现有方法的本质区别在于，它不是简单地最小化最大概率（Minimax）或最大化最小概率（Leximin），而是试图找到一个概率分布，使得所有个体的选择概率都落在一个可接受的范围内。这种方法能够更好地平衡公平性和抗操纵性，并且更容易实现透明性。

关键设计：Goldilocks目标函数的关键设计在于如何确定选择概率的上下界。论文中并没有明确给出如何确定这些上下界的具体方法，这可能需要根据具体的应用场景和数据进行调整。此外，论文还考虑了如何将Goldilocks的输出进行转换，以实现透明性，这可能涉及到一些后处理步骤，例如对选择概率进行排序或分组。

📊 实验亮点

实验结果表明，Goldilocks目标函数在真实数据集上表现出色，能够在大多数情况下同时实现接近实例最优的最小和最大选择概率。这意味着Goldilocks在实际应用中能够有效地平衡公平性和抗操纵性，并且具有很强的实用价值。此外，该方法还能够实现透明性，使得抽选过程更加公开和可信。

🎯 应用场景

该研究成果可应用于公民大会、陪审团遴选、委员会成员选择等需要公平、公正和透明的随机抽选场景。通过使用Goldilocks目标函数，可以提高抽选过程的公平性和抗操纵性，增强公众对决策过程的信任度，并促进更具代表性和包容性的决策结果。

📄 摘要（原文）

Sortition, the random selection of political representatives, is increasingly being used around the world to choose participants of deliberative processes like Citizens' Assemblies. Motivated by sortition's practical importance, there has been a recent flurry of research on sortition algorithms, whose task it is to select a panel from among a pool of volunteers. This panel must satisfy quotas enforcing representation of key population subgroups. Past work has contributed an algorithmic approach for fulfilling this task while ensuring that volunteers' chances of selection are maximally equal, as measured by any convex equality objective. The question, then, is: which equality objective is the right one? Past work has mainly studied the objectives Minimax and Leximin, which respectively minimize the maximum and maximize the minimum chance of selection given to any volunteer. Recent work showed that both of these objectives have key weaknesses: Minimax is highly robust to manipulation but is arbitrarily unfair; oppositely, Leximin is highly fair but arbitrarily manipulable. In light of this gap, we propose a new equality objective, Goldilocks, that aims to achieve these ideals simultaneously by ensuring that no volunteer receives too little or too much chance of selection. We theoretically bound the extent to which Goldilocks achieves these ideals, finding that in an important sense, Goldilocks recovers among the best available solutions in a given instance. We then extend our bounds to the case where the output of Goldilocks is transformed to achieve a third goal, Transparency. Our empirical analysis of Goldilocks in real data is even more promising: we find that this objective achieves nearly instance-optimal minimum and maximum selection probabilities simultaneously in most real instances -- an outcome not even guaranteed to be possible for any algorithm.