May, 2016

关于最大化最小份额分配的诚实机制

PDF
TL;DR本文研究了一种公平分配问题，即计算最大最小份额分配。通过机制设计方法，提出了三种关于机制试图引导玩家了解其偏好的信息模型，并对每个模型进行积极和消极（不可能性）结果的阐述，最后特别关注了两位玩家的情况，提出了挑战性的问题。
fair division problemindivisible itemsmaximin share allocationsmechanism design approachtruthful mechanisms
发现论文，激发创造
  • 计算最大最小份额分配的近似算法

    本文研究了计算最大最小份额保证的问题，提出了新的公平性概念并使用近似算法解决分配问题，证明了在随机生成的实例中存在最大最小份额分配的概率高，同时对两种特殊情况进行了正面的研究和改进。

    Mar, 2015

  • Maximin 公平分配的近似算法

    研究在 n 个代理人之间公平地分配不可分割物品的问题。针对加法和次模值问题，提出了最大化份额的概念和算法，同时利用多线性扩展分析回路算法的性能，得到了存在 0.21 近似的最大化份额分配结果。

    Mar, 2017

  • 最大份额最小化的改进近似算法

    该研究研究了在多个代理设置下使用最大最小份额分配公平分配资源的问题，并提出了一种新方法来简化算法并改进其逼近性能。

    Feb, 2019

  • 二元估值的公平诚实机制

    设计了一种分配机制，基于私有偏好，旨在通过将不可分割物品分配给玩家来实现高效和公平；使用具有二分边缘概率的估值，并且它是公证的，它生成的分配满足许多所需的公平性质。

    Feb, 2020

  • 不可分割物品的公平分配：改进与概括

    本文研究不可分割物品的公平分配问题，使用最小最大份额范例作为公平性标准，并提出了一种在聚类代理人的集合上使用匹配配分和貪婪演算法获得 3/4 最小最大份额得分的方法，同时将该方法推广到子模，分数次折价及次折价情况，并提出了相应的近似比较与上界。

    Apr, 2017

  • 群体最大最小公平分配不可分物品

    本文研究了在 n 个代理人中公平分配不可分性商品的问题，提出了比最小限度份额更强的公平性概念：团体最小限度份额保证。我们证明，在特定情况下，总是存在 GMMS 分配，在加性估值模型下存在近似 GMMS 分配，并提出了一个多项式时间算法来找到这样的分配。此外，我们表明 GMMS 可能导致近似无嫉妒的分配。

    Nov, 2017

  • 保证最小最大份额：一些代理被落下

    本论文提出了一种以人口为基础的近似公平性概念，重点研究了最大最小份额的分配，并证明了在 9 个代理人以内，可以使用多项式时间算法来分配最大最小份额的 $ rac {2}{3} $，从而提高了现有的保证值，并在合成数据上进行了实证实验。

    May, 2021

  • 公平分配：可行性，主导和激励

    研究了无货币转移的情况下，将一组不可分割物品公平地分配给 n 个权利平等的代理商，其中每个代理商都有一个来自某个估值函数类的估值。研究表明，适当的 “份额” 是可以实现的，需要将其定义为可行实现的问题，并确定计算可行最大收益份额的算法。

    May, 2022

  • 公平分配的机制设计

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

    Dec, 2012

  • 具有部分信息的公正而有效的资源分配

    本文研究了将不可拆分物品分配给具有加法偏好的代理人的基本问题。我们考虑 eliciting 每个代理人仅排名她最喜欢的 $k$ 个物品，而不是她的完整基数估值。我们表征了实现嫉妒 - 自由度高达一个良好且近似最大值共享保证的 $k$ 值。我们还分析了由于缺乏完整信息而产生的社会福利的乘法损失，无论是否满足公平要求。

    May, 2021