偏好单调性的神经网络：组合分配问题的新机器学习方法

+v：mala2277获取更多论文1单调值神经网络：利用偏好单调性进行组合分配Jakob Weissteiner1，3<$，Jakob Heiss2，3<$，Julien Siems1<$andSvenSeuken1，31苏黎世大学2苏黎世联邦理工3ETH AI中心weissteiner@ifi.uzh.ch，jakob. math.ethz.ch，juliensiems@gmail.com，jakoben@ifi.uzh.ch摘要许多重要的资源分配问题涉及物品的组合分配，例如，拍卖或课程分配。由于bundle空间中的项目数量呈指数级增长，因此偏好诱导是这些领域的关键挑战。最近，研究人员提出了基于ML的机制，优于交易机制，同时减少代理的偏好诱导成本。然而，所使用的ML算法的一个主要缺点是它们忽视了关于代理为了解决这个问题，我们引入了单调值神经网络（MVNN），它被设计为捕获组合值，同时强制单调性和正常性。在技术层面上，我们证明了我们的MVNN在单调和归一化值函数类中是通用的，并且我们提供了一个混合整数线性规划（MILP）公式，使解决基于MVNN的获胜者确定问题（WDP）实际可行。我们评估例如，重新分配渔获量份额[Bichler等人，，2019]。在没有资金的领域，一个流行的例子是组合课程分配，其中课程座位分配给大型商学院的学生[Budish，2011]。所有这些域的共同点是，代理可以报告项目包的值，而不仅仅是单个项目的值。这使他们能够表达更复杂的偏好，即，一个代理人然而，由于捆绑包空间的项目数量呈指数级增长因此，简约偏好的启发是设计实用的组合分配机制的关键。在本文中，我们提出了一种新的机器学习方法，利用先验（结构）知识的代理人的我们的贡献适用于任何组合分配问题。然而，我们提出了我们的算法在一个CA的上下文中，具体地，简化符号和是-原因存在良好的研究偏好发电机CA我们的MVNN实验在频谱拍卖域。我们的研究结果表明，MVNNs im-我们可以用来做实验评估对于具有一般估值的CA，Nisan和Segal[2006]证明了预测性能，它们在拍卖中产生了最先进的分配效率，并且它们还减少了WDP的运行时间 。 我 们 的 代 码 可 以 在 GitHub 上 找 到 ：https://github.com/marketdesignresearch/MVNN。1引言许多重要的经济问题涉及到多个不可分的项目的组合分配给多个代理人。在金钱领域，突出的例子包括组合拍卖（CA）和组合交易所（CE）。在CA中，异构项目在一组投标人之间分配，例如用于频谱许可证的销售[Cramton，2013]。在CE中，一组物品在多个代理之间分配，这些代理可以同时是卖家和买家，*本文是Weissteiner等人[2022 a]在IJCAI[2]这些作者对本文的贡献相当。已经表明，指数通信的数量，在最坏的情况下需要物品的最优分配来找到物品对投标人的最优分配，即，以确保充分的效率。因此，对于一般的估值，实际的CA不能在大的域中提供效率保证。在实践中，采用迭代组合拍卖（ICA），拍卖师与投标人进行多轮互动，获取有限的信息量，旨在找到一个高效的分配。ICA被广泛使用;例如，出售建造海上风电场的许可证[Ausubel和Cramton，2011年]。 通过组合时钟拍卖（CCA）提供频谱许可证[Ausubel et al. ，2006年]产生了超过200亿美元的总收入[Ausubel和Baranov，2017年]。因此，将这种真实世界的ICA的效率仅提高1%，就可以转化为数百万美元的货币收益1.1基于ML的拍卖设计近年来，研究人员已经成功地将机器学习（ML）算法集成到CA的设计中，以提高CA的性能。arXiv：2109.15117v4 [cs.GT] 2022年8月+v：mala2277获取更多论文2∈--∈ XX →∈∈ X关于我们+−Σ∈ Fa∈ Xn：. 我们假设出价-i∈Nvi（ ai）−pi+i∈Nvi（ai）.我们让∈宣传他们的表现。 杜廷等 [2019]和Rahme等人。[2021]使用神经网络（NN）从数据中学习整个自动化机制，遵循自动化机制设计范式。 Brero等人 [2019]研究了使用概率价格更新的贝叶斯ICA，以实现更快的收敛到有效的分配。与本文最相关的是Brero等人的工作。 [2018; 2021]，他开发了一种基于值查询的ICA，其效率甚至高于广泛使用的CCA。在后续工作中，Weissteiner和Seuken[2020]通过将神经网络（NN）集成到其机制中来扩展其工作，并可以进一步提高效率。最后，Weissteiner等人。[2022 b]使用傅里叶变换（FT）来利用偏好计算中值函数稀疏性的不同概念然而，尽管取得了这些进展，它仍然是一个挑战性的问题，找到有效的分配，同时保持招标成本低。即使是国家的最先进的approaches遭受显着的效率损失，突出需要更好的偏好启发算法。我们在本文中表明，这些限制可以部分地解释，由于使用穷人，非信息ML算法，它要么不包括重要的先验领域知识或投标人的价值函数的限制性假设 Brero等人[2018; 2021] 使 用 了 具 有 二 次 核 的 支 持 向 量 回 归（SVR），其只能学习项目之间的双向交互，并且不能解释投标人价值函数的重要单调性。虽然Weissteiner和Seuken[2020]使用的全连接前馈神经网络更具表达力，但它们也不能解释这种单张性。特别是在只有少量数据点的情况下（这是市场机制的标准，因为优惠的吸引成本很高），这可能会造成重大的效率损失。在过去的十年中，ML的主要成功是通过专门的NN架构（例如卷积神经网络）取得的，这些架构结合了特定领 域 的 先 验 知 识 以 提 高 泛 化 能 力 [Bronstein et al. ，2017]。在本文中，我们遵循相同的范式，将单调偏好的先验知识纳入NN体系结构，以提高泛化能力，这是一个功能良好的偏好启发算法的关键先前已经提出了将单调性纳入NN然而，对于这些架构，不知道如何基于NN的获胜者确定问题（WDP）可以快速解决，或者它们有其他限制。Sill[1998]只提出了一种违反规范化属性的浅层架构。You等人 [2017]提出了一种非标准架构，其中不知道WDP的相应MILP公式是否可以制定为一个简洁的MILP，从而迅速解决和（ii）我们提出了一个通用的全连接前馈架构，任意数量的隐藏层，可以有效地训练。1.2我们的贡献我们做出以下贡献：1. 我们介绍了单调值神经网络（MVNNs），这是一类新的NN，具有精心选择的激活函数（bReLU）和对参数的强制约束，以便它们被归一化并满足单调性（第3节）。这些MVNN特别适合于在经济环境中建模单调（组合）值2. 在 技术 层 面 上， 我 们 提供 了 以 下两 个 定 理（3.1节）：首先，我们证明了MVNN在单调和归一化组合值函数类中是泛函数，即，可以将具有任意复杂可替换性和互补性的任何值函数精确地表示为MVNN。其次，我们将展示如何将基于MVNN的WDP制定为MILP，这是有效计算最优分配的关键。3. 我们在四个不同的频谱CA域中实验评估了MVNN与NN的学习性能，并表明MVNN在建模投标人的组合价值函数方面明显更好4. 最后，我们通过实验研究了MVNNs与普通NN集成到现有的基于ML的ICA（MLCA）中时的性能，并将其与Weissteiner等人的基于FT的方法进行了比较。[2022 b]。我们表明，MVNN导致的效率损失大大小于现有的最先进的机制（第5节）。2预赛在这一节中，我们提出了我们的正式模型，并审查基于ML的ICA由Brero等人。 [2021年]。2.1ICA的形式化模型我们考虑一个CA与n投标人和m不可分割的项目。设N=1，. . .，n且M= 1，. . .、m分别表示投标人和项目的集合。 我们用x=0，1 m表示一个表示为指示向量的项丛，其中x j=1当且仅当项jM包含在x中.投标人对捆绑包的真实偏好由其（私有）价值函数v i：R +，i N表示，即，Vi（x）表示投标人i由 =（a1，. . . ..艾恩斯We表示可行分配的集合，F=通过表示目标函数作为NN的积分，因此WDP将导致计算上不可行的MILP。 Liu等人 [2020]训练具有连续更高正则化的NN，直到基于MILP的DER 付款PRn，u i（a，p）= v i（a i）p i. 这意味着（真正的）社会分配a的福利V（a）等于所有投标者的价值之和，即，V（a）i=i∈Nui（ai，pi）+u拍卖者r（p）=∈∈F再训练和验证导致高计算成本。相反，我们的方法特别适合于组合分配，因为（i）我们基于NN的WDPaargmaxaV（a）是社会福利最大化，即，高效的分配。任何分配a的效率都可以用V（a）/V（a）来衡量。在计算上是可行的。Wehenkel和Louppe[2019]i∈Naij≤1，验证过程保证单调性。重复i∈Npi=+v：mala2277获取更多论文3X →^∈∈∈|+联系我们^∈||| ≤A∈一V我一我.Σ我我l=1新argmaxa∈F我 我∈ICA机制定义了投标人如何与拍卖人互动，以及如何确定最终的分配和付款。 我们表示一个投标人的（可能不真实的） 报告价值功能的v i：R +。在这篇论文中，我们考虑ICA，要求投标人迭代地报告他们的价值vi（x）为特定的bundlesx所选择的机制。一组LN个报告的有效值对投标人i表示为R=. x（l），v（x（l））L，x（l）∈X.这一点很重要，因为操纵的机会可能会降低效率。与所有已部署的频谱拍卖（包括CCA[Ausubel和Baranov，2017]）一样，MLCA并非防策略性的。然而，Brero etal. [2021]认为，它在实践中有良好的激励;并给出两个额外的假设，投标如实是一个事后纳什均衡MLCA。他们的分析适用于使用任何ML算法的MLCA，因此也适用于基于MVNN的MLCA。我们提供更详细的激励分析设R =（R1，. . . ，Rn）表示所报告的束的元组。从所有投标人获得的值对我们定义报告的社会福利分配一个给定的R为V（aR）：=iN：（ai，vi（ai））Rivi（ai），其中（ai，vi（ai）） Ri确保只有报告的捆绑包的值有贡献。最后一次行动-附录B。3单调值神经网络在组合分配问题中，值函数是时间分配a<$R∈F和支付p（R）∈Rn是连续的，用于为每个代理仅基于引出的报告R。更正式地，在报告R中的最优分配a∈R∈Fg i被定义为：项目（vi：0，1mR+）。然而，虽然束空间随着项目的数量呈指数增长，但代理一个人argmaxV（a R）.（一）a∈F值函数通常表现出可被开发的有用结构。一个常见的假设是单调性：(M) 单调性（由于拍卖人通常只能向每个出价人i查询有限数量的捆绑包R i，Qmax（例如，Qmax=100），该机制需要一个复杂的偏好获取算法，目标是在有限的值查询数下找到一个高效的最终分配算法。2.2 一种机器学习驱动的ICA我们现在回顾Brero等人的机器学习驱动的组合拍卖（MLCA）。 [2021年]。感兴趣的读者可参考附录A，其中我们详细介绍了MLCA。MLCA循环进行，直到达到每个出价者的最大值查询数量Qmax。在每一轮中，在投标人的报告Ri上针对每个投标人i N训练通用ML算法i。接下来，MLCA产生新的价值F 或 A ， B∈2M ： 若 A<$B ， 则 v<$i （ A ） ≤v<$i（B）成立. [1]该属性在许多市场领域都得到了满足。例如，在许多CA中，投标人可以自由处置不需要的物品;在组合课程分配中，学生可以放弃他们被分配的课程然而，之前关于基于ML的市场设计的工作[Weissteiner 和 Seuken ， 2020; Weissteiner 等 人 ，2019]。，2022b; Brero et al. ，2021]没有考虑到这一特性，这对性能产生了负面影响（见第4节和第5节）。为了便于说明，我们还假设值函数是归一化的：(N) 标准化（vi（）=vi（（0，. . . ，0））：=0查询qnew=（qnew）n，其中qnew∈ X \Ri通过求解a请注意，此属性不是我们的方法所必需的，我基于ML的WDPqi=1∈iA（a）。i∈N这个想法是这样的：如果我是好的代理模-els的投标人V：={vi：X→R+|满足（N）和（M）}（2）有效分配的良好代理，从而为拍卖人提供有价值的信息。此外，在现实世界的MLCA中，投标人这减轻了投标人没有被要求正确查询的风险。在我们的实验中，MLCA实现了已经国家的最先进的结果，而不使用任何所有满足正规化和单调性的值函数的集合。接下来，我们介绍了单调值神经网络（MVNNs），并证明了它们跨越整个集合。因此，MVNN特别适合于具有单调值函数的所有应用。定义1（MVNN）。 A MVNNNθ：X →R+（投标人）（数学上额外的在每轮结束时，MLCA从所有投标者接收针对新生成的查询q_new的报告R_new，并且更新总体引出的报告R。当达到Qmax时，MLCA计算使所报告的社会福利最大化的分配aR（参见等式（1）），并确定VCG基于报告值的付款p（R）（见附录定义B.1）。注1（IR、无赤字和MLCA的激励措施）。 Brero等人[2021]表明，MLCA满足个体理性（IR）和无缺陷，任何ML算法i。此外，他们还研究了MLCA的激励特性，i∈N定义为Nθ（x）= Wi，Ki<$0，t. . . t（Wi，1x + bi，1）. . . 、（3）• Ki+1∈N是层数（Ki−1个隐藏层），• t是我们的MVNN特异性激活函数，t>0，我们称之为bounded ReLU（bReLU）：20，t（z）：= min（t，max（0，z））（4）[1]我们在这里稍微滥用了符号，使用集合而不是它们对应可以容易地被适配为任何其他固定值，或者被适配为学习参数。在下文中，我们用+v：mala2277获取更多论文4的指示向量作为vi的函数。2 bReLU也已用于视觉模式识别问题，以提高训练稳定性（见Liew et al. [2016]）。+v：mala2277获取更多论文5k=1k=1×≤··- - −- - −34我，V=N：W≥0，b≤ 0。 （五）12i，k，j，lj，l0≤ηi，k≤（1−yi，k）·Li，k武里武里Σ我i，ki，k• Wi：=（Wi，k）Ki其中Wi，k≥0且bi：=（bi，k）Ki与MVNN捕捉互补性、替代性和非替代性。b i，k0表示维度di，kdi，k−1和di，k的非负权重和非正偏置的元组，其参数存储在θ=（W i，b i）中。3关于MVNN的实现细节，我们参考附录C. 6。除非明确说明，否则我们从现在开始考虑bReLU的截止值t=1，即，（z）：=接下来，我们讨论bReLU的选择bReLU的选择（i）对权重和偏置的约束强制MVNN的单调性（实际上对于任何单依赖项。组合分配机制的一个关键步骤是找到社会福利最大化的 分 配 ， 即 ， 赢 家 决 定 问 题 （ Winner DeterminationProblem，WDP）为了在这样的机制中使用MVNN，我们需要能够有效地解决基于MVNN的WDP。为此，我们提出了一种基于MVNN的WDP的MILP关键思想是将bReLU（z）重写为最大的）一、max（0，z））并编码为每个投标者i、隐藏层k和神经元j都是max（，）op。具有两个二元决策变量yi，k，µi，k的生成器。 一是音调激活）。（2）对于普遍性（见定理1），我们需要J J显示如何编码单个有界单调非常数激活，即，对于Re-LU和我们的约束，不能表示可替换性。(iii)对于MILP（见定理2），我们需要分段线性激活（例如，对于S形，我们不能形成MILP）。综上所述，bReLU是最简单的有界、单调、非常数、分段线性激活（有关详细讨论，请参见附录注释C.2和C.3备注2. 对于期望值函数“几乎”（但不完全）单调的应用MVNN的隐藏层多重线性约束。我们在附录C.4中提供了证明。引理2. 固定投标人i∈N，设k∈ {1，. . .，K i−1}，并将第k层的预激活输出表示为 oi ， k：=Wi ， kzi ，k−1+bi，k，其中Wi，k∈Rdi，k×di，k−1，bi，k∈Rdi，k。然后，第k层的输出z i，k：=max（o i，k）=min（1，max（0，o i，k））=max（1，η i，k），其中η i，k：=max（0，o i，k）可以由以下线性约束等效地表示：通过经由正则化实现对权重和偏置的约束，例如，max（0，−W i，k）.这导致oi，k≤ηi，k≤o+y i，k·L1（6）（七）软MVNN，可以模拟一些如果数据证据很强，3.1理论分析和MILP公式接下来，我们提供了MVNN的理论分析，并提出了基于MVNN的WDP的MILP公式。2ηi，k−μi，k·Li，k≤zi，k≤ηi，k（8）1−（1−µi，k）·Li，k≤zi，k≤1（9）yi，k∈ {0，1}di，k，μi，k∈ {0，1}di，k， （10）引理1. 设N θ：X → R+是定义1中的MVNN。i，ki，ki，ki，k其中L1，L2，L3，L4∈R+是足够大的常数则对所有Wi ≥ 0且bi≤ 0，N（W，b）∈ V成立.我们在附录C.1中给出了引理1的证明。接下来，我们陈述关于MVNN的主要定理。对于相应的大M约束。4最后，我们制定了MVNN为基础的WDP作为MILP。定理2（MILP）.基于MVNN的WDPTheo r em1（Univ ersality）. 一个y值函数v∈i：X→R+MaxN（ai）可以等价地表示为：（W，b）满足（N）和（M）的，可以精确地表示为我a∈F我我i∈N i定义1中的MVNNNθ，即，（W i，bi） iii我们给出了Ap中定理1的构造性证明以下MILP：5Maxa∈F，zi，k，μi，k，ηi，k，yi，k.i∈NWi，Kizi，Ki−1（十一）C.3.在 的 证明， 我们 考虑 任意（vi（x））x∈Xθ∈V，我们为它构造一个两个维度为[m，2m−1，2m−1，1]的隐藏层MVNNNi，S.T. 对于i ∈ N，k ∈ {1，. . . ，Ki− 1}zi，0=ai（十二）参数θ=（Wi，bi）使得Nθ（x）=v<$i（x）<$x∈X .Wi，kzi，k−1+bi，k≤ηi，k（13）请注意，对于q个查询，总是可以构造大小为[m，q，q，1]的MVNN，它完全适合q个数据点（参见附录推论C.1）。因此，最糟糕的-ηi，k≤Wi，kzi，k−1+bi，k+yi，k·Li，k0≤ηi，k≤（1−yi，k）·Li，k（十四+v：mala2277获取更多论文6/34/）（十五）情况所需的体系结构大小仅随查询的数量线性增长。在我们的实验中，我们已经实现了非常好的性能，甚至更小的架构。附录中的示例C.1很好地说明了3我们将线性读出映射应用于最后一个隐藏层，即，没有Ki0，t和bi，Ki：= 0。通过设置bi，Ki= 0且trainable=False，MVNN可以对归一化属性中除零之外的任何其他值进行建模。通过不限制bi，k≤0并设置bi，Ki0，ηi，k−μi，k·Li，k≤zi，k≤ηi，k（16）1−（1−µi，k）·Li，k≤zi，k≤1（17）yi，k∈ {0，1}di，k，μi，k∈ {0，1}di，k（18）4为了解释bReLU中的一般截止值t=1，需要通过用t替换最左边和最右边的1来调整（9）。5为了说明bReLU中的一般截止值t/= 1，需要trainable=True也可以学习空bundle的值通过用t替换最左边和最右边的1来调整（17）。+v：mala2277获取更多论文7证据证明如下迭代地应用引理2为每个投标人和所有她各自的隐藏MVNN层。事实1. 人们可以通过收紧每个神经元的边界来显着减少MILP的求解时间。在Ap-penetration C.5中，我们通过区间算法（IA）提出了约束收紧[Tjeng et al. ，2019]用于MVNN。对于普通的ReLU NN，这些IA边界并不严格，并且以计算高效的方式计算更严格的边界非常困难。相比之下，MVNN-IA边界总是完美紧的，因为它们的编码单调性。神经元的上界和下界是神经元输出的输入值（1，. . .，1）和（0，. . .，0）。 这是一与普通（ReLU）NN相比，MVNN具有很大的优势。注释3（MVNN作为偏好生成器）。为了从实验上评估一个新机制，需要生成许多不同的可能值函数。偏好生成器，如频谱拍卖测试套件[Weiss et al. ，2017]被精心设计以捕获频谱拍卖的基本属性，但它们并不适用于每种应用。代替使用这样的域特定偏好生成器，还可以使用具有随机初始化权重的MVNN来生成可能的值函数。随机MVNN的一个优点是它们是通用的（参见定理1），因此具有足够丰富的多样性，可以任意采样任何可能的单调值函数在模拟投标人时，我们遵循先前的工作（例如，[Breroetal. ，2021]）并假设真实的出价（即，vi=vi）。有关我们如何收集数据以及训练/验证/测试划分的详细信息，请参见附录D.1。HPO为了有效地优化超参数并公平地比较MVNN和普通NN，以便在每个SATS域的不同实例上进行最佳泛化，我们将超参数优化（HPO）问题框定为算法配置问题，并使用 完善的基于序 列模型的 算法配置 （SMAC ）[Hutter etal. ，2011]。SMAC快速丢弃在少数SATS实例上表现不佳的超参数，并通过贝叶斯优化提出更有前途的超参数它是足够灵活的参数化神经网络，因为它自然处理的分类，整数和浮点超参数的混合。有关设置（包括超参数范围）的更多详细信息，请参见附录D.2。4.2 预测性能结果为了便于说明，我们只给出了我们的MVNN（以下称为MVNN）的MVNN-RELU-PROJECTED其他MVNN实现的结果可以在附录D.3中找到。在表1中，我们比较了HPO在测试数据上发现的不同训练数据量（T）的获胜模型的预测性能我们看到，与普通的复杂的可替代性和互补性（分布，补充物和互补物的分配可以通过截止值T来控制，其中T越小/越大，可替代性/互补性越大这些类型的生成测试床变得越来越重要，以避免在特定仿真引擎和/或真实数据集上过度拟合[Osband等人，，2021]。4MVNN的预测性能在本节中，我们表明，在所有考虑的CA域中，MVNN在捕获投标人的复杂值函数方面明显优于R2↑KT↑DOMAINTBIDDERMVNNNNMVNNNNGSVM 10处的NR例如20NATREG50NATREG0.686±0.0610.618±0.0680.923±0.0160.940±0.0180.992±0.0010.997±0.0010.534±0.0400.668±0.0270.633±0.0380.849±0.0170.882±0.0200.962±0.0030.974±0.0020.583±0.0210.557±0.0330.752±0.0290.815±0.0210.953±0.0030.953±0.0030.504±0.0620.818±0.0320.880±0.0220.988±0.0010.988±0.001LSVM 10处的NR例如50NATREG100 NATREG0.248±0.0690.563±0.0490.616±0.0200.921±0.0150.677±0.0140.965±0.0100.137±0.0310.348±0.0670.199±0.0310.872±0.0120.396±0.0330.936±0.0100.693 0.011 ± 0.0110.710±0.0230.605±0.0310.753±0.0090.860±0.0170.813±0.0050.918±0.0150.504±0.0250.678±0.0350.812±0.0130.706±0.0180.857±0.012SRVM 10H.F.0.5380.044-2.123±0.2680.626 0.020 ± 0.0200.607±0.012LO0.381 ±0.0450.267 ±0.0420.559 ±0.0300.489±0.032N AT0.389 ±0.0630.341±0.0380.560 ±0.0260.535±0.0124.1实验设置-预测性能在我们的实验中，我们使用模拟数据R例如50H.F.LONATREG0.422±0.0510.860±0.0150.895±0.0200.988±0.0040.989±0.0040.372±0.0360.773±0.0340.588±0.0310.828±0.0150.872±0.0470.562±0.0230.853±0.0130.902±0.0000.918±0.0050.931±0.0040.544±0.0140.803±0.0200.771±0.0300.801±0.0090.823±0.022来自频谱拍卖测试套件（SATS）版本0.7.0 [Weiss etal. ，2017]。我们考虑以下四个领域：• 全球协同价值模型（GSVM）[Goeree和Holt，2010]有18个项目，6个区域和1个国家投标人。• 局部协同价值模型（LSVM）[Scheffel et al. ，2012年]有18个项目，5个区域和1个国家投标人。互补性源于物品的空间接近性。100 H.F.LONATREGMRVM10LONATREG100 LOCALNATREG300 LOCAL0.911±0.0080.948±0.0140.998±0.0000.996±0.0010.182±0.0450.036±0.0850.831±0.0230.778±0.0220.832±0.0280.944±0.0060.849±0.0110.723±0.0050.913±0.0080.945±0.004-0.556±1.355-0.048±0.0920.493±0.0270.560±0.0190.447±0.0530.871±0.0090.908±0.0060.903±0.0000.952±0.0030.948±0.0210.365±0.0180.322±0.0220.786±0.0190.726±0.0140.779±0.0270.883±0.0100.896±0.0060.900±0.0020.841±0.0080.895±0.0120.200±0.0150.414±0.0080.255±0.0380.545±0.0120.581±0.0100.572±0.0180.819±0.009[]NAT0.868±0.0160.855±0.0290.814±0.0090.808±0.013• 单区域价值模型（SRVM）Weiss et al. ，二〇一七年REG0.917 ±0.0170.847 ±0.0100.851 ±0.0190.809±0.012有29个项目和7个投标人（分类为本地，高频区域或国家）和模型的大型英国4G频谱拍卖。• 多区域价值模型（MRVM）[Weiss et al. ，2017年]有98个项目和10个投标人（本地，区域或国家）和模型大型加拿大4G频谱拍卖。表1：通过R平方（R2）和Kendall tau（KT）测量的预测性能，在四个SATS域中具有95% -CI，具有相应的投标人类型：高频（H.F.），地方（LO）、地区（REG）和国家（NAT），平均超过30个拍卖实例。MVNN和普通NN都是在T上训练的，并在209 715−T随机束上进行评估。获胜者以灰色标记。-0.055 0.058 ± 0.058-0.018 0.050 ± 0.0500.262±0.017+v：mala2277获取更多论文808.16 ±0.4100.23 ±0.0600.70 ±0.4000.00±0.0000.00 ±0.00Σ+∈∈∈ F−E效率损耗（% ↓T-T测试）为效率：DOMAINQMAXMVNN NN FT RSH0：µNN≤µMVNNH0：µFT≤µMVNNGSVM 100LSVM 100SRVM 100MRVM 10002.91 ±1.4401.13 ±0.2209.05 ±0.5301.77±0.9630.34±1.61pVAL=3e−601.54±0.6531.73± 2.15pVAL=2e−03 pVAL=5e−300.72±0.1628.56± 1.74pVAL=5e−10 pVAL=2e−810.37±0.5748.79± 1.13pVAL=9e−03 pVAL=1e−7表2：MVNN与普通NN、傅立叶变换（FT）基准和随机搜索（RS）的效率损失所示为50个CA实例的测试集的平均值和95%CI基于显著性水平为1%的（配对）t检验的获胜者以灰色标记效率损失，即， 1V（aR）/V（a）和相关的Re地点iNp（R）i/V（a），分配aR和付款p（R）Rn由MLCA在引发报告R时确定。由于MLCA的单次评估的运行时间较长，我们执行受限的HPO，其对于每个域仅使用三个训练数据量T的预测性能实验（表1）的优胜者。这是一个合理的选择，因为在预测性能上我们针对投标人的价值优化了泛化性能图1：SRVM中MVNN与普通NN的预测性能标识以灰色显示。NN、MVNN在R平方R2方面提供了显著更好的拟合，以及更好的Kendall Tau秩相关性KT（即，更好的顺序排序）。因此，在MVNN中强制执行单调性属性显著提高了学习性能。图1通过提供高度非单峰SRVM的预测性能的可视化比较来说明我们的发现6我们看到MVNN完全符合训练数据（蓝色十字），尽管HPO只优化了验证数据的泛化性能。这强烈表明MVNN对应于更现实的先验，因为对于现实的先验，[这也是MLCA的关键功能。对于每个域，我们使用Qinit=40个初始随机查询，并将查询预算设置为Qmax=100。我们在中间迭代中终止MLCA，如果它已经找到有效的分配（即，效率损失为0）。5.2效率结果在表2中，我们给出了基于MVNN的MLCA和基于NN的MLCA的效率结果我们关注的是效率而不是收入，因为频谱拍卖是政府运营的拍卖，有一个最大限度地提高效率而不是收入的日期[Cramton，2013]。在附录E.2和E.3中，我们还介绍并讨论了详细的收入结果。对于每个域，我们提出了相应的结果，最好的MVNN和NN之间的三个现任ob-在无噪声设置中拟合训练数据Heiss et al. ，二零二一、从预测性能实验中得出。我们提案D.2.a]。相比之下，HPO为普通NN选择了超参数，这导致训练数据的拟合较差（否则对看不见的数据的泛化将更差）。此外，普通NN在频率较低的较低值和较高值丛上显示出特别差的拟合5MVNN驱动的迭代CA为了评估MVNN在组合市场机制中使用时的性能，我们将MVNN集成到MLCA中（见2.2节），产生了MVNN驱动的迭代CA。在本节中，我们将我们的基于MVNN的MLCA的经济效率与预先提出的基于NN的MLCA进行比较。为了求解MLCA中基于MVNN的WDP，我们使用定理2中的MILP。5.1实验设置-MLCA为了生成合成CA实例，我们使用与第4节相同的四个SATS域。SATS还使我们能够获得真正的最优分配，我们用它来衡量[6]我们在附录D.3中为其他领域和投标人类型提供了相应的图;结果在定性上是相似的。在附录E.2中列出了所有三个现任者的结果。总的来说，我们看到MVNN（表1）更好的预测性能转化为MLCA 中 更 小 的 效 率 损 失 。 在 LSVM 和 SRVM 中 ，MVNN的性能明显优于NN，效率损失降低了四倍以上。在MRVM中，MVNN考虑到2014年加拿大4G拍卖的总收入约为50亿美元[Ausubel和Baranov，2017年]，MRVM中1%的效率损失可以转化为约5000万美元的福利收益最后，在最简单的领域GSVM中，投标人作为进一 步 的 基 线 ， 我 们 评 估 傅 立 叶 变 换 （ FT ） 拍 卖[Weissteiner etal. ，2022 b]使用他们提出的最优超参数和随机搜索 （RS ）。我们不 与SVR 进行比较[Breroetal. ，2021]，因为它们在[Weissteiner和Seuken，2020]中已经被普通NN超越。我们观察到RS会导致30-50%的效率损失，这此外，我们看到MVNN在所有领域的表现都明显优于FT。+v：mala2277获取更多论文910110010−110−210−3GSVM101LSVM10−40101SRVM1004030MRVM10040 55 70 85100数量的查询2010140 55 70 85100数量的查询图3：MLCA中MVNN与普通NN在10个LSVM实例上的MILP运行时（200秒的时间限制），用于选择架构。图2：MVNN与普通NN的MLCA效率损失路径。显示的是50个拍卖实例的95%CI平均值。在图2中，我们给出了MVNN与NN的效率损失路径后悔曲线）对应于表2。我们看到，在LSVM和SRVM中，MVNN对于每个查询数量都导致较小的（平均）效率损失在MRVM中，对于50个或更多的查询也是如此。在GSVM中，网络在每一个实例中都没有效率损失，56个问题。由于在现实世界的CA中，单个查询的成本可能非常高，因此请求很少的查询是有意义的图2示出了MVNN在具有少量查询的设置中也始终优于普通NN（即，Qmax）5.3MILP分析当将MVNN集成到MLCA或另一种迭代组合分配机制中时，需要在一次完整运行中多次求解因此，在这种机制中集成MVNN时的关键计算挑战是有效地解决基于MVNN的WDP。在定理2中，我们已经展示了如何将基于MVNN的WDP编码为简洁的MILP，这可以有效地然而，由于bReLU激活功能，即，两个截止值分别为0和t>0时，基于MVNN的MILP具有两倍的双nary变量（yi，k和µi，k）比使用ReLU的普通NN的MILP编码更简单[Weissteiner和Seuken，2020]。图3显示了所选架构的MVNN与普通ReLU NN的MILP运行时。我们观察到两个效果：第一，即使MVNN为基础的MILP有两倍的二进制变量的数量，他们可以解决的速度比普通的NN为基础的MILP的所有架构。第二，结构越深或神经元越多，这种差异就越大。对这两种效应的一种可能的解释是，MVNN比普通NN更规则（由于它们的单调性），因此更容易优化。六、结论在本文中，我们介绍了MVNNs，一类新的神经网络，专门设计用于模型归一化和单调值函数的组合分配问题。我们已经实验评估了MVNN在四个组合频谱拍卖域中的性能，表明MVNN在预测性能、经济效率和运行时间方面优于普通NN。总的来说，我们的实验表明，MVNN是目前最好的组合分配偏好诱导模型因此，将重要的结构知识纳入ML算法在组合分配中起着重要的作用MVNN使我们能够将信息先验纳入市场机制。未来的工作可以使用这种信息先验并增强现有机制（例如，MLCA）也使用后验估计在一个更有原则的方式，而不仅仅是平均预测。例如，可以将ICA框架为（组合）贝叶斯优化任务，并整合后验不确定性的定义明确的概念以促进探索[Heiss et al. ，2021]。最后，这将是有趣的，也评估MVNN在其他组合分配问题，如课程分配的性能致谢我们感谢匿名评论者提供的有用意见。本文是一个项目的一部分，该项目已获得欧洲研究委员会（ERC）的资助，根据欧盟805542）。引用[Ausubel和Baranov，2017] Lawrence M Ausubel和OlegBaranov。组合时钟拍卖实用指南Economic Journal，127（605）：F334-F350，2017. 一、三、六[Ausubel and Cramton，2011] Lawrence Ausubel and PeterCramton.风权拍卖设计。海洋能源管理、监管和能源局报告，2011年。1[Ausubel et a