NeurIPS 2020 | 非诚实拍卖中效用与均衡的学习问题

2020 年 11 月 27 日 专知

导读

本文是第三十四届神经信息处理系统大会（NeurIPS 2020）入选论文《非诚实拍卖中效用与均衡的学习问题（Learning Utilities and Equilibria in Non-Truthful Auctions）》的解读。

该论文分析了在（非完美信息的）首价拍卖等非诚实拍卖中估计买家的效用的样本复杂性，即需要多少个来自买家的估值分布的样本才能（以精度 $\epsilon$ ）估计（ $n$ 位）买家在拍卖中采用某组策略时的期望效用，证明了需要且仅需要 $\widetilde{O}\left(\frac{n}{\epsilon^2}\right)$ 个样本就能同时估计所有单调策略的期望效用。作为推论，首价拍卖的（近似）贝叶斯纳什均衡可通过 $\widetilde{O}\left(\frac{n}{\epsilon^2}\right)$ 个样本学得。

论文下载：https://arxiv.org/pdf/2007.01722.pdf

（或点击文末“阅读原文”跳转）

引言

想象你身处一场首价拍卖（first price auction）：卖家拍卖一件物品，另外 $n-1$ 位买家与你竞拍，报价最高的人赢得物品并支付其报价。你内心对这件物品的估值为10元，并思索着应该出价多少。你不会诚实地报价10元，因为这么做的话，你的收益（或称效用（utility），定义为估值减去支付的费用）为0。你的最优报价与其他买家的估值和出价策略有关。但你不知道他们的估值是多少，也不清楚他们的出价策略。幸运的是，你收集到了他们的估值的样本，也就是说，假设他们每个人的估值都服从某个分布 $F_i$ ，你可以从这些分布中抽取一些样本。你开始思考这么一个问题：

我要收集多少个样本，才能针对其他人的所有可能的出价策略，准确估计我在这场拍卖中的期望效用？

本论文告诉你：只要别人的策略是单调的（即估值越高报价越高），那么大约 $O\left(\frac{1}{\epsilon^2}n\right)$ 个样本就够了；而且，你至少需要 $O\left(\frac{1}{\epsilon^2}n\right)$ 个样本。

形式化

在一场首价拍卖中， $n$ 位买家竞拍一件物品。买家 $i\in\left\{1,\ \ldots,\ n\right\}$ 对物品的估值为 $v_i$ ， $v_i$ 服从分布 $F_i$ 。不同买家的估值相互独立。每位买家采取的报价策略为一个函数 $s_i:R_+\rightarrow R_+$ ，即估值为 $v_i$ 时，出价 $b_i=s_i\left(v_i\right)$ 。如果买家 $i$ 出价最高，则他赢得物品，支付他的出价，此时他的效用为 $v_i-b_i$ ；否则他的效用为0。因此，买家 $i$ （在估值 $v_i$ 下）的期望效用为 ${(v}_i-b_i)Pr[b_i>s_j\left(v_j\right),\ \ \forall j\neq i\ |\ v_j\sim F_j].$

每位买家的期望效用与其他买家的估值分布 $F_j$ 和策略 $s_j$ 有关。我们考虑如下“ $\left(\epsilon,\ \delta\right)$ -效用估计问题”：

【定义1： $\left(\epsilon,\ \delta\right)$ -效用估计】从每个分布 $F_i$ 中取 $m$ 个样本，以至少 $1-\delta$ 的概率，同时对所有买家 $i$ ，对所有在区间 $\left[0,\ 1\right]$ 内的估值 $v_i$ 和报价 $b_i$ ，对所有可能被其他买家采用的报价策略 $s_j$ ，以至多 $\epsilon$ 的误差计算买家 $i$ 的期望效用。

注意到，我们希望在抽取样本后，同时估计多种估值和报价策略下的期望效用。如果我们事先固定一位买家，固定他的估值和所有人的报价策略，再通过抽样来估计效用的期望值，则仅需要 $O\left(\frac{1}{\epsilon^2}\right)$ 个样本就够了（用 Chernoff bound 等 concentration inequality 可证）。

