CA——(RegretNet)Optimal-Auctions-through-Deep-Learning

参考链接：
- 原始论文：Optimal Auctions through Deep Learning，ICML 2019，London School of Economics & Harvard University
- 博客：【论文阅读】Optimal Auctions Through Deep Learning

整体概述

最优拍卖（收益最大化拍卖） ：激励兼容且能最大化预期收益的拍卖机制（这种机制一般称为最优拍卖(Optimal Aucion)机制），这种机制很复杂，很难设计
Myerson拍卖 ：Myerson 在1981年一篇具有开创性的论文中提出了单一物品下的最优拍卖机制
问题提出 ：然而，即使经过了30-40年的深入研究，对于看似简单的多竞拍者、多物品拍卖场景 ，这个问题仍然没有得到解决
论文的内容 ：
- 创新性方法 ：论文开启了利用深度学习工具自动设计最优拍卖机制的探索。将拍卖建模为一个多层神经网络，把最优拍卖设计框架构建为一个带约束的学习问题，并展示了如何使用标准流程来解决它
- 方法论证 ：论文证明了泛化边界，并进行了大量实验，在多物品拍卖场景中，论文基本上恢复了过去已知的所有解析解，并且在最优机制未知的场景中获得了新的拍卖机制

论文设计思路

最优拍卖（Optimal auction）设计是经济理论的基石之一，具有重要的实际意义。在标准的独立私人估值模型中，每个竞拍者对物品子集都有一个估值函数，这些估值函数独立地从不一定相同的分布中抽取。假设拍卖人知道这些分布，并且能够（也会）在设计拍卖机制时利用这些信息。设计拍卖机制的一个主要困难在于，估值是私人信息 ，需要激励竞拍者如实报告他们的估值。目标是找到一种激励兼容的拍卖机制，以实现收益最大化
Myerson 解决了单一物品拍卖时的最优拍卖设计问题（ Myerson ，1981）。但该方案仅限于单物品拍卖，直到30-40年后的今天，即使是对于有两个竞拍者和两个物品的简单场景，这个问题也没有完全解决。今年来的研究中，大多数适用于较弱的贝叶斯激励兼容（BIC）概念
- 贝叶斯激励兼容（BIC） ：
论文的重点是设计满足占优策略激励兼容（DSIC）的拍卖机制，这是一种更稳健、更理想的激励兼容概念

论文的贡献

论文提供了第一个通用的端到端方法来解决多物品拍卖设计问题。使用多层神经网络对拍卖机制进行编码，将竞拍者的估值作为输入，将物品分配和支付决策作为输出。然后，论文使用从估值分布中抽取的样本来训练网络，以便在满足激励兼容约束的情况下最大化预期收益
为了能够使用标准流程来解决这个问题，论文将激励兼容约束重新表述为要求拍卖的预期事后遗憾为零。论文采用增广拉格朗日方法来解决由此产生的约束优化问题，在每次迭代中，论文通过求解一个内部优化问题来找到每个竞拍者和估值 profile 的最优虚报值，从而通过遗憾项推送梯度
论文描述了针对具有加性、单位需求和组合估值的竞拍者的网络架构（注：这几个概念的详细定义见后面的内容），并进行了大量实验，结果表明：
- 理论保障 ：论文的方法能够恢复过去30-40年中多物品拍卖场景下几乎所有的解析解。通过找到收益几乎最优且遗憾极小的拍卖机制，其分配和支付规则与理论上最优拍卖的规则匹配度非常高
- 最优拍卖 ：在最优拍卖未知的场景中，论文的方法能找到收益高且遗憾可忽略不计的拍卖机制，其性能与当前最先进的计算结果相当或更优
- 多竞拍者多物品 ：目前分析文献中研究的最大场景是有2个竞拍者和2个物品，而论文的方法可以为更大的场景学习拍卖机制，例如5个竞拍者、10个物品的场景。在这些场景中，最优拍卖很难设计，而论文的方法能找到遗憾低且收益比强基线更高的拍卖机制
- 注：（其他理论证明）论文还证明了一个新的泛化边界，这意味着，对于论文的架构，在训练数据上的高收益和低遗憾很有可能转化为在新抽取的估值上的高收益和低遗憾

论文中的一些讨论

事后遗憾非论文创新 ：通过关注预期事后遗憾（expected ex post regret），论文采用了对占优策略激励兼容的一种可量化的松弛，这一概念最早在（迪廷等人，2014）中提出。论文的实验表明，这种松弛是逼近最优DSIC拍卖的有效工具
论文的方法更高效 ：虽然最初关于自动拍卖设计的工作将该问题表述为线性规划（LP）（2002；2004），但后续研究已经认识到这种方法存在严重的可扩展性问题，因为它需要的约束和变量数量与参与者和物品的数量呈指数关系（2010）。论文发现，即使对于有2个竞拍者和3个物品的小场景（并且将每个物品的价值离散化为5个区间），LP也需要69个小时才能完成，因为LP需要处理约 $10^5$ 个决策变量和约 $4×10^6$ 个约束。对于相同的场景，论文的方法在9个多小时内就找到了一个遗憾更低的拍卖机制（见表1）

