May, 2022

随机排序法：惟一无二的无欺诈、比例公平的随机设施选址机制

PDF
TL;DR我们提出了一种叫做 “强比例” 的概念，可以用来解决设施选址问题。我们证明了一个称为随机排名机制的方法，可以在期望上满足强比例，但是没有确定性的策略证明机制可以满足该性质。最后，我们证明了在强比例的基础上，即使弱化了普遍的真实性，通过减少策略真实性可以达到更强的后验公平保证。
proportionalitystrong proportionalityrandom rankmechanismfacility location problem
发现论文，激发创造
  • 讨厌设施位置中的比例公平

    本文讨论了令人反感的设施位置问题，并提出了基于距离的比例公平概念层次结构。我们在确定性和随机机制方面考虑了这些公平公理，并计算出比例公正的定价的紧密界限。

    Jan, 2023

  • 关于确定性机制在设施选址博弈中的威力

    考虑 K-Facility Location games 中的确定性策略对象机制，证明了确定性策略对象机制最佳逼近率为 n-2，并研究了在不同情况下的适用特点，如线性空间情况下存在唯一的独裁者机制，而简单情况下的策略不可能实现有界逼近率。

    Jul, 2012

  • 候选位置设施选址博弈机制设计

    机制设计，通过策略证明机制来解决设施选址游戏，最小化代理的总成本和最大成本，并针对单设施问题和两设施问题分别证明了逼近度的下界和逼近算法。

    Oct, 2020

  • 公平分配的机制设计

    研究公平分配问题，提出真实机制设计方案，为每个代理人提供一定比例的比例公正估价，同时证明对于加性线性估价，没有真实机制可以保证超过 0.5 比例的比例公正估价。

    Dec, 2012

  • 聚类中的比例公平性：社会选择视角

    我们研究了陈等人的比例聚类问题，并将其与计算社会选择中的多胜者投票领域相关联。我们展示了任何满足 Brill 和 Peters 的弱比例概念的聚类同时获得陈等人比例公平概念、个体公平和 “核心” 的最佳已知拟合度。事实上，我们证明了任何对比例公平的近似也是对个体公平的近似，反之亦然。最后，我们还研究了比例代表性更强的概念，在这些概念中，偏差不仅发生在单个候选中心，还发生在多个候选中心，并且展示了 Brill 和 Peters 的更强比例概念对这些更严格的保证的拟合度。

    Oct, 2023

  • 具有缩放效应的设施选址博弈

    我们对传统的设施位置问题进行了变体研究，研究了代理人的个体成本函数与设施到代理人的距离乘以某一由设施位置决定的缩放因子的乘积；我们探讨了总成本和最大成本的最优解计算，以及在近似机制设计中代理人偏好不再是单峰时的条件并寻找了满足这些条件的缩放函数对应的策略稳定和匿名机制可达到的总成本和最大成本的近似比例。

    Feb, 2024

  • 设施位置机制设计的 MAC 建议

    基于预测的机制设计研究设施位置问题中的鲁棒性及其影响

    Mar, 2024

  • 联邦学习中的比例公平性

    本文介绍并研究了联邦学习中的公平性问题，提出了一种新的公平性概念 —— 比例公平性，并通过 Bargaining Games 建立联系，进而提出了一种简单易实现的算法 PropFair，用于在联邦学习中寻找比例公平的解，该算法可以在视觉和语言数据集上进行广泛的实验证明，平衡了所有客户端和最差的 10% 客户端的平均性能。

    Feb, 2022

  • 公平混合：二分偏好的情况

    讨论了三个优秀的投票规则，其中条件功利规则是一个策略性稳健且容易计算的规则，其最坏和平均效率在代理人数量较小时都是低的，而效率最高的 Nash Max Product 规则虽然可以实现任何联盟的最强福利保障，但不符合排斥策略性稳健性，而有效的平等主义规则保护个体代理人但不保护联盟。

    Dec, 2017

  • 比例公平聚类

    本论文在度量空间中探讨了公平机器学习领域中比例质心聚类问题，定义了公平性并提出了计算、优化和审计聚类方案的算法，分析了比例方案与 K-Means 指标之间的权衡关系。

    May, 2019