基于多面体和的快速动态拍卖算法及其在瓦拉西亚均衡中的应用

《ACM Transactions on Economics and Computation》：Faster Dynamic Auctions via Polymatroid Sum

本综述深入探讨了基于多面体和的快速动态拍卖算法，用于寻找具有不可分割物品和强总替代估值函数（strong gross substitutes）市场中的瓦拉西亚均衡（Walrasian equilibrium）。文章核心在于将每次价格调整步骤中寻找极小极大过度需求集（minimal maximally overdemanded set）或极小极大不足需求集（minimal maximally underdemanded set）的问题，转化为一个子模函数最小化问题，并进一步将其视为多面体求和问题（polymatroid sum problem）。通过引入一种快速、简洁的推高重标算法（push-relabel algorithm），本研究显著改进了Murota, Shioura和Yang先前的最佳运行时间。此外，文章还揭示了瓦拉西亚价格在供需变化下的单调性规律，证明了最小/最大瓦拉西亚价格在供给减少或需求增加时只会上升，反之亦然。这些发现源于对市场价格的细粒度分析，并引入了打包价格（packing prices）和覆盖价格（covering prices）的概念，深化了对市场均衡结构的理解。

　　

引言与经济模型

本研究聚焦于计算瓦拉西亚市场均衡的计算和结构方面。考虑一个市场，其中包含一组具有拟线性效用（quasi-linear utilities）的买家，他们有兴趣购买一组商品。主要目标是找到商品的分配以及商品的价格，这些价格应满足以下属性：每个买家获得一个偏好捆绑（preferred bundle），即在该给定价格下最大化其效用的物品集合；没有商品被超额售出；所有商品都被售出；并且该分配是帕累托最优的（Pareto-optimal）。属性1-3共同构成了瓦拉西亚均衡条件，巧合的是，它也意味着属性4，这通常被称为第一福利定理（First Welfare Theorem）。

动态拍卖（dynamic auction）迭代地宣布商品价格，买家报告其需求对应（demand correspondence）。如果存在满足所有需求的可行方式，并且所有商品都分配给了买家，则拍卖以宣布的价格和可行的分配终止。否则，价格将以直观的方式调整：过度需求的商品价格上涨，而需求不足的商品价格下降。

与静态密封投标拍卖（sealed-bid auction）相比，动态拍卖可能耗时更长，但它更具透明度，并且买家无需向拍卖人完全披露其估值函数这一私有信息。此外，在假设买卖双方之间没有通信成本的情况下，密封投标拍卖可能运行得更快，但这要求买家将其估值函数（即对商品所有子集的价值，其数量随商品数量呈指数级增长）全部传达给拍卖人。

动态拍卖通过提高过度需求集或不足需求集上的价格来迭代调整价格。过度需求集是指需求超过供给的物品集合，而极大过度需求集是那些在所有集合中最大化需求与供给之差的过度需求集。类似地可以定义不足需求集（underdemanded sets）和极大不足需求集（maximally underdemanded set）。我们将包含关系极小的极大过度需求集称为极小极大过度需求集。

本研究探讨了四种不同类型的动态拍卖，它们已知在总替代估值的假设下，能以瓦拉西亚价格向量终止。第一种拍卖通过在每个迭代中提高包含关系极小的极大过度需求集上的价格，来计算唯一的分量最小瓦拉西亚价格向量。第二种拍卖通过降低包含关系极小的极大不足需求集上的价格，来计算分量最大瓦拉西亚价格向量。第三种是两阶段拍卖，从任何初始价格向量出发找到某个瓦拉西亚价格。第四种是贪婪拍卖，同样从任何初始价格向量出发找到某个瓦拉西亚价格。