Auction Design as a Learning Problem

拍卖设计基础及符号说明

论文考虑一个有一组 $n$ 个竞拍者 $N = \{1, \ldots, n\}$ 和 $m$ 个物品 $M = \{1, \ldots, m\}$ 的场景。每个竞拍者 $i$ 都有一个估值函数 $v_i: 2^M \to \mathbb{R}_{\geq0}$ ，其中 $v_i(S)$ 表示竞拍者对物品子集 $S \subseteq M$ 的估值。在最简单的情况下，竞拍者可能具有加性估值 ，即她对 $M$ 中单个物品有一个价值，并且她对物品子集 $S \subseteq M$ 的价值为 $v_i(S) = \sum_{j \in S} v_i(\{j\})$。竞拍者 $i$ 的估值函数独立地从分布 $F_i$ 中抽取，取值包含在价值取值空间 $V_i$ 中。论文将估值 profile 写为 $v = (v_1, \ldots, v_n)$ ，并表示 $V = \prod_{i = 1}^{n} V_i$
拍卖人知道分布 $F = (F_1, \ldots, F_n)$ ，但不知道竞拍者实际的估值 $x$ 。竞拍者报告他们的估值（可能不真实），然后拍卖决定将物品分配给哪些竞拍者，并向他们收取费用。论文将拍卖 $(g, p)$ 表示为一对分配规则 $g_i: V \to 2^M$ 和支付规则 $p_i: V \to \mathbb{R}_{\geq0}$ （这些规则可以是随机化的）。给定出价 $b = (b_1, \ldots, b_n) \in V$ ，拍卖计算出分配 $g(b)$ 和支付 $p(b)$
一个估值为 $v_i$ 的竞拍者对出价配置文件 $b$ 的效用为 $u_i(v_i, b) = v_i(g_i(b)) - p_i(b)$ 。竞拍者是策略性的，他们试图最大化自己的效用，可能会报告与他们真实估值不同的出价。令 $v_{-i}$ 表示不包含元素 $v_i$ 的估值 profile $v = (v_1, \ldots, v_n)$ ，类似地定义 $b_{-i}$ ，并令 $V_{-i} = \prod_{j \neq i} V_j$ 表示除竞拍者 $i$ 之外其他竞拍者可能的估值 profile 。如果无论其他竞拍者报告什么，每个竞拍者如实报告时其效用最大，那么这个拍卖就是占优策略激励兼容（DSIC）的。换句话说，对于每个竞拍者 $i$ 、每个估值 $v_i \in V_i$ 、每个出价 $b_i \in V_i$ 以及其他竞拍者的所有出价 $b_{-i} \in V_{-i}$ ，都有 $u_i(v_i, (v_i, b_{-i})) \geq u_i(v_i, (b_i, b_{-i}))$ 。如果每个竞拍者都能获得非零效用，即对于所有 $i \in N$ 、 $v_i \in V_i$ 和 $b_{-i} \in V_{-i}$ ，都有 $u_i(v_i, (v_i, b_{-i})) \geq 0$ ，那么这个拍卖就是（事后）个体理性（IR）的
在DSIC拍卖中，如实报告对每个竞拍者来说是最有利的，因此在估值 profile $v$ 上的收益是 $\sum_{i} p_i(v)$ 。最优拍卖设计旨在找到一个DSIC拍卖，以最大化预期收益

表述为 Learning Problem

