Apr, 2022

超越最坏情况的调度机制

PDF
TL;DR该论文探讨了两种调度机制（K 和 P 机制）的性能，证明了 K 机制是优于 P 机制的，并在特定条件下给出了它们的平均近似比例收敛值。
schedulingmechanism designresource allocationtruthful mechanismapproximation ratio
发现论文，激发创造
  • 公平算法设计：公平高效的机器调度

    本论文探讨了自动决策算法引起的偏见问题，提出了一种通过合理使用个人数据来平衡公平和有效性之间矛盾的 Pareto 调度机制，以及带来的社会福利和个人利益之间的差异。

    Apr, 2022

  • 理解激励：机制设计转化为算法设计

    本文提供了一种从机制设计到算法设计的计算高效的黑盒约简方法，并且在虚拟福利和收益两个问题上进行了探讨，发现在单调子模拟拍卖场景下，这两个问题都无法在多项式时间内进行近似解决。

    May, 2013

  • 有承诺的在线真实调度

    研究在线机制在满足截止日期的前提下如何保证完成作业的价值最大化，通过使用 deadline slackness 的自然假设，我们构建了一个具有竞争力的高效调度机制，并且如果满足 commitment property 的条件，则用户可以提前得知作业的完成情况和必要的付款，从而更好地满足他们的严格截止日期需求。

    Jul, 2015

  • 无货币的诚实分配

    研究不使用支付的真实机制的设计，以解决广义分配问题（GAP）及其变体。引入私人估值的模型，并研究了几种 GAP 变体，开发了一个基于 LP 的通用技术，可以将设计真实机制的问题降低到该问题的分数版本，获得了一些近似算法且吻合上下界，这个技术也可用于其他基于 LP 的问题。

    Jan, 2010

  • 关于确定性机制在设施选址博弈中的威力

    考虑 K-Facility Location games 中的确定性策略对象机制，证明了确定性策略对象机制最佳逼近率为 n-2，并研究了在不同情况下的适用特点，如线性空间情况下存在唯一的独裁者机制，而简单情况下的策略不可能实现有界逼近率。

    Jul, 2012

  • 隐含支付计算的诚实机制

    本文介绍了一种简单而通用的规约方法，可将单参数域的单调分配规则转化为随机机制，使得机制期望上是真实的，并且对于每个实现都是独立的。该机制的运行时间复杂度与 Dijkstra 算法相同，可在机制设计的许多问题中应用。

    Apr, 2010

  • 分类任务带部分验证的自动化机制设计

    本文研究了自动机制设计中的部分验证问题，侧重于所有类型在结果上共享相同偏好的环境中的真实机制，并寻找优化确定性真实机制的有效算法，同时将这些结果推广到代价函数为次模的情况。

    Apr, 2021

  • 云中保留实例销售的随机化机制

    该论文考虑了更加灵活的云计算实例预留价格模型，提出了基于随机化机制的技术来优化社会福利和云服务提供商的收益，得到了较好的成果。

    Nov, 2016

  • 具有独立偏好的分配问题的平均情况分析

    本文研究了基本的分配问题，提出了一种新的机制来最大化效益，即当提供自利智能体对不可分割项目的私人偏好时，我们提出了一种新的机制：随机优先级机制，并且发现这种机制的效率损失具有常数界 。

    Jun, 2019

  • 候选位置设施选址博弈机制设计

    机制设计，通过策略证明机制来解决设施选址游戏，最小化代理的总成本和最大成本，并针对单设施问题和两设施问题分别证明了逼近度的下界和逼近算法。

    Oct, 2020