A Multi-Dimensional Online Contention Resolution Scheme for Revenue Maximization

我们研究了多买家多商品的顺序定价机制，旨在实现一种自然的分数松弛——前期最优收入的近似。我们假设买家的价值是次可加的，但对价值分布没有任何假设。虽然在这种情况下，最优收入以及前期基准是无法通过任何简单的机制近似的，但以前的研究表明，通过所谓的“多次购买”机制进行优化的较弱基准是可以近似的。特别地，已知在单买家或多个单位需求买家的情况下，可以进行近似。我们将这些结果扩展到了更广泛的多个次可加买家的情况。我们展示了通过顺序商品定价可以将前期多次购买收入近似到$O(\log^2 m)$的因子，其中$m$是商品数量。我们还表明，对$m$的对数依赖是必要的。 我们通过构建一个新的多维在线争用解决方案（OCRS）来实现我们的近似，该方案提供了最优前期解的在线舍入。Chawla等人在arXiv:2204.01962中先前构建了一个针对单位需求买家的OCRS，但他们的构建在很大程度上依赖于单位需求值的“几乎单维”特性。在那项工作之前，OCRS仅在单参数买家的社会福利最大化的背景下进行了研究。对于福利目标，已经证明了对商品分配的各种组合约束和买家估值函数类的常数因子近似。我们的工作为收入最大化开辟了类似的成功之路。

多买家多商品顺序定价机制的收益最大化问题

通过构建一个新的多维在线竞争解决方案（OCRS），将最优的ex ante解决方案进行在线舍入，从而实现对ex ante buy-many收益的逼近，从而实现序列商品定价，使其在m个商品的情况下可以在O（log^2 m）的因子内逼近。

论文提出了一种新的多维在线竞争解决方案（OCRS），用于在线舍入最优的ex ante解决方案，实现对ex ante buy-many收益的逼近。这个新的OCRS可以在多个次加性买家的情况下工作，并且是序列商品定价的有效逼近方案。

之前已经有一些关于序列定价的研究，但是该论文的方案是在多个次加性买家的情况下实现序列商品定价的有效逼近方案。