论文将最优拍卖设计问题表述为一个学习问题，在这里，论文不使用衡量与目标标签误差的损失函数，而是采用从 $F$ 中抽取的估值上的负预期收益。论文给定一个参数化的拍卖类 $(g^w, p^w) \in \mathcal{M}$ ，其中参数 $w \in \mathbb{R}^d$ （ $d \in \mathbb{N}$ ），以及一个从 $F$ 中独立同分布抽取的竞拍者估值 profile 样本 $S = \{v^{(1)}, \ldots, v^{(L)}\}$ 。目标是在所有满足激励兼容性的拍卖中，找到一个使负预期收益 $-\sum_{i \in N} p_i^w(v)$ 最小的拍卖
特别地，论文在学习问题中引入约束，以确保所选的拍卖满足激励兼容性。为此，论文定义每个竞拍者的事后遗憾，来衡量拍卖违反激励兼容性的程度。固定其他竞拍者的出价，一个竞拍者的事后遗憾是她考虑所有可能的非如实出价时，效用的最大增加量。论文关注竞拍者 $i$ 的预期事后遗憾：
$$rgt_i(w) = \mathbb{E}_{v\sim F}\left[\max_{v_i’ \in V_i} u_i^w(v_i; (v_i’, v_{-i})) - u_i^w(v_i; (v_i, v_{-i}))\right]$$
- 其中期望是对 $v \sim F$ 取的，并且对于给定的模型参数 $w$ ， $u_i^w(v_i, b) = v_i(g_i^w(b)) - p_i^w(b)$ 。论文假设 $F$ 在估值取值空间 $V$ 上具有完全支撑，并且认识到遗憾是非负的，一个拍卖满足DSIC当且仅当对于所有 $i \in N$ ， $rgt_i(w) = 0$
- 特别说明：$V_{i \cdot }$ 是估值取值空间（估值空间，包含所有可能得估值集合）
- 个人理解：$rgt_{i \cdot } \geq 0 $ 可衡量一个机制的满足 DSIC 条件的程度。任意一个 $\boldsymbol{v}$ 都是一个包含所有竞拍者真实私有价值 ，$u_{i \cdot }$ 则与机制 $\mathcal{M}(g,p)$ 有关，由于 $\boldsymbol{v}$ 是竞拍者真实私有估值（相当于都在说真话），此时满足 DSIC 条件的机制下，应该有事后遗憾 $rgt_{i \cdot } = 0 $。从更加广义的松弛视角看，机制越满足 DSIC 条件，则事后遗憾值应该越小，最小值为0
- 模型训练中，$rgt_{i \cdot }$ 越小的机制越满足 DSIC 条件
鉴于此，论文将学习问题重新表述为最小化预期损失，即在每个竞拍者的预期事后遗憾为0的条件下，最小化预期负收益：
$$\min_{w \in \mathbb{R}^d} \mathbb{E}_{v \sim F}\left[-\sum_{i \in N} p_i^w(v)\right] \\ \text{ s.t. } rgt_i(w) = 0, \forall i \in N$$
给定一个来自 $F$ 的 $L$ 个估值 profile 的样本 $S$ ，论文估计竞拍者 $i$ 的经验事后遗憾为：
$$\hat{rgt}_i(w) = \frac{1}{L} \sum_{\ell = 1}^{L} \max_{v_i’ \in V_i} u_i^w(v_i^{(\ell)}; (v_i’, v_{-i}^{(\ell)})) - u_i^w(v_i^{(\ell)}; v^{(\ell)})$$
并寻求在所有竞拍者的经验遗憾为零的条件下，最小化经验损失：
$$\min_{w \in \mathbb{R}^d} -\frac{1}{L} \sum_{\ell = 1}^{L} \sum_{i = 1}^{n} p_i^w(v^{(\ell)}) \\ \text{ s.t. } \hat{rgt}_i(w) = 0, \forall i \in N$$

个体理性

论文还将要求设计的拍卖满足个体理性，这可以通过将搜索空间限制在一类参数化拍卖 $(g^w, p^w)$ 中来实现，这类拍卖向任何竞拍者收取的费用都不超过她对分配的预期效用。在第3节中，论文将分配和支付规则建模为神经网络，并在架构中纳入个体理性要求

泛化边界（TODO）

论文根据抽取的估值 profile 数量来界定预期遗憾和经验遗憾之间的差距。论文对收益也展示了类似的结果。论文的边界适用于从有限容量类中选择的任何拍卖，这意味着用大样本求解（2）式会得到一个预期收益接近最优且预期遗憾接近零的拍卖（论文注意到，在实践中，论文可能无法精确求解（2）式）
论文使用排名文献中使用的覆盖数定义来衡量拍卖类的容量（鲁丁和沙皮尔，2009）。论文定义拍卖 $(g, p)$ ， $(g’, p’) \in \mathcal{M}$ 之间的 $\ell_{\infty, 1}$ 距离为 $\max_{v \in V} \sum_{i, j}|g_{ij}(v) - g_{ij}’(v)| + \sum_{i}|p_i(v) - p_i’(v)|$ 。对于任何 $\epsilon > 0$ ，令 $N_{\infty}(\mathcal{M}, \epsilon)$ 是在 $\ell_{\infty, 1}$ 距离下覆盖 $\mathcal{M}$ 所需的半径为 $\epsilon$ 的最小球数
定理1 ：对于每位竞拍者 $i$，不失一般性地假设其估值函数 $v_{i}(S)\leq1$，其中 $\forall S\subseteq M$。设 $\mathcal{M}$为满足个体理性的拍卖类别。固定 $\delta\in(0,1)$。从 $F$中抽取 $L$个估值 profile 样本 $s$，至少以 $1-\delta$的概率，对于任何 $(g^{w}, p^{w})\in\mathcal{M}$，有：
$$\mathbb{E}_{v\sim F}\left[-\sum_{i\in N}p_{i}^{w}(v)\right]\leq -\frac{1}{L}\sum_{\ell = 1}^{L}\sum_{i = 1}^{n}p_{i}^{w}(v^{(\ell)})+2n\Delta_{L}+Cn\sqrt{\frac{\log(1/\delta)}{L}}$$
- 并且
  $$\frac{1}{n}\sum_{i = 1}^{n}rgt_{i}(w)\leq\frac{1}{n}\sum_{i = 1}^{n}\widehat{rgt}_{i}(w)+2\Delta_{L}+C’\sqrt{\frac{\log(1/\delta)}{L}}$$
  - 其中 $\Delta_{L}=\inf_{\epsilon>0}\left\{\frac{\epsilon}{n}+2\sqrt{\frac{2\log(N_{\infty}(\mathcal{M},\epsilon/2))}{L}}\right\}$，$C$、$C’$为与分布无关的常数
