福利最大化的多维动态定价

ACM Transactions on Economics and Computation，卷。号81.第六条。出版日期：2020年4月福利最大化的多维动态定价Aaron Roth，美国宾夕法尼亚大学ALEKSANDRS SLIVKINS，美国微软研究院JONATHAN ULLMAN，美国东北大学STEVENWU，美国明尼苏达大学我们研究的问题，卖方动态定价d不同类型的不可分割的商品，当面对的在线到达的单位需求的买家独立绘制从一个未知的分布。这些商品的供应并不有限，但只能以有限的速度生产，而且生产成本很卖方只观察每天购买的一捆货物，而不观察买方我们的主要结果是一个动态的定价算法优化福利（包括卖方我们能够做到这一点，尽管事实上，（i）价格反应函数是不连续的，甚至它的分数松弛是一个非凹函数的价格，（ii）福利是不可观察的卖方。我们得出这个结果作为一个应用程序的一般技术优化福利可分割的商品，这是独立的利益。当购买者具有强凹的、Hölder连续的价值函数时，我们给出了一个一般的多项式时间动态定价方法.我们能够将这一技术应用于单位需求购买者的设定，尽管在该设定中商品是不可分的，并且单位需求估值的自然分数松弛不是强凹的。为了应用我们的一般技术，我们引入了一种新的价格随机化过程，其效果是隐含地诱导买家用一个强凹函数来“正则化”他们的估值。最后，我们还将我们的结果扩展到一个有限的供应设置，其中每种商品的供应无法补充。CCS概念：·计算理论→数学机制设计;在线学习理论;附加关键词和短语：多维动态定价，有限供给，在线学习，凸优化，显示偏好ACM参考格式：Aaron Roth，Aleksandrs Slivkins，Jonathan Ullman，and Zhiwei Steven Wu.2020年。福利最大化的多维ACM跨经济计算8，1，第6条（2020年4月），35页。https://doi.org/10.1145/33815276这项工作得到了NSF资助号CNS-1253345、斯隆基金会奖学金和DARPA资助的部分支持。作者地址：A.罗斯，宾夕法尼亚大学，3401核桃街，费城，宾夕法尼亚州，19104，美国;电子邮件：aaroth@cis.upenn.edu; A。Slivkins，Microsoft Research，641 6 th Ave，New York，NY 10011;电子邮件：slivkins@microsoft.com;J. Ullman，东北大学，805 Columbus Ave，Boston，MA 02118，USA;电子邮件：jullman@ccs.neu.edu; Z. S.吴，明尼苏达大学，200联合街东南，明尼阿波利斯，明尼苏达州55455;电子邮件：zsw@ umn. edu。允许免费制作本作品的全部或部分的数字或硬拷贝，以供个人或课堂使用，前提是制作或分发副本的目的不是为了盈利或商业利益，并且副本的第一页上有本声明和完整的引用。必须尊重作者以外的其他人拥有的本作品组件的版权。允许使用学分进行摘要。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定许可和/或付费。从permissions@acm.org请求权限。© 2020版权归所有者/作者所有。授权给ACM的出版权。2167-8375/2020/04-ART6 $15.00https://doi.org/10.1145/3381527ACM Transactions on Economics and Computation，卷。号81.第六条。出版日期：2020年4月第六A. Roth等人1介绍考虑一个卖家通过动态定价反复分配大量商品的问题每种商品的价格都是有限的，每单位生产或采购成本都是有限的。在每一轮中，卖家可以动态地为每种商品设置价格，在每一轮中，买家到达并选择要购买的商品每个买家都有一个未知的价值函数定义（一般）在捆绑的货物和准线性效用，选择购买哪一个项目，以优化他的效用函数给定的价格。卖方观察买方的购买决定，即，买方的显示偏好-但不是买方买方卖方的目标是优化社会福利：买方对所购商品的预期估价减去其生产成本。尽管收入或利润是动态定价研究中更常见的目标，但社会福利往往是公共实体定价和分配的更自然的目标。例如，一个分配农业剩余或粮食捐赠的政府机构主要希望通过其分配来最大化福利。解决这个问题的第一个诱人的尝试是简单地将每种商品的价格设定为等于其生产成本，如果买家购买的商品没有其他限制，这确实会使社会福利然而，由于将价格设定在更现实的情况下，每种商品的生产和再供应速度都受到限制因此，我们研究的福利最大化问题中，我们施加了额外的约束，预期的捆绑购买（在期望超过买方的抽奖）在于在一个有界的集合。由于这类约束了购买者，因此将价格设定为等于成本是失败的，这个问题需要一个非平凡的解决方案。尽管这种由于买方的分布是未知的，卖方不能直接计算使社会福利最优化的价格相反，她面临着一个学习问题：她可以随着时间的推移尝试不同的价格，观察从分布中随机抽取的买家的反应，并尝试学习最佳价格向量。更正式地说，我们的目标是使用少量的回合来学习一个几乎优化预期社会福利的价格向量我们希望算法的保证，从本质上讲，我们正在研究一个福利优化版本的著名的动态定价问题，也被称为学习和赚取，与d> 1的商品出售。（之前关于动态定价的工作主要集中在利润最大化上。在一个非常高的水平上，提出的主要挑战是学习价格响应函数，即，该函数将价格映射到预期购买的捆绑包，然后在福利方面对其进行优化。此外，这是一个高维函数（对于大d），因此必须克服维数灾难。非贝叶斯动态定价的先前工作（例如，参考文献[4，10，11，14，19，25，33]）通过对价格反应函数本身做出强有力的假设来应对这一挑战。典型假设包括Lipschitzness[10，11，33]（允许在低维问题中进行离散化），特别是对于高维问题，线性[19，25]或非线性[4，10，33]。1、假设[1]先前的工作没有对估值或需求曲线的形状做出假设，要么仅限于销售单一商品（d=1）[4，26]，要么受到维数灾难的影响，并提供相对于离散价格而不是所有价格的性能保证[5]。多维动态定价第六章：ACM Transactions on Economics and Computation，卷。号81.第六条。出版日期：2020年4月+>0个+这类措施没有得到微观经济基础的充分支持。事实上，自然界的...对买方估价的影响不一定会导致这些物业的价格反应函数。在这篇文章中，我们追求一种不同的方法，它建立在更强大的微观经济基础之上：我们直接对估值函数的形式做出假设（而不对估值函数的分布做出假设），并表明我们可以使用由此产生的价格反应函数。尽管我们的问题是高维的，并且由我们的假设得出的价格响应函数不是凹的，但情况仍然如此。我们还面临着一个额外的挑战：与利润不同，福利是不可观察的，我们可以观察购买的捆绑产品，但不能观察买家对该捆绑产品的估值。尽管如此，我们设计的算法，找到一个接近最优的价格向量福利，在一些回合，是多项式的d和精度参数。（然而，例如，基于价格响应函数的离散化和Lipschitzness的朴素解决方案需要d的指数轮数。我们的研究结果也扩展到有限供应设置。1.1我们的贡献我们的主要结果解决了当买方是单位需求时，或者，当卖方只允许每个客户购买单一商品时，在不可分割的商品设置的问题令人惊讶的是，不需要其他假设！此外，我们给出了一个一般性的结果设置的可分商品的估值函数在一定的假设。事实上，我们展示了这个一般结果 可以被利用来产生具有单位需求估值的不可分割商品的结果。两种设置的工作方式如下。有D货。在每一轮中，价格被设定，一个买家到达并从一组可行的捆绑中购买她最喜欢的捆绑卖方在每次销售中产生生产或采购成本，这些成本在销售捆绑中是线性的我们给出了一个计算效率和样本效率的算法，以找到一个几乎福利最大化的价格向量的约束下的预期消费。设SW（p）为设定价格p所产生的期望社会福利。卖方希望设定价格，以确保每种商品j的预期每轮购买量（记为xj（p））在一定供应量sj的范围内。这模拟了一个现实的场景，其中卖方例如，也许最多可以储备一卡车的货物每日如果补货周期对应于大量的轮次，则用对预期的每个客户购买的约束来近似补货周期约束是合理的，因为这些轮次上的已实现消费集中在其预期周围。在下文中，我们将写x（p）=（x1（p），.，xd（p））来表示由价格p（即当价格被设定为p时对商品的预期需求）引起可分割的商品。与以前的工作不同，我们不对价格反应函数的函数形式进行假设，这取决于买家具体来说，我们假设买家（这些假设得到了大量经过充分研究的估值的满足，包括CES和Cobb-Douglas，如参考文献所示[28]）。出售的捆绑被约束为位于有界集合FRd中（例如，F=[0，1]d意味着每种商品最多只能购买一个单位定理1.1（DI vI sI B lE GOOD s）。 假设d是可分的商品，买家具有强凹和和Hölder连续的估值。 存在一种算法，其将参数d、α、δ> 0作为输入参数。以及一个供给向量s∈Rd，使得在概率至少为1−δ的情况下，该算法输出一个价格向量p∈Rd，使得ACM Transactions on Economics and Computation，卷。号81.第六条。出版日期：2020年4月第六A. Roth等人≤≥++++D ≤ D ≥·∈（d，）·αmx（p）s和SW（p）maxp∈Rd：x（p）≤sSW（p）−α。（一）轮数和总计算时间是d，1和log 1的多项式。α δ单位需求买家和不可分割的货物。在此基础上，给出了在不可分割商品下，当购买者具有单位需求价值时，福利最大化的多项式时间动态定价算法。这里，我们考虑价格向量p∈Rd上的分布D，而不是固定价格向量p。为了扩展我们的符号，设x（D）=Ep<$D[x（p）]，SW（D）=EpD[SW（p）]。 我们证明：定理1.2（在不同的标准中）。假设货物是不可分割的，且买方具有单位需求估价。 有一种算法，它将参数d，α，δ> 0和供应向量s ∈Rd作为输入，使得在概率至少为1 − δ的情况下，该算法输出价格向量p∈Rd上的分布D，使得X（ ） ， 则SW（）最大分布DJ：x（DJ）≤sSW（DJ）−α。（二）轮数和总计算时间是d，1和log 1的多项式。α δ在我们陈述定理的一般性中，使用价格分布而不是固定的价格向量是不可避免的。原因在于，当购买者对不同的商品不感兴趣时，他们是如何打破关系的。如参考文献[24]所示，在没有进一步的泛型假设的情况下，如果买方使用不协调的平局打破规则，那么没有固定的定价可以诱导最优（甚至可行）分配。相反，打破平局需要在买方之间进行协调：打破平局的规则需要针对不同的买方而有所不同，而且基本上需要由机制来具体规定。我们定价方案中的随机性充当了买家之间的协调机制（因为每个买家都面临着不同的价格实现）。备注。在这两种情况下，我们证明了更一般的定理，我们表示我们的结果在一个更强的基准福利的最佳彩票分配，而不限制那些可以引起的张贴定价。2上述定理可以用给定时间范围T的累积后悔来重新表述。然后在相应的定理中的算法的执行对应于有界长度的探索阶段。由算法计算的价格向量p用于由所有后续轮次组成的开发阶段。定理1.1保证了我们的算法是在多项式中完成的 log1−m轮，对于某个常数.相对于最佳固定价格的矢量可以由y1的勘探周期和a+δ的勘探周期来确定。是的。 通过优化α和δ的选择，得到了最优的（d，logT）Tm/（m+1）. 对于单位需求设置，1.2意味着类似的推论。扩展到有限供应。我们将我们的结果扩展到一个有限的供应设置。在我们的模型中，有一个固定的T轮，卖方有一个不可消化的供应Tsj单位每一个好的J。T和s[0，1] d 都是提前知道的。每天，卖家都会设定价格，随机的买方将购买他们偏好的捆绑包，直到时间范围或卖方对于定价策略π，我们使用SWtot（π）来表示其预期总福利。 同样，2一个算法计算出的标价向量（分别是它们的分布）只能希望与 最佳发布价格向量（分别为分布）。因此，公式（2）背后的数学陈述是，定理中使用的公布价格基准实际上等同于更强的基准。ACM Transactions on Economics and Computation，卷。号81.第六条。出版日期：2020年4月多维动态定价第六DD++≥–D ≥p2个4个总是独立于相同的固定分布绘制价格向量。这些策略的预期总福利分别表示为SWtot（p）和SWtot（）。在可分物品的设置中，我们简单地使用定理1.1的算法，具有相同的约束向量。通过该算法计算的价格向量p实现了高预期的总福利为一个给定的问题实例：我们证明了它是接近最优的最佳固定向量定价策略相比。此外，与任何定价政策相比，它几乎是最优的。同样，在单位需求购买者的设置中，我们使用定理1.2的算法，具有相同的约束向量s。与x（D）≤s的最优固定分销定价策略相比，该算法计算的分销D是接近最优的。第1.3节. 考虑供应有限的动态定价。固定约束向量s ∈ Rd和时间水平T>32log（T）/s，其中s=minjsj。(a) 考虑d个可分商品和具有强凹和和Hölder连续估值的买家的设置。 当定理1.1中的算法被给定为输入d，s，α，δ，概率为1-δ时，它输出一个价格向量p ∈ Rd，使得软件总计（p）供应价格政策π SW到t（π）−αT−O。，Tlogg（T）/s 的对数。(b) 假设d个不可分割的货物和买家单位需求估值。 当定理1.2的算法被给定为输入d，s，α，δ，概率为1 δ时，它输出价格向量上的分布，使得S3-S4（）supx（DJ） ≤s的分布 DJSW到t（DJ）−αT−O。，Tlogg（T）/s 的对数。轮数和总计算时间是d，1和log 1的多项式。α δ1.2我们的技术我们对可分商品的一般性结果建立在一个关键的结构性质上：即使诱导捆绑x（p）的预期福利在价格向量p中不是凹的，但如果我们将捆绑本身视为决策变量，它就会变成我们通过一个简单的一维例子来说明这一点，改编自参考文献[28]。实施例1.4. re是一个单一的goo d（d=1），并且是一个单一的bu y r，其值为v（x）n=nx。THE卖方如果价格p被公布，那么购买者因此，福利是SW（p）= v（x（p））− c（x（p））=1− 12.x-p·x，注意福利不是价格的凹函数。然而，如果我们将福利写为x=x<$（p）的函数，那么购买的商品数量，这个函数是凹的：SW（x）= v（x）− c（x）= x − x。因此，我们想优化预期福利作为一个功能的诱导束。但是，我们只控制价格，不诱导捆绑。为了解决这个问题，我们的算法有两个“层”，外层优化诱导的捆绑，内层找到一个价格向量，近似诱导一个给定的捆绑。另一个挑战是，福利没有得到观察，因为我们没有观察到买家的估值。相反，我们找到了一种方法来近似福利的次梯度，并使用噪声容忍次梯度下降来优化捆绑。第六章：A. Roth等人ACM Transactions on Economics and Computation，卷。号81.第六条。出版日期：2020年4月我们建立并扩展了参考文献[28]的结果，用于单一购买者和无限供应的特殊情况（关注利润而不是福利）。主要区别是单一买家与买家分布;换句话说，参考文献[28]假设对于给定的价格向量，结果是确定的，而在我们的文章中，它是从一个固定但未知的分布中得出的。我们算法的这个扩展提出了几个技术挑战，并回答了他们的主要开放问题之一。特别地，我们分析了参考文献[28]中使用的凸规划技术的推广，以适应（任意多个）买家的分布。我们不能使用参考文献[ 28 ]中的相反，我们开发了一种新的技术来获得福利函数的次梯度，以实现一阶优化。此外，我们删除了同质买家估值的主要假设。如上所述，我们的一般结果不适用于不可分割商品的单位需求买家为了把这个问题作为一个可分割的商品问题，我们认为买家对可分割的商品有线性估值，对至多有41范数的捆绑集进行优化。使线性函数最大化的丛总是在可行域的顶点处，因此是积分的。也就是说，它是在不可分割的商品设置中由单位需求购买者购买的捆绑然而，有一个实质性的困难：我们的一般技术依赖于买方估价函数是强凹的，线性函数不满足的条件在凸优化文献中获得强凸性的标准方法是向目标函数添加强凸正则化子然而，我们不能以这种方式修改买方相反，我们扰动我们的一般动态定价算法与Gumbel噪声提出的价格向量。这样做具有这样的性质，即每个买家购买的预期捆绑（其中期望值超过价格扰动）是最大化买家的线性估值函数的捆绑因此，在我们的扰动预期，我们可以看到买家作为优化的估值函数，是强凹的41范数，即使对于每个固定的扰动，买家最大化一些线性函数，从而购买一个单位捆绑不可分割的商品。因此，通过扰动在我们的算法运行过程中用于可分割商品的价格向量，我们可以优化这些“正则化”买家的福利通过降低噪声率（因此隐式正则化参数），我们接近实际的，单位需求的买家的最佳福利有限供给的扩展（定理1.3（a））依赖于来自背包强盗的技术[5]，有限供给的动态定价是一个特殊情况。我们使用一个非标准的1.3相关工作我们的背景与几个行业有关第一，动态定价，也就是learn-and-earn，专注于每种商品都有大量库存的卖家，面对估值未知的买家流这是一个很大的工作范围，主要是在运筹学中--参见参考文献[13]的综述。最相关的是非贝叶斯方法。如上所述，主要区别在于我们对买方估值而不是价格反应函数进行假设。此外，据我们所知，学习和赚钱的文献并没有考虑福利优化。其次，我们的问题可以被视为多武装土匪问题[16，22]的一个实例，这是一个经过充分研究的抽象框架，其中算法重复选择动作（例如，价格向量）并接收奖励（例如，销售收入主要问题是多维动态定价第六ACM Transactions on Economics and Computation，卷。号81.第六条。出版日期：2020年4月很好信息的获取和使用，也就是，探索与开发的权衡Bandit算法通过离散化[4，5，26]或通过对预期收入的假设直接适用于动态定价。[3]主要区别（还是）在于，强盗问题的解决方案倾向于直接对回报做出假设，部分原因是它们没有对回报背后的更精细结构（如估值函数）进行建模。第三，有几篇关于组合拍卖中福利优化定价的论文[6，12，18，20]。这些论文解决了不可分割商品和非IID估值的更困难的场景，因此获得了较弱的乘法保证。此外，定价要么是静态的[6，20]（不随时间变化），要么随时间变化但不适应观察到的购买[12，18]。本研究的动机主要是连接到组合拍卖的机制设计。第四，从萨缪尔森[30]开始，有大量关于显示偏好的文献;背景见[27，29，32]。经济学中的大多数工作都集中在解释或合理化给定价格/捆绑观察序列的效用函数的构建上;例如，参考文献[1]。最近的文献研究了在不同价格点上预测购买决策的问题[8，9，35]。与我们的文章更相关的是Amin et al.[3]他研究了用线性效用函数迭代地设定价格以最大化从单个预算购买者（重复地做出购买决策）获得的利润的一个相关但不同的文献关注于从这些函数的示例评估中学习赋值函数[7]，而不是从这些函数的示例最大化中学习（如在显示偏好文献中）。参考文献[28]。 从技术角度来看，最相关的论文是我们之前的工作[28]。我们从以前的工作中继承的主要技术是两层算法，在第3节中详细介绍。然而，我们的工作在许多重要方面与参考文献[28]不同首先，我们的目标是福利最大化，而参考文献[28]关注的是利润最大化。其次，我们研究了一个随机设置，其中买家来自一个未知的分布，但在文献[28]的设置中，一个具有未知估值函数的固定买家重复出现。为了处理买家的随机到达，我们推导了参考文献[28]中定义的凸规划的随机版本，并很好地利用了我们可以从显示的偏好反馈计算随机梯度的事实此外，我们是第一篇关于“从显示偏好中学习”的论文最后，我们还将我们的结果扩展到有限供给设置，这在参考文献[28]中没有研究。1.4文件地图第3节包含我们关于可分商品的一般结果（定理1.1的推广）。我们在不可分商品单位需求估价中的应用及扰动技术在第4节中给出了推导这个结果的方法。在第5节中讨论了有限供应设置。为了改进文章的流程，一些细节被推迟到附录。2模型和序言有一个卖方出售d种不同类型的货物给一系列的买方到达一个又一个轮。每个买方的估价v独立于货物估价函数的有限类V上的未知分布σ得出，其中|V|= n. 4，5和V都是未知数[3]例如，如果预期收入在价格上是凹的，那么我们可以对凹回报应用强盗算法[2，17，21，23]。[4]我们取V为有限只是为了方便。我们的结果不依赖于n=| V|，所以它可以任意大。5在整个过程中，R+={x∈R|x≥0}且R>0={x∈R|x>0}分别表示非负实数和正实数，第六章：A. Roth等人ACM Transactions on Economics and Computation，卷。号81.第六条。出版日期：2020年4月V+∼∈+ →+>0个+≡−∈⊥⊥⊥+∈卖给卖家在整个过程中，我们将使用i来索引买家在每一轮t，卖方发布价格向量p=pt研发，和第t个买家与估值v在这些价格下进行购买以使他的效用最大化。特别是，我们考虑两种不同的设置：一个与可分割的货物和其他不可分割的货物。可分割的商品。每个估值v：RdR+是一个从（分数）商品束到价值的函数。在价格p下，估值为v的买家将购买效用最大化的捆绑包，xv<$（p）<$argmax[v（x）−（x，p）]，∈F其中FRd表示可供购买的可行束的集合。不可分割的商品。我们考虑单位需求买家，他们要么购买1个单位，要么是好事要么是坏事每个买方的估价由价值向量v ∈ Rd定义，使得v j表示她对第j个商品的1个单位的价值在第t轮，估值为v的买家xv（p） argmax[vjpj]，j∈[d]<${<$}其中表示不买任何东西的选择（我们定义v=p=0），并且我们允许任意的平局打破规则。卖方有一个（已知的）成本向量cRd，使得生产一单位商品j的成本是cj。卖方希望设定价格以优化预期的社会福利-买方购买的捆绑或项目的预期价值减去其生产成本。特别地，如果卖方在商品上张贴价格向量p，则预期社会福利为SW（p）=Ev. v（xv<$（p））−c（xv<$（p））。、（3）其中重写c（xv（p））以表示采购xv（p）的生产成本。对于任何差异，D除以价格，则预期福利定义为SW（D）=Ep <$D[SW（p）]。计算模型。我们可以将该算法看作是可以访问一个显示偏好的预言ReP（p）：给定任何输入价格向量p Rd，它将从ReP中抽取一个随机估值v，并返回p rchase decision xvR d（p）。我们的目标是设计计算效率高的算法来计算最优的价格只使用多项式许多查询ReP。值得注意的是，预期的或重新分配的社会财富对于算法是不可观测的，因为它不能观测到社会财富v（xv（p））。雷马尔湾事实上，我们的算法只需要访问它查询的每个价格向量p的x_p（p）的有界和无偏估计，我们可以用任何可以计算这种无偏估计的过程来代替ReP2.1噪声次梯度下降在我们的算法中的一个关键成分是能够最小化凸函数（或最大化凹函数），只访问噪声子梯度的功能。我们使用梯度下降算法来实现这一点。下面，我们回顾一些必要的背景。设C∈Rd是一个直径至多为D（w.r.t.）的紧凸集。42 norm）。函数f：C→R在点x∈C处的次梯度是任何向量<$∈C，对任何点y∈C满足不等式f（y）≥f（x）+（<$，y-x）。在x处的所有次梯度的集合记为f（x）。如果f是可微的，那么唯一的次梯度<$就是梯度<$f（x）。X多维动态定价第六ACM Transactions on Economics and Computation，卷。号81.第六条。出版日期：2020年4月∈∈⊆− ⊆∈≤不≤t=1不t=1√基本的次梯度下降法是一种迭代算法，从某个点x1C开始并迭代以下等式：yt+1=xt−η <$t且xt+1=<$C（yt+1），其中η是学习率，<$tf（x t）是函数f在点x t处的次梯度，C（x）=argmin yCxy 表示到C上的投影算子。现在，我们假设<$t和/或xt受噪声影响。我们将使用该算法的两种变体，它们在两种不同的噪声模型下运行。在第一个模型中，算法只能获得次梯度的无偏估计THEOREM 2.1（[36]）. 假设f是凸的，并且对于某个常数 D，G，对所有的步t，次梯度满足E[<$t]∈G_（？）f（x_t）且d_（？）<$t≤G，且集合的维数满足C然后，如果我们以步长η = D/（G T）运行次梯度下降法，则对于任何T与任意初始点x1∈C，则点z=1.不xt满足E[f（z）] minf（x）+ 2DG/ΔT。x∈C在第二个模型中，该算法可以访问无噪声的次梯度，但是点xt在投射后会受到干扰第2.2节. 假设f是凸的，固定常数D、E和G。假设梯度下降算法在每次迭代中执行以下更新：yt+1=xt−η <$t且xt+1=C（yt+1）+t，使得<$t∈R_f（x_t）且d_t∈R_d是噪声向量. 证明了当xt ∈ C时，G ≤G且G≤E，xt∈C对于所有的台阶t，且台阶t的直径满足≤ D.然后，如果我们运行次梯度去-步长为η=D/（GT）的梯度法，对任意T和任意初始点x1∈C，则z=1.不xt满足f（z） minf（x）+DG/x∈CT+GE T.该证明类似于梯度下降的标准分析（例如，参见参考文献[15]中的定理3.1）。为了完整起见，我们在附录B中提供了这个结果的自包含证明。3可分物品设置的一个通用算法本节专门讨论可分商品的设置：我们给出了一个计算效率高的算法，用于找到一个价格向量，该价格向量近似优化社会福利，但约束条件是每个商品j的预期每轮需求不超过sj。具体来说，让x=x（p）表示随机购买者在价格p（或诱导价格）下购买的最优价格包bundlebyp），即xx（p）=Ev. xv（p）. .给定对显示偏好预言机ReP的访问，该算法使用对ReP的多项式查询和保证x_p（p）≤ s来找到近似最优的价格向量p。我们的解决方案概述。我们将提出我们的算法在三个主要步骤。(1) 首先，我们分析了一个相关的凸规划，得到了几个结构性结果。特别地，我们证明了期望的社会福利可以表示为诱导束的凹函数。√第六章：A. Roth等人ACM Transactions on Economics and Computation，卷。号81.第六条。出版日期：2020年4月+12F∈ VFF ≤FFFF..++(2) 接下来，我们给出了算法的内层：给定任何目标束x，我们可以迭代地找到p个向量p，t，使得诱导束x，t（p，t）在时间上收敛到x，t。(3) 最后，我们展示了如何从现有的信息中获得预期的社会福利函数的次梯度。然后，算法的外层将使用（噪声）次梯度下降来优化束空间上的福利函数。我们对可行集和每个估值函数v做以下假设。在引入福利凸规划之后，我们将对可行集和价值函数都做一个假设装配1（F EA s IB l E S ET）。 对于可行丛的集合Rd=[0，1]d：每个买家最多可以同时购买一个单位的每种商品。一般来说，我们假设是凸的，封闭的，有非空的内部6和有界范数：对于某个参数R，2 R。7第2节（电压）。V中的每个赋值函数v满足：(1) v是F上关于4 - 1范数的（λ，β）-Hölder连续的，其中λ ≥ 1且β∈（0，1]. 不，|v（x）−v（xJ）|对于allx，xJ ∈ F，≤ Λ ·<$X − X J<$β.(2) v是F-上的σ-强凹的，对所有x，xJ∈ F，v（xJ）≤v（x）+（？v（x），xJ−x）−（σ/2）·x−xJ<$2。假设2中的第一个条件确保了估值函数是良好的和光滑的。我们将使用第二个条件-这些关于估值的假设被大量研究充分的估值函数所满足，包括常数替代弹性（CES）和柯布-道格拉斯（见参考文献[28]的证明）。另一个简单例如（如例1.4所述）在一种商品的情况下，v（x）=x，这是增加的，[0， 1]上的（1，1/2）-Hölder连续，1/2-强凸3.1一个随机凸规划设丛x∈Rd是可诱导的，如果存在一个价格向量p∈Rd使得x∈R（p）= x∈ R（p）.注意，每个诱导丛x∈ {\displaystyle x ∈ {\displaystyle x ∈ {\displaystyle x}都是n个丛的凸组合，所以它必须位于集合中。在我们的分析中，一个核心是下面的福利最大化凸计划，charterizes之间的关系公布的价格和诱导捆绑。定义3.1. 对于任意丛x∈ F，设凸规划SCP（x ∈ F）如下：Maxx∈Fn（vi）vi（xi），（4）vi∈V使得对于每个j∈[d]，（5）vi∈Vxi∈ F，对每个vi∈V。（六）6正式定义见定义A.17.对于一个CRd和一个m·d，我们写C=supx∈Cx。 当这位护士不在场的时候，这是一个总结，以达到42。多维动态定价第六ACM Transactions on Economics and Computation，卷。号81.第六条。出版日期：2020年4月.VD∈ F∈VL>0个++阿吉岛Dx∈Fn设VAL（x≠ 0）为凸规划SCP（x≠ 0）的最优值.我们还说SCP（x）是供给饱和的，如果它的最优解x·使方程（5）定义的所有供给约束饱和，即i（vi）xi·j=xj，对于所有j。为了将上述解释为随机福利最大化程序，考虑一个市场，其中有d种商品，每种商品j的供应量为x<$j。对于每个估值函数vi，我们引入一个具有此估值的买家i，他以概率<$i（v i）出现在市场上。我们使用向量xi=（xi1，. ，x_id）来表示如果买方i出现则分配给他的那捆货物。然后，该程序精确地计算了所有购买者的分配，以最大化预期福利，但要满足预期需求不超过由x给出的供给的约束现在，我们准备陈述我们的最后一个假设，它要求凸规划是供给饱和的。3级加速器（饱和）。对于买方分布，凸规划SCP（x≠）为：供应饱和如果类中的赋值是增函数，则SCP（x≠ 0）的最优解将使等式（5）中的所有供应约束ClAIM 1. 假设每个赋值v ∈V在每个坐标上单调递增。则对任意x ∈ F，凸规划SCP（x ∈F）是供给饱和的.对于等式（5）中的每个供给约束，我们可以引入对偶（价格）变量pj写下下面的部分拉格朗日量：Lx（x，p）=.（vi）vi（xi）−.pjl。（vi）xij−x<$j\n （七）vi∈Vj=1Zvi∈Vl我们也可以考虑凸规划的拉格朗日对偶函数：Rd→R：<$x<$（p）= maxx<$（x，p）。（八）x∈Fn我们将主要关注x∈（F <$Rd）的情况，我们可以证明这是一个充分条件，为诱导。83.2. hot water 设x∈（F<$Rd>0个）是丛，则x是可诱导的。P屋顶。考虑凸规划SCP（x≠ 0）。由于凸规划满足Slatermax minLx（x，p）=min maxLx（x，p）=VAL（x）。x∈Fnp∈Rdp∈Rdx∈Fn此外，由于SCP（x）是供给饱和的，最优解满足Ev[x·]=x。让p是最优对偶解。它遵循x ·=argmaxL（x，p·）=argmax.（vi）vi（xi）−.P·J·J·L·（vi）xij−x<$j<$\x∈Fnx∈Fnij=1Zvi∈Vl=argmax.（vi）.vi（xi）−（p·j，xi）+（p·，xi）<$.我[8]丛在每个坐标上为正的限制是必要的--在某些坐标上为零的丛可能是不可诱导的。考虑例1.4中相同的简单设置，其中d=1，并且有一个估值为v（x）=1x。因为0点的边际估值是无穷大的，所以不存在有界价格来诱导买方购买0单位的好。第六章：A. Roth等人ACM Transactions on Economics and Computation，卷。号81.第六条。出版日期：2020年4月我“−≤“F →（1/β）⎪中国共产党请注意，argmax中的表达式可以在i上线性分离。因此，我们认为，xi·=argmax [vi（xi）−（p·，xi）+（p·，xi）]= argmax [vi（xi）−（p·，xi）]。（九）xi∈Fxi ∈F因此，对于每个i，xi·=xvi（p·），因此价格向量p·诱导出丛xi。□接下来，我们证明了诱导丛x的价格是拉格朗日对偶的最优解，并且每个购买者响应于这些价格购买的丛形成了唯一的原始解。最优解3.3. babyBABY 设x <$∈（F <$Rd）是一个丛，p <$∈ Rd是一个价格向量，使得x<$（p<$）= x <$.联系我们然后• 价格向量p是SCP（x≠ 0）的最优对偶解，并且• 向量x ·∈Fn使得xi·=xv<$（p<$）对每个i是唯一最优原始解.引理3.3的一个非常好的结果是，只要诱导丛xx固定，每种类型的购买者购买的已实现丛也固定。这使我们能够将预期的社会福利仅仅表示为诱导包的函数。特别地，在期望中引入x的期望值正好是VAL（x）。这表明了一种不同的方式来表达福利：作为诱导捆绑的函数（与等式（3）中定义的价格向量的函数相反）。对于每个x∈F，我们可以定义SW（x）=VAL（x）−（c，x）。（十）我们可以证明，在期望中引入x的期望社会福利正好是SW（x）（见权利要求5）。更重要的是，通过将福利改写为捆绑的函数，我们得到了一个凹的目标函数。这对于我们以后获得有效的算法是至关重要的。3.4. baby baby 等 式 （ 10 ） 中 定 义 的期望社会福利函数SW： R是凹的。有了以上的结构性结果，我们就可以给出一个两层的算法来寻找福利最大化的价格。3.2内层：将目标捆绑包转换为价格即使我们可以将预期福利表示为诱导捆绑的凹函数，我们仍然不能直接优化该函数，因为卖方只控制商品的价格，而不是预期诱导捆绑本身。为了在捆绑空间上进行优化，我们给出了一个算法，该算法找到一个价格向量，该向量近似地诱导任何目标期望捆绑x。具体地说，假设卖方心中有一些目标捆绑包x，我们可以学习一个价格向量，使得引入的ex p ec t e d bundle接近目标bundle：x（p）ε。在引理3.3中，我们证明了精确地诱导目标丛x<$x的价格是凸规划SCP（x<$x）的最优对偶解，SCP（x <$x）是使La- grangian对偶函数<$x <$x最小化的价格向量p。我们将证明，如果我们能找到一个近似极小的<$x<$，然后，我们可以近似地导出目标期望束x∈{\displaystyle x ∈ {\displaystyle x}}。特别是，我们将应用噪声梯度下降法（定理2.1）来最小化函数<$x，并且为了算法的收敛，我们将价格向量的搜索空间限制为⎧⎪⎨d- 是的4d（1−β）/βP（ε）=<$p∈R+|pε2σ、（十一）其中ε是目标精度参数。在（ε）的定义中，选择42范数界，使得拉格朗日的极小极大值保持接近VAL（x∞），即使当我们限制多维动态定价第六ACM Transactions on Economics and Computation，卷。号81.第六条。出版日期：2020年4月P>0个4>0个>0个∈>0个二元变量/价格在（ε）中，如下所述。证明（推迟到附录）将主要依赖于估值函数的赫尔德连续性。3.5. 设x∈（F <$Rd）. 存在值R-OPT，使得maxp min）Lxmax（x，p）=pmin） maxLxmax（x，p）=R-OPT.x∈Fn∈P（ε∈P（ε x∈Fn此外，VAL（x∞）≤ R-OPT≤ VAL（x ∞）+ ε2 σ.下一个结果将最小化函数<$x<$的近似误差转化为利用V中赋值的强可达性导出目标丛x<$的误差。3.6.BLOG设x<$∈（F <$Rd），pJ是P（ε）中的价格向量，使得<$x<$（pJ）≤minp∈ P （ε ）<$x<$（p）+α，其中α>0. LetxJ=x（pJ）be ex pect e dbundle idbypricespJ. 那么，<$xJ−x< $$> 2