贪心算法求解纳什社会福利最大化问题
研究分配一组不可分割商品给一组代理商的公平和高效问题,当代理商对商品具有可加性评估时,存在一种同时满足 EF1 和 PO 的最大 Nash 社会福利目标的分配,并提出了一个类似于假多项式时间算法的方法用于寻找 EF1 和 PO。
Jul, 2017
研究在 n 个代理人之间公平地分配不可分割物品的问题。针对加法和次模值问题,提出了最大化份额的概念和算法,同时利用多线性扩展分析回路算法的性能,得到了存在 0.21 近似的最大化份额分配结果。
Mar, 2017
该研究针对在线情况下可分配商品的公平高效分配问题,提出了一种基于平均值的算法框架来最大化每个成员获得的价值。该框架可以用于范围各异的福利函数,通过特定的阈值,得到了统一的与个性化竞争保证,并实现了比现有算法更好的效果。
Sep, 2021
本文研究了计算最大最小份额保证的问题,提出了新的公平性概念并使用近似算法解决分配问题,证明了在随机生成的实例中存在最大最小份额分配的概率高,同时对两种特殊情况进行了正面的研究和改进。
Mar, 2015
研究在具有双值次模估值的代理人之间公平分配不可分割物品的问题,并提出了一种基于 Yankee Swap 机制的简单顺序算法框架,可用于计算多种解决方案概念,包括 leximin,max Nash welfare(MNW)和 $p$-mean welfare 最大化分配,当 $a$ 除以 $b$ 时;对于两个公认的特性 - 羡慕无阻和最大收益份额保证,我们进一步检查 leximin 和 MNW 分配。
Feb, 2023
研究为具有加法估值函数的代理分配不可分割货物的公平分配问题,并探索两个突出的公平性概念之间的关系:最大纳什福利(MNW)和任何物品的无嫉妒(EFX)。
Jan, 2020
本文研究了将不可拆分物品分配给具有加法偏好的代理人的基本问题。我们考虑 eliciting 每个代理人仅排名她最喜欢的 $k$ 个物品,而不是她的完整基数估值。我们表征了实现嫉妒 - 自由度高达一个良好且近似最大值共享保证的 $k$ 值。我们还分析了由于缺乏完整信息而产生的社会福利的乘法损失,无论是否满足公平要求。
May, 2021
本文研究了在私有约束下如何进行资源分配问题,可以从最大权重匹配、联合差分隐私和总代用品假设等方面来考虑。通过研究分析发现,这种问题在不同隐私条件下的解决方案存在明显差异,提出了适用于差分联合隐私的解决方案来保障社会福利最大化。
Nov, 2013
这篇论文研究了在加性估值条件下关于不可分配物品的公平分配问题,提出了使用 Leximin 算法和新算法来解决不同公平与经济效益的权衡问题,实现了 Pareto 最优分配。实验结果表明,近似无嫉妒、近似公平和 Pareto 最优可以同时实现。
May, 2019