- 证明见附录。若上述边界中的 $\Delta_{L}$项随着样本量 $L$的增加而趋于 0，则当 $L\rightarrow\infty$时，上述边界也趋于 0。在第 3 节的定理 2 中，论文给出了论文所提出神经网络架构的 $\Delta_{L}$上界

神经网络架构

论文描述用于对多物品拍卖进行建模的神经网络架构，称为RegretNet。论文考虑具有加性、单位需求和一般组合估值的竞拍者。该架构包含两个逻辑上不同的组件：分配网络和支付网络

加性估值下的网络架构

如果竞拍者对物品束（bundle of item） $S\subseteq M$的价值是她对 $S$中单个物品价值的总和，即 $v_{i}(S)=\sum_{j\in S}v_{i}(j)$，则该竞拍者具有加性估值。在这种情况下，竞拍者仅报告他们对单个物品的估值。此场景下的架构对随机分配网络 $g^{w}:\mathbb{R}^{nm}\to[0,1]^{nm}$和支付网络 $p^{w}:\mathbb{R}^{nm}\to\mathbb{R}_{\geq0}^{n}$进行建模，这两个网络均被建模为具有双曲正切（tanh）激活函数的前馈全连接网络。网络的输入层由表示竞拍者 $i$对物品 $j$估值的出价 $b_{ij}$组成
分配网络为每个物品 $j\in[m]$输出一个分配概率向量 $z_{1j}=g_{1j}(b),\cdots,z_{nj}=g_{nj}(b)$。为确保可行性，即物品被分配的概率至多为 1，分配概率通过softmax激活函数计算，使得对于所有物品 $j$，$\sum_{i = 1}^{n}z_{ij}\leq1$。为适应物品未分配给任何竞拍者的可能性，论文在softmax计算中引入一个虚拟节点，用于保留剩余的分配概率。由于将物品分配给同一竞拍者的输出单元可能相关，因此可以实现物品捆绑
支付网络 ：为每个竞拍者输出一个支付金额，表示该竞拍者针对此特定出价配置文件的预期支付金额。为确保拍卖满足个体理性，即向竞拍者收取的费用不超过其对分配的预期价值，网络首先使用sigmoid单元为每个竞拍者 $i$计算一个分数支付 $\tilde{p}_{i}\in[0,1]$，并输出支付 $p_{i}=\tilde{p}_{i}\sum_{j = 1}^{m}z_{ij}b_{ij}$，其中 $z_{ij}$是分配网络的输出。架构概述见图1，其中收益和遗憾是根据分配网络和支付网络的参数计算得出的

单位需求估值下的网络架构

（这部分比较晦涩，待进一步理解）

当竞拍者对物品束 $S\subseteq M$ 的价值是她对束中单个物品分配的最大价值时（理解：说明至多只能分配一个物品），即 $v_{i}(S)=\max_{j\in S}v_{i}(j)$，该竞拍者具有单位需求估值。单位需求竞拍者的分配网络是图2所示的前馈网络。在这个场景中为实现收益最大化，可以证明考虑为每个竞拍者分配至多一个物品的分配规则就足够了。在随机分配规则的情况下，这要求每个竞拍者的总分配至多为1，即 $\sum_{j}z_{ij}\leq1$，$\forall i\in[n]$。论文还要求任何物品都不会被过度分配，即 $\sum_{i}z_{ij}\leq1$，$\forall j\in[m]$
- 因此，论文设计的分配网络其输出概率矩阵 $[z_{ij}]_{i,j = 1}^{n}$是双随机的（注：doubly stochastic matrix，双随机矩阵是指每行每列之和为1 ，且单个元素值大于0的矩阵，论文中似乎将行列之和放松为小于等于1了）
具体来说，论文让分配网络计算两组分数 $s_{ij}$和 $s_{ij}’$，第一组分数按行归一化，第二组分数按列归一化。这两组归一化都可以通过将分数输入softmax函数来实现。然后，竞拍者 $i$对物品 $j$的分配计算为相应归一化分数中的最小值：
$$z_{ij}=\varphi_{ij}^{DS}(s,s’)=\min\left\{\frac{e^{s_{ij}}}{\sum_{k = 1}^{n + 1}e^{s_{kj}}},\frac{e^{s_{ij}’}}{\sum_{k = 1}^{m + 1}e^{s_{jk}’}}\right\}$$
- 其中索引 $n + 1$和 $m + 1$表示虚拟输入，分别对应物品未分配给任何竞拍者以及竞拍者未分配到任何物品的情况
引理1 ：对于 $\forall s$，$s’\in\mathbb{R}^{nm}$，$\varphi^{DS}(s,s’)$是双随机的。对于任何双随机分配 $z\in[0,1]^{nm}$，存在 $s$，$s’\in\mathbb{R}^{nm}$，使得 $z=\varphi^{DS}(s,s’)$
- 注：双随机矩阵式行和列的和都等于1的矩阵，论文将双随机矩阵的行列和定义为小于等于1 ，所以引理1才能成立，否则是不成立的
支付网络与图1中的相同