经济模型考虑一个包含m种物品类型和n个买家的市场。每种物品e以u_e个不可分割的单位可用，每个买家i对可能的捆绑包（bundles）有个体估值函数v_i。估值函数被假设为非递减的。对于给定的价格向量p，买家i的效用函数由其估值减去价格给出，即u_i(z; p) = v_i(z) - p^?z。买家i的偏好捆绑集D_i(p)是其在价格p下效用最大化的集合。

利用最小偏好捆绑集D_i^min(p)和最大偏好捆绑集D_i^max(p)，可以量化一个集合S在当前价格p下的供给是过高还是过低。集合S的过度需求度定义为λ^p(S) = Σ_i∈N min_{z∈D_i^min(p)} z(S) - Σ_e∈S u_e。类似地，不足需求度定义为μ^p(S) = Σ_e∈S u_e - Σ_i∈N max_{z∈D_i^max(p)} z(S)。如果一个集合S满足λ^p(S) > 0 [或μ^p(S) > 0]，则称其关于价格p是过度需求的[不足需求的]。极大过度需求集是那些在所有S?M中最大化λ^p(S)的过度需求集。

一个分配x = (x₁, ..., x_n)被称为关于价格p是打包的（packing），如果每个x_i是买家i的偏好捆绑，并且这些集合可以被打包到物品集合中（没有物品被分配过多次）。一个允许打包分配的价格向量p也被称为打包价格。类似地，一个分配是覆盖的（covering），如果存在每个买家一个偏好捆绑，使得这些集合覆盖了所有可用物品。一个价格向量是瓦拉西亚的，如果存在一个分配，它同时是打包的和覆盖的。

强总替代估值函数保证瓦拉西亚价格的存在。对于强总替代估值，瓦拉西亚价格向量在分量序下形成一个格（lattice），因此存在唯一的分量最小和分量最大瓦拉西亚价格向量。

主要贡献

本研究的贡献是双重的：提供了更快的拍卖算法，并提出了关于价格单调性的结构结果。

与Murota等人类似，我们利用李雅普诺夫函数（Lyapunov function）的特殊结构来获得更快的运行时间。我们将子模最小化问题从对偶视角视为一个多面体求和问题，并使用一个快速且简单的推高重标算法来解决这个问题。我们的算法在多供给情况下的运行时间为O(m²n * ExO)，其中ExO是每次交换预言机查询（exchange oracle query）的时间。相比之下，Murota等人的算法运行时间为O(m³n * ExO)。对于单位供给情况，问题变成了经典的拟阵并问题（matroid union problem），我们获得了更好的运行时间O(mn * ExO)。

我们的推高重标算法是Frank和Miklós提出的更一般的子模流可行性算法的一个特殊实现。我们的贡献在于给出了在预言机调用次数方面的高效实现。

第二个主要贡献是关于价格单调性。我们清晰地区分了打包价格、覆盖价格和瓦拉西亚价格。我们证明，对于强总替代估值，分量最小的打包价格与最小瓦拉西亚价格一致，而分量最大的覆盖价格与最大瓦拉西亚价格一致。这些性质进而导致了价格单调性结果：如果物品的供给减少或买家的需求增加，最小和最大瓦拉西亚价格只能增加。

相关研究

总替代条件和瓦拉西亚均衡的研究由来已久。Kelso和Crawford在其开创性论文中表明，如果所有估值函数满足总替代条件，则保证瓦拉西亚均衡的存在。Gul和Stacchetti的最大域定理表明，总替代确实是保证瓦拉西亚均衡存在的最大估值函数类。Fujishige和Yang建立了总替代性质与M-凹性（M-concavity）的等价性，这允许使用离散凸分析（discrete convex analysis）的强大工具。

动态拍卖或瓦拉西亚试探过程由Walras本人提出。Demange等人首次对单位需求估值进行了现代研究。Gul和Stacchetti为总替代估值提供了升序拍卖的框架。Ausubel使用子模函数最小化来填补如何计算这些集合的空白。Murota等人表明李雅普诺夫函数不仅是子模的，而且是M-凸的（M-convex），这允许使用比普通子模函数最小化更快的方法。

