Feb, 2023

利用次模式价值将良好和更好的项目分配给代理

HTML
PDF
TL;DR研究在具有双值次模估值的代理人之间公平分配不可分割物品的问题，并提出了一种基于Yankee Swap机制的简单顺序算法框架，可用于计算多种解决方案概念，包括leximin，max Nash welfare（MNW）和$p$-mean welfare最大化分配，当$a$除以$b$时；对于两个公认的特性-羡慕无阻和最大收益份额保证，我们进一步检查leximin和MNW分配。
发现论文，激发创造
  • 具有顺序偏好的不可分配物品的公平分配

    研究针对代理人与物体之间的离散分配问题，使用分数或随机分配的随机支配关系系统地定义了不同的比例公正和不嫉妒的概念，提出了多个公正概念并设计了多项式时间算法，扩展到不平等权利的情况，并且提出了一些公正概念，其中最优比例和最优弱比例是可取的。

    Dec, 2013

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

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

    Nov, 2017

  • 基数限制下的公平分配

    本论文主要研究如何在给定的特定限制条件下，实现资源公平配置问题，提出了一种有效的算法来计算两个中心公平概念，即 EF1和MMS，在满足限制条件的状态下，特别地，证明了在所有代理具有相同加性估值的情况下，即使存在限制条件，仍然可以有效地计算出 EF1 分配。

    Apr, 2018

  • 使用少量查询合理分配多种货物

    研究对不可分割物品的公平分配的查询复杂度。 发现对于两个代理人和任意单调效用的情况，可以使用对数数量的查询计算满足envy-freeness最多一个good (EF1)的分配，并且这个logarithmic查询复杂性界限也适用于具有可加性效用的三个代理人，但是需要使用polylogarithmic界限来满足单增效用的情况。同时，证明即使只有两个代理人具有相同可加效用时，计算满足envy-freeness和EFX（envy-freeness up to any good）之一的分配需要线性数量的查询。

    Jul, 2018

  • 不可分配物品分配中的加权无嫉妒公平性

    本文介绍和分析适用于配有权重的代理商在不可分配的物品的分配中的公平概念。我们提出了两种权重嫉妒自由概念：强权重嫉妒自由和弱权重嫉妒自由。我们证明，满足强权重嫉妒自由和帕累托最优的分配总是存在且可以在伪多项式时间内计算。此外，我们还建立了一个轮换选择算法的泛化版本，可以在多项式时间内为任意数量的代理商产生具有强权重嫉妒自由的分配。最后，我们强调了权重公平分配比其无权重对应更为复杂。

    Sep, 2019

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

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

    May, 2021

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

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

    May, 2021

  • (几乎)嫉妒平衡、比例和高效的不可分混合信物分配

    研究如何公平高效地分配不可分割物品给不同的需求者，考虑到嫉妒与比例问题，尝试提出了 Pareto 最优的多项式时间算法，同时维护各种类型的good/bad需求和纯商品和混合商品状况下的各项情形。

    Feb, 2022

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

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

    May, 2022

  • 二元超模资源下的加权公平性概念

    本文探讨了如何在代理者之间分配不可分割的家务，使用二元超模成本函数，并基于权值的公平性原则设计了分配方案。

    Mar, 2023