组合估值下的网络架构

论文还考虑具有一般组合估值的竞拍者。在本研究中，论文仅针对少量物品开发了这种架构
在这种情况下，每个竞拍者 $i$针对每个物品束 $S\subseteq M$（空束除外，其估值视为零）报告一个出价 $b_{i,S}$。分配网络为每个竞拍者 $i$和物品束 $S$输出一个 $z_{i,S}\in[0,1]$，表示该竞拍者被分配到该物品束的概率。为防止物品被过度分配，论文要求物品出现在分配给某个竞拍者的物品束中的概率至多为1。论文还要求分配给每个竞拍者的物品束总量至多为1（约束（3）和约束（4））：
$$\sum_{i\in N}\sum_{S\subseteq M:j\in S}z_{i,S}\leq1,\forall j\in M \\
\sum_{S\subseteq M}z_{i,S}\leq1,\forall i\in N$$
- 论文将满足上述约束（3）和（4）的分配称为组合可行分配。为强制执行这些约束，论文让分配网络为每个物品计算一组分数，并为每个竞拍者计算一组分数。具体而言，对于每个竞拍者 $i\in N$，有一组竞拍者相关分数 $s_{i,S}$，$\forall S\subseteq M$；对于每个物品 $j\in M$，有一组物品相关分数 $s_{i,S}^{(j)}$，$\forall i\in N$，$S\subseteq M$。每组分数都使用softmax函数进行归一化：$\bar{s}_{i,S}=\frac{\exp(s_{i,S})}{\sum_{S’}\exp(s_{i,S’})}$和 $\bar{s}_{i,S}^{(j)}=\frac{\exp(s_{i,S}^{(j)})}{\sum_{i’,S’}\exp(s_{i’,S’}^{(j)})}$。竞拍者 $i$对物品束 $S\subseteq M$的分配定义为 $i$的归一化竞拍者相关分数 $\bar{s}_{i,S}$与 $S$中每个物品 $j$的归一化物品相关分数 $\bar{s}_{i,S}^{(j)}$中的最小值：
  $$z_{i,S}=\varphi_{i,S}^{CF}(s,s^{(1)},\cdots,s^{(m)})=\min\left\{\bar{s}_{i,S},\bar{s}_{i,S}^{(j)}:j\in S\right\}$$
引理2 ：对于 $\forall s$，$s^{(1)},\cdots,s^{(m)}\in\mathbb{R}^{n2^{m}}$，$\varphi^{CF}(s,s^{(1)},\cdots,s^{(m)})$是组合可行的。对于任何组合可行分配 $z\in[0,1]^{n2^{m}}$，存在 $s$，$s^{(1)},\cdots,s^{(m)}\in\mathbb{R}^{n2^{m}}$，使得 $z=\varphi^{CF}(s,s^{(1)},\cdots,s^{(m)})$
图2（b）展示了有2个竞拍者和2个物品场景下的网络架构。为便于说明，论文在讨论中忽略空物品束。对于每个竞拍者 $i\in\{1,2\}$，网络为她可能被分配的每个物品束计算三个分数 $s_{i,\{1\}}$，$s_{i,\{2\}}$和 $s_{i,\{1,2\}}$，并使用softmax函数对其进行归一化。网络还为物品1计算四个分数：$s_{1,\{1\}}^{1}$，$s_{2,\{1\}}^{1}$，$s_{1,\{1,2\}}^{1}$和 $s_{2,\{1,2\}}^{1}$，即物品1存在于每个分配中的分数，类似地，为物品2计算四个分数：$s_{1,\{2\}}^{2}$，$s_{2,\{2\}}^{2}$，$s_{1,\{1,2\}}^{2}$和 $s_{2,\{1,2\}}^{2}$。然后，每组分数都通过单独的softmax函数进行归一化。每个竞拍者的最终分配为：$z_{i,\{1\}}=\min\{\bar{s}_{i,\{1\}},\bar{s}_{i,\{1\}}^{1}\}$，$z_{i,\{2\}}=\min\{\bar{s}_{i,\{2\}},\bar{s}_{i,\{2\}}^{2}\}$，$z_{i,\{1,2\}}=\min\{\bar{s}_{i,\{1,2\}},\bar{s}_{i,\{1,2\}}^{1},\bar{s}_{i,\{1,2\}}^{2}\}$
组合竞拍者的支付网络与图1中的结构相同，使用sigmoid单元为每个竞拍者 $i$计算一个分数支付 $\tilde{p}_{i}\in[0,1]$，并输出支付 $p_{i}=\tilde{p}_{i}\sum_{S\subseteq M}z_{i,S}b_{i,S}$，其中 $z_{i,S}$是分配网络的输出