主要结果

【定理1】从每个分布 $F_i$ 中取

$m=O\left(\frac{1}{\epsilon^2}\left(n\log{n}\log{\frac{1}{\epsilon}}+\log{\frac{n}{\delta}}\right)\right)$

个样本，我们就能以至少 $1-\delta$ 的概率，同时对所有买家 $i$ ，对所有在区间 $\left[0,\ 1\right]$ 内的估值 $v_i$ 和报价 $b_i$ ，所有单调的报价策略 $s_j$ ，以至多 $\epsilon$ 的误差计算买家 $i$ 的期望效用。

“单调的报价策略”是指报价关于估值递增，即 $s_j(v_j)$ 关于 $v_j$ 单调递增。之所以我们认为买家们只会采用单调的报价策略，是因为可以证明单调策略总是优于（dominate）非单调策略，即单调策略的效用更高。此外，如果我们希望能同时估计任意非单调策略的期望效用，不难证明这需要“无穷多”的样本。

定理1给出了 $\left(\epsilon,\ \delta\right)$ -效用估计问题的样本复杂性的上界。与之相反的是下界问题：至少需要多少样本，才能同时对所有单调策略 $\left(\epsilon,\ \delta\right)$ -估计期望效用？为此，我们有如下定理：

【定理2】无论使用何种算法，为了对任意分布都能 $\left(\epsilon,\ \delta\right)$ -估计单调策略的期望效用，至少需要 $\Omega\left(\frac{n}{\epsilon^2}\right)$ 个样本。

证明思路

我们只介绍定理1的证明思路。我们采用的效用估计算法十分简单：直接在样本组成的均匀分布（即经验分布）上计算期望效用！形式化的，用 $v_j^1,\ \ldots,\ v_j^m$ 表示 $F_j$ 的 $m$ 个样本，我们用下式估计买家 $i$ 的期望效用：

$\frac{1}{m}\sum_{t=1}^{m}{\left(v_i-b_i\right) \cdot {\rm I}\left[b_i>s_j\left(v_j^t\right),\ \forall j\neq i\right]}$ 样本越多，算法的误差越小。为了求使该算法的误差不超过 $\epsilon$ 所需的样本数，我们使用了称为“pseudo-dimension”的技术。Pseudo-dimension 是 VC-dimension 的拓展，用于刻画一个实值函数类的复杂度。

【引理1，[1]】用 $\mathcal{H}$ 表示一个由从输入空间 $\mathcal{X}$ 映射到区间 $\left[0,1\right]$ 的函数组成的集合。如果 $\mathcal{H}$ 的 pseudo-dimension 为 $d$ ，则对任意一个 $\mathcal{X}$ 上的分布 $F$ ，只要从 $F$ 中取 $m=O\left(\frac{1}{\epsilon^2}\left(d\log{\frac{1}{\epsilon}}+\log{\frac{1}{\delta}}\right)\right)$ 个样本，就能保证：以至少 $1-\delta$ 的概率， $\mathcal{H}$ 内所有函数在 $F$ 上的期望被他们在经验分布上的期望近似，误差不超过 $\epsilon$ 。

因此，我们只需分析买家的效用组成的函数类的 pseudo-dimension。我们将效用 $U_i^{v_i,b_i,s_{-i}}\left(v_{-i}\right)=\left(v_i-b_i\right){\rm I}\left[b_i>s_j\left(v_j\right),\forall j\neq i\right]$ 视为将其他买家的估值 $v_{-i}$ 映射到买家 $i$ 的效用的函数。期望效用即效用函数 $U_i^{v_i,b_i,s_{-i}}\left(\cdot\right)$ 在估值分布 $F_{-i}$ 上的期望。

