静5杰出讲座回顾｜叶荫宇教授谈随机Fisher市场中的在线均衡标价问题

关键词：随机Fisher市场，在线标价

编者按

2023年3月31日，斯坦福大学的叶荫宇教授访问北京大学前沿计算研究中心，在静园五院作了题为“Online Equilibrium Pricing in Stochastic Fisher Markets”的报告，介绍了在随机 Fisher 市场中的在线标价问题。报告由中心教授邓小铁老师主持。

叶荫宇教授报告现场

首先，叶老师介绍了 Fisher 市场在资源公平分配上的关键性作用。这里的典型场景是，一个顾客将自己的预算分配在若干产品上，以达到个体效益的最大化。

相应地，从社会整体利益最大化的角度，我们也会得到一个相应的优化问题。Eisenberg 和 Gale 的重要结果证明了这两个优化问题是等价的，而均衡时的物品标价恰好是市场供应限制的相应对偶变量。

然而，传统结果的一个重要局限是所有买家同时进入市场，而相应的资源分配问题也是静态的。叶老师与其合作者的工作考虑了买家有序地进入市场的情况。

在技术上，这一问题场景与在线线性规划（Online Linear Programming，OLP）有很强的相关性。在后者问题中，决策者在每一轮中会收到一个请求，伴随着收益以及相应的资源消耗；这些请求是从某个分布中独立抽取的。而决策者需要立刻、不可修改地决定接受或者拒绝这一请求。决策者的目标是在有限的资源下最大化自己的累计收益。如果我们将决策者看成做市商，而请求看成顾客，则在线线性规划和在线标价这两个问题的紧密联系是显而易见的。

对于在线线性规划问题，前序的工作给出了在线算法和最优解之间差距（称为悔）的上界和下界，都是在请求数量的对数级别。从而，我们期待在在线标价问题上也得到类似的结果。此外，相应的结果也可以被拓展到带有背包约束的老虎机问题（Bandits with Knapsacks，BwK）上。

回到研究的问题上，对于在线标价问题，我们衡量一个算法的标准是比较其所获的社会福利和 Eisenberg-Gale 规划所给出的最优社会福利的差（称为悔），以及资源供应限制的超额程度，在这一框架下，而任何固定标价算法带来的悔或资源超额都至少是顾客数量的平方根级别。

叶老师与其合作者提出的第一个算法是建立在重解法这一思路上的。面对每一个顾客，做市商都会重新求解在剩余资源下的 Eisenberg-Gale 规划，并把相应解中每个资源的价格提供给顾客，并进行更新。这一算法的悔是顾客数量的对数级别，而资源超额则是常数。

然而，上面算法的缺陷在于：（1）算法中每一次进行重解为做市商带来的计算负担比较大；（2）这一算法要求做市商已知顾客类型的分布。从而，在现实中，上面算法的应用是受限的。从而，叶老师与合作者进一步设计了一个基于对偶更新的算法，这里对偶变量的更新采用在线梯度下降的思路。这一算法的悔和约束超额都是顾客数量的平方根量级的。

叶老师对自己工作的介绍引来了同学们的踊跃提问，报告在热烈的探讨中圆满结束。

现场问答

合影留念

图文 | 陈炤桦

PKU daGAME

杰出讲座系列回顾

—   版权声明  —

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。