覆盖数边界

论文现在为上述神经网络在定理1的泛化边界中界定 $\Delta_{L}$项
定理2 ：对于具有 $R$个隐藏层、每个隐藏层有 $K$个节点、分配网络有 $d_{a}$个参数、支付网络有 $d_{p}$个参数且所有模型参数向量 $|w|_{1}\leq W$的RegretNet，对于不同竞拍者估值类型，$\Delta_{L}$项的边界如下：
加性估值 ：
$$\Delta_{L}\leq O\left(\sqrt{\frac{R(d_{a}+d_{p})\log(LW\max\{K,mn\})}{L}}\right)$$
单位需求估值 ：
$$\Delta_{L}\leq O\left(\sqrt{\frac{R(d_{a}+d_{p})\log(LW\max\{K,mn\})}{L}}\right)$$
组合估值 ：
$$\Delta_{L}\leq O\left(\sqrt{\frac{R(d_{a}+d_{p})\log\left(LW\max\left\{K,n2^{m}\right\}\right)}{L}}\right)$$
证明见附录。随着样本量 $L\rightarrow\infty$，$\Delta_{L}\rightarrow0$。上述结果对网络层数、节点数和参数的依赖与神经网络的标准覆盖数边界类似（安东尼和巴特利特，2009）。注意，组合估值边界中的对数项抵消了对物品数量 $m$的指数依赖

优化与训练

论文使用增广拉格朗日方法在神经网络参数 $w$的空间上求解（2）式中的约束训练问题。首先，论文为优化问题定义拉格朗日函数，并添加一个用于惩罚违反约束的二次项：
$$\mathcal{C}_{\rho}(w;\lambda)=-\frac{1}{L}\sum_{\ell = 1}^{L}\sum_{i\in N}p_{i}^{w}(v^{(\ell)})+\sum_{i\in N}\lambda_{i}\widehat{rgt}_{i}(w)+\frac{\rho}{2}\left(\sum_{i\in N}\widehat{rgt}_{i}(w)\right)^{2}$$
- 其中 $\lambda\in\mathbb{R}^{n}$是拉格朗日乘子向量，$\rho>0$是一个固定参数，用于控制二次惩罚项的权重。求解器在每次迭代中对模型参数和拉格朗日乘子进行以下交替更新：
  - （a）$w^{new}\in\arg\min_{w}\mathcal{C}_{\rho}(w^{old};\lambda^{old})$；
  - （b）$\lambda_{i}^{new}=\lambda_{i}^{old}+\rho\widehat{rgt}_{i}(w^{new})$，$\forall i\in N$
- 理解：对于 regret 约束，给了一次项惩罚和二次项惩罚
- 问题：在训练时如何计算 $\widehat{rgt}_{i}(w)$ ?
  - 回答：计算公式为
    $$\hat{rgt}_i(w) = \frac{1}{L} \sum_{\ell = 1}^{L} \max_{v_i’ \in V_i} u_i^w(v_i^{(\ell)}; (v_i’, v_{-i}^{(\ell)})) - u_i^w(v_i^{(\ell)}; v^{(\ell)})$$
    - 其中 $V_i$ 出价可能的取值集合（即取值空间），猜测可以通过随机采样几个值 ，或提前定义几个按照固定间隔采样取值，再取他们对应效用函数中的最大值即可作为近似最大效用函数
具体训练流程如下：
求解器如算法1所示。论文将训练样本 $s$划分为大小为 $B$的 minibatch，并对训练样本进行多次遍历（每次遍历后对数据进行随机洗牌）。论文将第 $t$次迭代时收到的 minibatch 记为 $S_{t}=\{u^{(1)},\cdots,u^{(B)}\}$。对模型参数的更新（a）涉及对 $\mathcal{C}_{\rho}$关于 $w$的无约束优化，使用基于梯度的优化器进行。令 $\tilde{rgt}_{i}(w)$表示在 minibatch $S_{t}$上计算的经验遗憾（见（1）式）。对于固定的 $\lambda^{t}$，$\mathcal{C}_{\rho}$关于 $w$的梯度为：
$$\nabla_{w}\mathcal{C}_{\rho}(w;\lambda^{t})=-\frac{1}{B}\sum_{\ell = 1}^{B}\sum_{i\in N}\nabla_{w}p_{i}^{w}(v^{(\ell)})+\sum_{i\in N}\sum_{\ell = 1}^{B}\lambda_{i}^{t}g_{\ell,i}+\rho\sum_{i\in N}\sum_{\ell = 1}^{B}\tilde{rgt}_{i}(w)g_{\ell,i}$$
- 其中
  $$g_{\ell,i}=\nabla_{w}\left[\max_{v_{i}’\in V_{i}}u_{i}^{w}(v_{i}^{(\ell)};(v_{i}’,v_{-i}^{(\ell)})) - u_{i}^{w}(v_{i}^{(\ell)};v^{(\ell)})\right]$$