在计算复杂性方面，动态拍卖的总体运行时间严重依赖于估值函数，因此在最坏情况下只能是关于物品和买家数量的伪多项式时间。因此，分析单次价格调整步骤的计算问题和通信成本更为合理。

我们的预言机模型仅依赖于给定价格p下最小或最大偏好捆绑集的拟阵性质。我们使用需求预言机（demand oracle）和交换预言机（exchange oracle），这些在拍卖设置中是很自然的。

离散凸性、拟阵并和多面体求和与我们的工作密切相关。推高重标算法在各种组合优化问题中得到了研究，并且在理论和实践上都可以胜过增广路径算法（augmenting path algorithms）。

寻找过度需求和不足需求集

极小极大过度需求集和极小极大不足需求集在动态拍卖的背景下起着重要作用。它们与相应的多面体及其秩函数（rank function）存在联系。

价格向量p是打包的，当且仅当不存在过度需求集。类似地，价格向量p是覆盖的，当且仅当不存在不足需求集。

为了找到这些集合，我们将问题表述为多体求和问题。给定价格p，每个买家i的最小偏好捆绑集D_i^min(p)形成一个M-凸集，因此是某个整数多面体的基多面体的整数点集，其关联的秩函数为ρ_i^p。过度需求度可以重写为λ^p(S) = Σ{i∈N} ρ_i^p(S) - Σ{e∈S} u_e。类似地，不足需求度可以重写为μ^p(S) = Σ{e∈S} u_e - Σ{i∈N} σ_i^p(S)，其中σ_i^p是与最大偏好捆绑集关联的秩函数。

利用多体求和的Min-Max定理，我们可以描述极大过度需求集的特征。具体来说，给定多体求和问题的一个最优解，一个集合S是极大过度需求的，当且仅当它满足三个性质：对于每个买家i，S是紧的（tight）；S不包含任何供给过剩的物品；S包含所有供给不足的物品。而且，存在一个唯一的包含关系最小的满足这些性质的集合。

我们可以通过在多体求和问题的最优解对应的交换图（exchange graph）中进行广度优先搜索来计算极小极大过度需求集。该交换图由物品构成，边由交换预言机查询的权重定义。极小极大过度需求集恰好是那些在交换图中可以到达某个供给不足物品的物品集合。类似的方法也适用于计算极小极大不足需求集。

解决多体求和问题的推高重标算法

推高重标算法是解决子模函数最小化问题或其子类的一种经过充分研究的算法范式。我们首先为多面体提出了一个通用的推高重标框架，并证明其正确性。然后，我们展示了如何首先为拟阵，然后为多面体实现该框架，并分析运行时间。

该算法维护一个水平函数（level function）?: E → Z，其中E是物品集合。算法从所有物品水平为0开始。只要存在水平低于m的供给不足物品，我们就选择一个这样的物品e。然后，我们尝试在该物品上进行推高操作，如果可能的话，否则进行重标操作。

推高操作：如果我们找到一个物品f，其水平?(f) = ?(e) - 1，并且存在一个买家i，使得将e加入其捆绑包同时移除f是可行的（即，保持其偏好捆绑），那么我们就在e上关于i和f执行推高操作。我们选择最大的可能值来交换，使得e不会变得供给过剩。

重标操作：如果找不到这样的物品，我们通过将?(e)增加1来对e进行重标。

该算法保持两个不变性：供给过剩的物品水平为0；对于任何物品e和买家i，水平?(e)不超过买家i当前捆绑包中与e可交换的物品的最小水平加1。

我们证明了该算法保持了水平不变性，并返回多体求和问题的一个最优解。

对于单位供给情况，每个D_i^min(p)是一个拟阵的基集。算法可以更有效地实现，运行时间为O(m^2 n * ExO)。关键之处在于，一个非供给过剩的物品最多只能被一个买家拥有，这简化了搜索过程。

