Apr, 2016

一种离散且有界的无嫉妒蛋糕切分协议，适用于任意数量的代理

PDF
TL;DR我们提出了一种离散和有界的无嫉妒协议，可为任何数量的代理找到无嫉妒分配。即使我们没有完全运行我们的协议，我们也可以在至多 $n^3 {(n^2)}^n$ 个查询中找到一个部分分配，以实现比例分配和无嫉妒性。最后，我们还表明，可以在最多 $n^3 {(n^2)}^n$ 个查询中计算一个无嫉妒的部分分配，使得每个代理人都获得至少糕点总价值的 $1 / (3n)$ 的连接块。
cake cutting problemenvy-free allocationdiscrete protocolqueriesproportional allocation
发现论文，激发创造
  • 四人离散有界无嫉妒蛋糕切割协议

    研究了蛋糕切分问题，提出了离散且有界的不嫉妒协议，以实现基于最少询问数的公平分配问题。

    Aug, 2015

  • 四个代理人的改进无嫉妒蛋糕切割协议

    本文研究了四个代理人的经典切蛋糕问题，提出了一种更简单并且运算复杂度比之前的算法低 3.4 倍的改进算法。

    Jul, 2018

  • 蛋糕切割的查询复杂度

    研究的是蛋糕切割问题的询问复杂度，同时给出了计算近似无嫉妒、完美和公平分配的下限和上限，其中下限在计算 n=3 个玩家之间的连通无嫉妒分配以及 n=2 个玩家之间的完美和公平分配方面非常紧密，还阐明了移动刀具程序的形式化方法，并证明了这个大的子类可以在 Robertson-Webb 的询问模型中以任意小的误差高效地模拟。

    May, 2017

  • 网络公平的蛋糕切分

    本文提出了一种在图形结构中实现公平分配的方法，其中包含了嫉妒自由和比例两个公平概念，并实现了一些在树和后代图中的算法。

    Jul, 2017

  • 公平分配

    研究分配问题，引入社交网络模型，通过局部比例和局部嫉妒性的概念，使用单人切割模型确定图形结构和嫉妒性代价下的最大效用分配。

    Nov, 2016

  • 无嫉妒图切割的复杂性

    这篇研究论文主要研究公平地分配一组异质可分资源给具有不同偏好的个体的问题，关注的是资源对应于一张连接图的边缘，每个个体必须被分配一块连通的图形，所考虑的公平概念是经典的无嫉妒性。该问题是 NP 完全的，我们分析了该问题相对于两个自然复杂度度量的复杂性：个体数量和图中边缘的数量。虽然即使对于只有两名个体的实例问题仍然是 NP 困难的，但我们根据图的结构性质给出了当个体数量是常数时该问题复杂性的两分法特征。对于后一种情况，我们设计了一个多项式时间算法，当图形具有常数数量的边时。

    Dec, 2023

  • 多层蛋糕的比例公平分割

    研究多层蛋糕切割问题，使用个体和多数代理的切换点思想证明了在连续性和可行性约束条件下，存在比例多分配给任意数量代理和任何数量喜好类型的情况。

    Aug, 2022

  • 分配家务：妒忌和真相

    研究了具有策略性代理的可分割坏资源的公平分配问题，证明了在一定约束下，没有确定性的、讲真话的、无妒忌的机制存在。

    Jan, 2023

  • 多件公平分割

    本文将枚举的方式应用于一些常见的分配问题，并使用拓扑学方法和 Furedi，Lovasz 和 Gallai 的超图定理进行了证明。

    Oct, 2017

  • 在线蛋糕切割（已发布版本）

    本文提出了一种在线蛋糕切分问题的解决方法，探讨了公平分配方案，包括在线比例公平性和不嫉妒性等公平性质，研究了代理之间勾结的影响，通过理论和经验考察竞争比率评估了各种在线蛋糕切分方法，结果表明在线 “切 - 选” 法能够更好地抵御代理的勾结并且效果更优秀。

    Jun, 2011