- 注意，$rgt$和 $g_{\ell,i}$项涉及对每个竞拍者 $i$和估值 profile $\ell$的虚报值求 “最大值”。论文使用另一个基于梯度的优化器求解关于虚报值的内部最大化问题，并通过最优虚报值处的效用差异推送梯度。具体来说，论文为每个 $i$和估值 profile $\ell$维护虚报值 $v_{i}^{(\ell)}$。对于模型参数 $w^{t}$的每次更新，执行 $R$次梯度更新以计算最优虚报值：$v_{i}^{(\ell)}=v_{i}^{\prime(\ell)}+\gamma\nabla_{v_{i}’}u_{i}^{w}(v_{i}^{(\ell)};(v_{i}^{\prime(\ell)},v_{-i}^{(\ell)}))$，其中 $\gamma>0$。在论文的实验中，论文使用Adam优化器（金马和巴，2014）对模型 $w$和 $v_{i}^{(\ell)}$进行更新
由于论文试图解决的优化问题是非凸的，求解器不能保证达到全局最优解。然而，在论文的实验中，论文的方法非常有效。学习到的拍卖机制产生的遗憾非常低，并且在已知最优拍卖结构的场景中，与最优拍卖结构非常匹配

实验结果

论文证明了论文的方法能够在几乎所有已知最优解的场景中找到接近最优的拍卖方案，并且在没有已知解析解的场景中发现新的拍卖方案。论文在附录中给出了完整的实验集，这里展示部分具有代表性的结果

Experiment Setup

框架：论文使用TensorFlow深度学习库实现了论文的框架
架构：所有网络均采用Glorot均匀初始化，隐藏节点使用tanh激活函数
数据集 ：在所有实验中，论文使用640,000个估值 profile 的样本进行训练，10,000个配置文件的样本进行测试
超参数设置 ：增广拉格朗日求解器最多运行80个轮次（epoch）， minibatch （minibatch）大小为128。增广拉格朗日中的超参数ρ初始值设为1.0 ，每2个轮次增加一次。每次 minibatch 更新时，使用学习率为0.001的Adam优化器更新w。每次更新w时，论文以0.1的学习率运行25次虚报更新步骤。在25次更新结束时，当前 minibatch 的优化虚报值会被缓存，并用于下一轮次相同 minibatch 的虚报值初始化。每100个 minibatch 更新一次拉格朗日乘子λ（即Q = 100）
硬件环境 ：论文的实验在配备NVIDIA GPU核心的计算集群上运行

评估指标

除了在测试集上评估学习到的拍卖机制的收益外，论文还评估所有竞拍者和测试估值 profile 上的平均遗憾值，计算公式为 $rgt = \frac{1}{n} \sum_{i = 1}^{n} \widehat{rgt}_{i}(f, p)$。每个 $\widehat{rgt}_{i}$ 都涉及在竞拍者估值 $v_{i}’ \in V_{i}$ 上对效用函数取“最大值”（见公式(1)）。论文通过对 $v_{i}’$ 进行2000次步长为0.1的梯度上升操作来评估这些项（论文测试1000个不同的随机初始 $v_{i}’$，并报告产生最大遗憾值的那个）

单个竞拍者

即使在单竞拍者拍卖的简单场景中，也只有在特殊情况下才有解析解。论文给出了第一种能够处理一般设计问题的计算方法，并与现有的解析结果进行比较。结果表明，论文不仅能够学习到收益接近最优的拍卖机制，而且能够学习到与理论最优规则惊人相似的分配规则
- 场景（I） ：单个竞拍者对2个物品具有加性估值，物品价值从均匀分布U[0,1]中抽取。最优拍卖方案由Manelli & Vincent (2006)给出
- 场景（II） ：单个竞拍者对2个物品具有单位需求估值，物品价值从均匀分布U[2,3]中抽取。最优机制由Pavlov (2011)给出
图3（a）展示了为场景（I）和（II）学习到的最终拍卖机制在测试集上的收益和遗憾值，所使用的网络架构有两个隐藏层，每层100个节点。学习到的拍卖机制的收益非常接近最优收益，遗憾值可忽略不计。在某些情况下，学习到的拍卖机制实现的收益略高于最优激励兼容拍卖。这是因为它们产生了很小的非零遗憾值。图4（a） - （b）中学习到的分配规则可视化结果表明，论文的方法也能很好地还原最优拍卖的结构。图3（c）展示了收益和遗憾值随训练轮次变化的曲线。求解器自适应地调整遗憾值上的拉格朗日乘子，在初始迭代中关注收益，在后续迭代中关注遗憾值

多个竞拍者

