Sep, 2024

含少量样本的在线组合分配和拍卖

HTML
PDF
TL;DR本研究针对在线组合分配和拍卖中的样本有限性问题，提出了在仅获得每个竞标者一份样本的情况下仍能实现 O(1) 竞争算法的可能性。这一发现利用了一种新颖的秘书式分析扩展。进一步的研究表明，通过多项样本可以获得 (2+\epsilon) 的在线真实机制，显著提升了已有的在线拍卖效果。
发现论文，激发创造
  • 拍卖中的学习：遗憾很难，嫉妒很容易

    本研究提出一种称为“无嫉妒学习”的拍卖学习概念，它是建立在 Walras 均衡基础上的，可有效实现且结果达到近似最优福利，即使投标人有分数次可减（XOS）估值或覆盖估值（无需具备要求），同时扩展到其他在文献中研究过的拍卖格式。

    Nov, 2015

  • 自动机制设计的样本复杂度

    本研究探讨自动机制设计算法在组合拍卖中的应用，提供了关于组合拍卖类的样本复杂度分析，为自动机制设计奠定了坚实基础并推进了学习理论的边界。

    Jun, 2016

  • 高效在线学习和拍卖设计

    本文研究了对手环境下的在线学习算法的设计，提出了广义随机扰动跟随者算法，且证明了在一定条件下它是牛逼优而且可以实现消失的后悔；同时，本文也提出了另一个基于拍卖设计的框架，用于帮助拍卖师在选举获得最佳的拍卖方式方面做出决策，并且得到相应的应用。

    Nov, 2016

  • 多商品利润最大化的泛化保证：定价、拍卖和随机机制

    本文探讨基于样本分布设计多项货品机制，利用分段线性结构证明了利润上限，并提出了优化复杂性和准确性之间的平衡的工具。

    Apr, 2017

  • 组合拍卖的贝叶斯清算机制

    本文基于贝叶斯框架，提出了一种组合拍卖设计方法，采用生成模型和估计最大后验概率算法，通过多次拍卖迭代过程实现过程收敛。实验结果表明，该方法在收敛迭代次数方面比组合时钟拍卖机制更具有竞争力。

    Dec, 2017

  • 在对抗性一价拍卖中学习最优且高效的竞标策略

    本研究探讨了如何学习在首价拍卖中进行出价，针对这一问题开发了首个达到最小化一般策略集的竞标算法，能够显著提升现有竞标算法的效果。这一算法利用专家策略和层级策略，取得了不错的效果，在三个真实场景的测试中表现出了优越性。

    Jul, 2020

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

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

    Feb, 2023

  • 带有预算的重复二价拍卖中的协调动态竞标

    本文研究了协同在线竞标算法在具有预算限制的重复次数第二价格拍卖中的效率，提出保证每个客户比独立竞标获得更高效用价值的算法，并以在线学习和均衡分析为技术支持，实现与多维基准的竞争。

    Jun, 2023

  • 零阶和一阶优化方法相结合的可扩展虚拟估值组合拍卖设计

    通过使用机器学习，自动化竞拍设计旨在发现在经验上高收入和激励相容机制。确保主导策略激励相容性是至关重要的，最有效的方法是将机制限制在仿射最大化拍卖中。然而，现有的基于仿射最大化拍卖的方法面临挑战，如可伸缩性问题（由组合候选分配引起）和收入的非可微性。在本文中，为了实现可扩展的基于仿射最大化拍卖的方法，我们进一步将拍卖机制限制在虚拟估值组合拍卖（VVCA）中，这是一种具有明显较少参数的AMAs子集。首先，我们使用可并行化的动态规划算法来计算VVCA的获胜分配。随后，我们提出了一种结合了零阶和一阶技术来优化VVCA参数的新型优化方法。广泛的实验证明了我们提出的方法[ZFO-VVCA]在应用于大规模拍卖时的功效和可伸缩性。

    Feb, 2024

  • 具有预算和ROI约束的非真实拍卖的无悔算法

    自动投标算法是广告主在在线广告平台上优化广告活动的方式之一，本研究通过设计在线自动投标算法来实现广告主在预算和投资回报率限制下的价值最大化，研究还包括竞标优化、价值分布和成交价相关性等方面。

    Apr, 2024