在线蛋糕切割(已发布版本)
研究的是蛋糕切割问题的询问复杂度,同时给出了计算近似无嫉妒、完美和公平分配的下限和上限,其中下限在计算 n=3 个玩家之间的连通无嫉妒分配以及 n=2 个玩家之间的完美和公平分配方面非常紧密,还阐明了移动刀具程序的形式化方法,并证明了这个大的子类可以在 Robertson-Webb 的询问模型中以任意小的误差高效地模拟。
May, 2017
公平蛋糕切分是一种研究如何公平地将资源划分给多个参与者的数学子领域。本研究阐述了公平蛋糕切分与监督多标签分类之间的联系,以及其在机器学习中解决公平性问题的潜力。研究发现,为了满足公平性要求,有时为了最优性,会故意犯错,并在同一社群中偏爱不值得的个体而拒绝给予值得的个体正面标签,这被称为 “挑大梁” 或 “彰显不公平”。
Jun, 2024
本篇研究论文调查了一个新兴的有前途的研究领域,这个领域考虑到许多实际的公平分配问题的在线性质。文章确定了种类繁多的这种在线公平分配问题,并讨论了适用于此在线设置的新机制和规范属性。这样的公平分配问题的在线性质提供了机会和挑战,如开发新的在线机制的可能性以及应对不确定未来的困难。
Nov, 2019
我们提出了一种离散和有界的无嫉妒协议,可为任何数量的代理找到无嫉妒分配。即使我们没有完全运行我们的协议,我们也可以在至多 $n^3 {(n^2)}^n$ 个查询中找到一个部分分配,以实现比例分配和无嫉妒性。最后,我们还表明,可以在最多 $n^3 {(n^2)}^n$ 个查询中计算一个无嫉妒的部分分配,使得每个代理人都获得至少糕点总价值的 $1 / (3n)$ 的连接块。
Apr, 2016
多次公平分割研究中,考虑了两个玩家 —— 爱丽丝和鲍勃 —— 对蛋糕的私人评估。通过使用类似二分搜索的策略,爱丽丝可以逐渐准确地判断鲍勃的喜好,从而在资源分配中获得了不成比例的份额。通过与 Blackwell 可达性的连接,证明了在每一轮的游戏中,通过保证对手的平均效用近似为 1/2,并保证自己的平均效用至少近似为 1/2,在极限情况下玩家可以实现公平的效用分配。最后,通过分析称为虚构博弈的自然动态,证明了虚构博弈以 O (1/√T) 的速率收敛到公平的效用分配。
Feb, 2024