接下来，论文将论文的结果与Sandholm和Likhodedov（Sandholm & Likhodedov, 2015）在最优拍卖未知场景下的最先进计算结果进行比较。这些拍卖是通过在一类参数化的激励兼容拍卖中搜索得到的。与这些先前的方法不同，论文不需要在特定的激励兼容拍卖类中搜索，仅受所使用网络的表达能力限制。结果表明，这能产生新颖的拍卖设计，其性能与现有最先进机制相当甚至更优
- 场景（III） ：2个加性估值的竞拍者和2个物品，竞拍者对每个物品的价值从U[0,1]中抽取
- 场景（IV） ：2个竞拍者和2个物品，其中$v_{1,1}, v_{1,2}, v_{2,1}, v_{2,2} \sim U[1,2]$，$v_{1,\{1,2\}} = v_{1,1} + v_{1,2} + C_{1}$，$v_{2,\{1,2\}} = v_{2,1} + v_{2,2} + C_{2}$，$C_{1}, C_{2} \sim U[-1,1]$
- 场景（V） ：2个竞拍者和2个物品，其中$v_{1,1}, v_{1,2} \sim U[1,2]$，$v_{2,1}, v_{2,2} \sim U[1,5]$，$v_{1,\{1,2\}} = v_{1,1} + v_{1,2} + C_{1}$，$v_{2,\{1,2\}} = v_{2,1} + v_{2,2} + C_{2}$，$C_{1}, C_{2} \sim U[-1,1]$
论文采用与场景（I） - （II）相同的实验设置。将训练得到的机制与来自VVCA和 $AMA_{bsym}$ 系列的激励兼容拍卖的最优拍卖方案进行比较（Sandholm & Likhodedov, 2015）。图3（b）总结了论文的结果。论文的方法带来了显著的收益提升，且遗憾值极小。与图3（a）相比，场景（I）中0.004（即0.72%）的遗憾值带来了收益优势，但在这些先前结果的对比下，这种微小的非零遗憾似乎不太可能解释论文方法在收益上的优势

扩展性测试

论文还考虑了多达5个竞拍者和10个物品的场景。由于问题的指数性质，这比现有分析文献所能处理的问题复杂几个数量级。在论文研究的场景中，在竞拍者数量趋于无穷时，对每个物品分别进行Myerson拍卖是最优的（Palfrey, 1983）。这提供了一个很强但仍可改进的基准
- 场景（VI） ：3个加性估值的竞拍者和10个物品，竞拍者对每个物品的价值从U[0,1]中抽取
- 场景（VII） ：5个加性估值的竞拍者和10个物品，竞拍者对每个物品的价值从U[0,1]中抽取
对于场景（VI），论文在图5（a）中展示了使用不同架构在10,000个配置文件的验证样本上学习到的拍卖机制的收益和遗憾值。这里 $(R, K)$ 表示具有R个隐藏层和每层K个节点的架构。在上述两种场景中，(5, 100)架构在所有100节点的网络中遗憾值最低。图5（b）表明，与基线相比，最终学习到的拍卖机制产生了更高的收益（遗憾值极小）

与线性规划（LP）的比较

论文还将论文算法的运行时间与Conitzer和Sandholm（2002; 2004）提出的LP方法进行比较。为了能够完整运行LP，论文考虑一个较小的场景，即2个加性估值的竞拍者和3个物品，物品价值从U[0,1]中抽取。使用商业求解器Gurobi求解LP。论文通过将每个物品的价值离散化为5个区间来处理连续估值（这会产生约 $10^5$ 个决策变量和约 $4×10^6$ 个约束），然后将连续的输入估值 profile 四舍五入到最接近的离散配置文件进行评估。关于LP的进一步讨论见附录
结果如表1所示。论文还报告了LP在测试集上违反个体理性（IR）约束的情况；对于L个估值 profile ，其计算方式为 $\frac{1}{Ln} \sum_{\ell = 1}^{L} \sum_{i \in N} \max(u_{i}(v^{(\ell)}), 0)$。由于粗粒度的离散化，LP方法存在显著的IR约束违反情况（因此产生了更高的收益）。对于更精细的离散化，论文无法在一周以上的计算时间内运行LP。相比之下，论文的方法在大约9小时内就产生了低得多的遗憾值，并且没有IR约束违反情况（因为神经网络在设计上满足IR）。实际上，即使对于更大的场景（VI） - （VII），论文算法的运行时间也不到13小时

附录：双随机矩阵（doubly stochastic matrix）

双随机矩阵（doubly stochastic matrix），在数学中，是一种特殊的方阵，其满足以下条件：
- 非负性：矩阵中的每个元素都是非负的。这意味着对于任意的元素 $P_{ij}$ 来说，都有 $P_{ij} \geq 0$
- 行和为1：每一行的所有元素之和都等于1。即对于所有的行索引 $i$，有 $\sum_j P_{ij} = 1$
- 列和为1：每一列的所有元素之和也都等于1。即对于所有的列索引 $j$，有 $\sum_i P_{ij} = 1$
- 随机这两个字的理解：随机是指概率，也就是行列都可以单抽出来作为一个概率的矩阵
一句话定义 ：每行的元素加起来是1，而且每列的元素加起来也是1，并且所有元素都是非负数，那么这个矩阵就是双随机矩阵
注：论文中对双随机矩阵定义有修改，论文中将双随机矩阵的定义修改为了行列和小于等于1