【引理2】对任意买家 $i$ ，其效用函数组成的类 $\mathcal{H}=\{\ U_i^{v_i,b_i,s_{-i}}\ |\ v_i,\ b_i\in\left[0,\ 1\right],\ s_{-i}\ 单调\}$ 的 pseudo-dimension 不超过 $O\left(n\log{n}\right)$ 。

引理1 + 引理2 + union bound on the failure probability => 定理1。

推论

既然买家在真实分布下的期望效用可以被经验分布下的期望效用近似，不难想到，经验分布下的贝叶斯纳什均衡（Bayesian Nash Equilibrium）必然是真实分布下的一个近似贝叶斯纳什均衡。

【推论1】从 $F$ 中取 $m=O\left(\frac{1}{\epsilon^2}\left(n\log{n}\log{\frac{1}{\epsilon}}+\log{\frac{n}{\delta}}\right)\right)$ 个样本，以 $1-\delta$ 的概率，任意一组在经验分布上构成贝叶斯纳什均衡的单调策略 $s_1,\ldots,\ s_n$ 是真实分布下的 $\epsilon$ -近似贝叶斯纳什均衡。反之亦然：任意一组在真实分布上构成贝叶斯纳什均衡的单调策略 $s_1,\ldots,\ s_n$ 是经验分布下的 $\epsilon$ -近似贝叶斯纳什均衡。

推论1可以帮我们计算首价拍卖在任意估值分布上的（近似）贝叶斯纳什均衡。[2]提出了一个多项式时间算法，可以求出首价拍卖在任意离散分布上的（近似）均衡。推论1将[2]推广到了非离散的估值分布：因为经验分布是离散分布，所以只要先从估值分布中采样，然后用[2]的算法求经验分布上的均衡即可。于是我们有如下推论：

【推论2】对于首价拍卖，存在多项式时间算法，可以针对任意估值分布以高概率求出一组近似贝叶斯纳什均衡。

定理1、2和推论1对首价拍卖和“所有人付费拍卖（all pay auction）”都成立。在所有人付费拍卖中，所有买家都要支付自己的报价，不论输赢。

结论

近年来不少文章（如[3, 4, 5]）研究了非完美信息拍卖中的样本复杂性问题。然而，大部分工作考虑的都是卖家收益最大化的样本复杂性，鲜有工作研究买家收益最大化。而且，大部分现有工作都关注诚实拍卖，不涉及非诚实的报价策略。[6]是一个特例：他们研究了非诚实拍卖中一位买家诚实报价的效用与非诚实报价的效用至多相差多少。与本文一样，[6]也采用了“采样->估计”的思路。但他们没有解决如何找到一组同时最大化所有买家的效用的策略（即纳什均衡）的问题，而这正是本文的贡献之一。

基于本文的后续工作可以研究多物品（多参数）拍卖、非独立估值分布等场景下的期望效用估计问题。

参考文献

[1] Martin Anthony and Peter L Bartlett. Neural network learning: Theoretical foundations. Cambridge University Press, 2009.

[2] Weiran Shen, Zihe Wang, and Song Zuo. Bayesian Nash equilibrium in first-price auction with discrete value distributions. AAMAS 2020.

[3] Richard Cole and Tim Roughgarden. The sample complexity of revenue maximization. STOC 2014.

[4] Chenghao Guo, Zhiyi Huang, and Xinzhi Zhang. Settling the sample complexity of single-parameter revenue maximization. STOC 2019.

[5] Johannes Brustle, Yang Cai, and Constantinos Daskalakis. Multi-Item Mechanisms without Item-Independence: Learnability via Robustness. EC 2020.

[6] Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. Estimating approximate incentive compatibility. EC 2019.

NeurIPS

神经信息处理系统大会（Conference on Neural Information Processing Systems, NeurIPS）是人工智能和机器学习领域的国际顶级会议，自1987年开始，每年的12月份，来自世界各地的从事人工智能和机器学习相关的专家学者和从业人士汇聚一堂。NeurIPS 2020将于12月6日-12日在线举行。

专知便捷查看