对于多供给情况，我们需要一种不同的方法。我们通过按字典序（lexicographic order）处理买家-物品对来实现推高重标框架。我们证明了一个关键的单调性性质：对于一个固定的物品e，满足推高必要条件的字典序最小的买家-物品对只会增加，直到e被重标。这意味着我们可以通过按字典序递增的顺序遍历所有物品-买家组合来找到所有可能的推高操作。

我们展示了该算法在多供给情况下的运行时间为O(m^2 n * ExO)。运行时间分析考虑了非饱和推高（non-saturating push）的次数，并表明其最多为O(m^2)次。

最小打包价格和最大覆盖价格是瓦拉西亚价格

众所周知，瓦拉西亚价格在分量最小和分量最大操作下形成一个完全格。因此，也存在分量最小和分量最大的瓦拉西亚价格向量。

打包价格和覆盖价格本身已经很有趣，因为它们都构成了较弱的均衡概念。此外，打包价格和覆盖价格是保证存在的，即使对于非强总替代估值函数，例如通过将价格设置得非常高或为零。

一个自然的问题是，这些松弛是否继承了那些格性质，以及最小打包价格或最大覆盖价格（如果存在）是否保证是瓦拉西亚价格。对于非强总替代估值，我们通过例子表明打包价格和覆盖价格不形成格，甚至不存在唯一的最小打包价格向量。

然而，对于强总替代估值，答案是肯定的。我们证明了存在唯一的最小打包价格向量和唯一的覆盖价格向量。此外，我们证明这些向量分别等于最小和最大瓦拉西亚价格向量。

具体来说，我们证明了对于任何打包价格向量q，都有q ≥ p_min，其中p_min是最小瓦拉西亚价格向量。因此，分量最小的打包价格向量存在并且等于p_min。类似地，对于任何覆盖价格向量q，都有q ≤ p_max，其中p_max是最大瓦拉西亚价格向量。因此，分量最大的覆盖价格向量存在并且等于p_max。

这些证明利用了将多供给情况转化为单位供给情况的技巧，并通过分析李雅普诺夫函数和利用总替代估值的性质来完成。

单调性分析

我们展示了在供给和需求方面，对于买家最优（即最小）和卖家最优（即最大）瓦拉西亚价格的单调性结果。

供给减少的单调性：如果某些物品的供给减少，则相应的买家最优和卖家最优瓦拉西亚价格只会增加。

需求增加的单调性：如果买家的总需求增加，则买家最优和卖家最优瓦拉西亚价格只会增加。

这些结果是通过利用最小打包价格和最大覆盖价格与瓦拉西亚价格的等价性，以及总替代估值是良分层（well-layered）的性质来证明的。良分层性质意味着贪心算法（总是选择具有最高边际价值的物品）在每次迭代中计算该大小下具有最高效用的捆绑包。

然而，需要注意的是，如果改变某些买家和某些物品的估值函数，则不存在单调性。我们通过例子表明，对于具有纯加法估值的最小瓦拉西亚价格，当估值改变时，价格不会单调变化。

结论

我们提供了一个简单、组合的算法，用于计算在多物品供给且所有买家具有强总替代估值函数的市场中的极小极大过度需求集和极小极大不足需求集。该算法本质上是使用适当预言机模型的多体求和算法的实现。事实证明，它非常有用，因为它允许快速执行动态拍卖步骤。

此外，我们证明了唯一的最小打包价格和最大的覆盖价格总是存在。唯一的最小打包价格与最小瓦拉西亚价格一致，而唯一的最大覆盖价格与最大瓦拉西亚价格一致。文献中大多忽略了打包价格和瓦拉西亚价格之间的区别。这里所做的清晰区分以及上述结果使我们能够证明最小和最大瓦拉西亚价格在需求和供给变化下的单调性性质。