产品组合拍卖和热带几何

2022-5-8 06:05:24

产品组合拍卖和热带地气学MAI TRAN和JOSEPHINE YUAbstract。在最近正在进行的一项研究中，鲍德温和克伦佩尔探索了热带几何学与经济学之间的联系。他们给出了在不可分割商品的产品组合拍卖中存在竞争均衡的充分条件。这个结果，我们称之为单模性定理，也可以追溯到Danilov、Koshevoy和Murota在离散凸分析中的工作。通过整数规划中经典的单模性定理，给出了单模性定理的一个新证明。我们通过热带几何学对这些结果进行了统一处理，并在只有两种产品的情况下，为竞争平衡建立了一个新的有效条件。我们的定理在高维上的推广等价于代数几何中各种形式的Oda猜想。1.导言。拍卖是一种出售商品的机制。这是一个收集投标并产生一组获胜者、每个获胜者获得的商品数量以及获胜者必须支付的价格的过程。产品组合拍卖是针对不同商品的密封式静态拍卖。也就是说，没有人知道其他人的出价，每个代理商只提交一次出价，而且有不同类型的商品。如果货物只能以整数数量出售，则货物是不可分割的，这正是我们感兴趣的情况。每一位代理人（投标人）都会说明她的估价，或者每一批货物对她来说价值多少。在看过投标书后，经济学人为每种商品设定了单价，将供应分成可能是空的捆绑，每个代理商一个。每个代理都按照设定的价格支付指定的捆绑包。如果有一个价格选择和一种精确分配供应的方法，每个代理都被分配一个最大化其效用的捆绑，那么竞争均衡就存在。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 06:05:27

竞争均衡被视为一种理想的、对所有结果的满意。因此，核心经济问题是找到竞争平衡始终存在的条件，如果可能的话，很容易计算。产品组合拍卖是在2007年英格兰银行危机之后由克伦佩雷[15,16]首次提出的。作为一款游戏，它的优点在于简单。特别是，如果存在竞争均衡，那么想要最大化其收益率的代理应该对捆绑包的真实估值出价，这是一个理想的经济结果。产品组合拍卖将许多型号归入特例[2]，包括关键词和短语。热带几何，产品组合拍卖，拍卖理论，集合包装，整数规划，单模性，离散凸性，Oda猜想，光滑多面体猜想，正规多面体，整数分解性质。2 NGOC MAI TRAN和JOSEPHINE Yu本身就是多单元组合拍卖的特例[10]。因此，与产品组合拍卖相关的文献分布在多个领域，从经济学到优化再到离散凸分析。每个领域都有自己的语言、中心问题和符号，因此，发现经常被重复。产品组合拍卖中的竞争均衡是一般均衡的一个例子，更具体地说，是瓦尔拉斯均衡。这种经典的经济模型可以追溯到19世纪末的法国数学家沃尔拉斯。然而，在商品不可分割的产品混合拍卖中，一般均衡理论中经常使用的凸分析和定点技术并不立即适用。Danilov、Koshevoy和Murota在考虑具有不可分割商品的Walrasian经济[7]时采用了这一观点，并寻找经典定点论证的离散模拟仍然有效的条件。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 06:05:30

他们在2001年获得了单模性定理[7，定理4]，尽管它的证明在三年后作为[8，定理3]的特例出现。这个定理的一个版本独立地出现在代数几何界，霍华德[13]在2007年重新发现了本质上是[8，Theorem3]的东西。然后在2012年，Baldwin和Klemperer在[1]中以本文所述的形式和上下文再次独立发现了单模性定理，我们在下文第4节给出的热带几何证明采用了与[8,13]相同的关键论点。从那时起，鲍德温和克伦佩尔利用热带几何发现了产品混合拍卖中竞争均衡的其他有效条件，最著名的是交叉计数定理[2，定理5.12]。新的晶格计数方法与本文讨论的结果是互补的，有关进一步的发展，请参见[2]。我们的论文有两个贡献。首先，我们将产品组合拍卖改写为一个特定的整数规划，将竞争均衡转化为一个线性与整数规划问题，并展示了单模块性定理是如何从整数规划中常用的单模块性定理中继承而来的。它不同于[2,7,8,13]的证明，在[2,7,8,13]中，我们需要找到一类多面体，在这些多面体中，进行Minkowski和运算以及取整数点的运算是相互转换的。其次，我们对产品组合拍卖中的竞争均衡进行了统一处理，并从文献中考虑的所有角度进行了自包含证明：离散凸分析、热带几何和整数规划。利用与晶格多面体的联系，我们给出了一个新的产品组合拍卖家族，其中竞争均衡保证成立（参见定理6.4）。这个结果的推广等价于代数几何中各种形式的Oda猜想。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 06:05:33

定理6.4的设置尽可能远离横向交叉点，这是[2]中发展的重点，因此似乎是新的。文献[2]的读者主要是经济学家，与之不同，本文是一篇关于产品组合拍卖的论文，面向的是一个数学读者，对拍卖理论的先验知识最少。[2]之后，我们选择陈述热带几何的产品组合，因为它引入了优雅的语言和关键几何景观。论文的结构如下。在定义§2中的产品组合拍卖后，我们将§3中的热带几何联系起来，并对§4中的产品组合拍卖和热带几何3单模性定理给出一个简单的证明。竞争平衡的整数规划方法出现在§5中，我们给出了单模块性定理的新证明。我们在§5.2中讨论了其他整数规划公式，并在§5.3中讨论了与子类的关系。最后，在第6节中，我们联系到研究由复曲面几何产生的晶格多面体，例如Oda猜想。符号。一套一套 Rn，让我们来讨论一下（A） RN表示其凸包，convZ（A）=conv（A）∩ zn表示它的整数凸包，|A |表示它的基数。致谢。由于西蒙娜·塞特帕内拉（Simona Settepanella）在2014年组织了一次研讨会，以及马特·贝克（Matt Baker）的一次演讲请求，该项目得以完成。我们感谢伊丽莎白·鲍德温、安东·莱金、伯纳德·斯特姆费尔斯、格莱布·科舍沃伊和拉凯什·沃赫拉的有趣讨论，感谢路易斯·博斯安、保罗·克伦佩尔、查尔斯·王，尤其是伊丽莎白·鲍德温对早期版本的评论，感谢匿名裁判的仔细阅读和有益建议。Ngoc Tran获得了西蒙斯基金会（197982至德克萨斯大学奥斯汀分校）和豪斯多夫数学中心波恩青年奖学金的资助。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

可人4

2022-5-8 06:05:36

Josephine Yu获得了NSF DMS拨款#1101289和#1600569.2的支持。产品组合拍卖。假设有n种不可分割的商品。一个好的束是锌的一个点。对于j=1，J、第J位经纪人向经济学家提供了她的估值函数（bids）uj:Aj→ R、 Aj在哪里 Znand uj（a）是她对捆绑包a的出价∈ Aj。这里的负坐标（可能是负估值）意味着代理人想要销售产品。在这种情况下，卖家和买家扮演着同样的角色。Minkowski sumA=JXj=1Aj:=（JXj=1Aj | aj）∈ 对于每个j=1，J）是经济中所有可能的好捆绑包的集合，可能与这组代理相匹配。对于固定价格向量p∈ Rn，其中Pi是第i个单位货物的价格，第j个代理人以p的价格购买捆绑a的效用是uj（a）-p·a.价格为p的第j个代理的需求集是最大化她的效用（1）Duj（p）：=arg maxa的捆绑集∈Aj{uj（a）- p·a}.4 NGOC MAI TRAN和JOSEPHINE Yu的总估值函数U:a→ RN是划分每个捆绑包的所有方式的最大总估值∈ A:（2）U（A）：=max（JXj=1uj（aj）|aj∈ AjandJXj=1aj=a）。p处的总需求是总估值UDU（p）的需求集：=arg maxa∈A{U（A）- p·a}。我们可以检查它是否是单个需求du（p）=JXj=1Duj（p）的Minkowski和 A.不可分割商品的产品组合拍卖的输入包括估值函数{uj | j=1，…，j}和固定供应捆绑A。经济学家需要找到价格向量p∈ 所以∈ 杜（p）。如果存在这样一个价格，我们说在定义2.1中存在竞争均衡。估值函数集{uj}具有竞争均衡∈ convZ（A）如果存在价格p∈ 因此∈ 杜（p）。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

点击查看更多内容…

2022-5-8 06:05:39

我们说，如果竞争均衡存在于每一个a∈ convZ（A）。当估值均为常数时，竞争均衡在一定程度上存在∈ convZ（A）当且仅当A∈ A+··+AJ。当每个Ai Z、检验竞争均衡的存在性正是一个NP完全的子集和问题。然而，在n=1的情况下，如果每个A包含其凸壳中的所有晶格点，则常数估值存在竞争平衡。这对n来说不是真的≥ 2.例如，A={（0,0），（1,1）}和A={（1,0），（0,1）}包含各自凸壳中的所有格点，但在任何估值（包括常数估值）下，（1,1）都不存在竞争平衡。经济学家对{uj}（或{uj，a}）上存在竞争均衡的一般条件以及确定价格p和这些价格下的赢家分配的算法非常感兴趣。如果有一个卖家和J- 1.一般来说，买方的竞争均衡并不保证卖方获得最大利益。卖家可以通过销售更少的产品来获得更大的收入，参见示例1。卖方利益最大化是一个不同于找到竞争均衡的问题。组合拍卖的目标通常是利润最大化[10]，因此文献不会立即转移。例1。假设n=1，卖方有两个相同类型的对象要出售。有两个代理，A=A={0,1,2}，估值为u（0）=0，u（1）=10，u（2）=11，u（0）=0，u（1）=2，u（2）=3。产品组合拍卖和热带几何学5（0,0），0（0,1），1（1,0），1（0,1），3（0,2），5（1,2），9（0,0），0（0,0），0（0,1），0（0,1），3（0,2），5（0,3），6（1,0），1（2,2），10（1,1），4（1,2），9（1,3），10图1。由两名代理人和两种产品类型组成的产品组合拍卖。从左到右：将A、A、A与估值u、u、Unset设置为相应的捆绑。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 06:05:43

多面体复合体是规则的细分UUU、如例4所述。尽管点（1，1）位于集合A+A中，但捆绑（1，1）的需求价格是不存在的，因此竞争均衡在该点失效。参见例3。竞争均衡价格为{p|1≤ P≤ 2} 当每个代理人购买一件商品时，卖方在竞争均衡下的最大收入为4。然而，如果代理设置价格p=10，那么代理1购买一个对象，代理2不购买任何东西。并不是所有商品都售出，所以竞争均衡不会保持在（1，1），但代理商获得了更大的收入10。我们将用两个例子来说明竞争均衡的失败。例2表明，如果A（convZ（A），竞争均衡肯定会失败，而不考虑代理的估值uj。这是因为总估值U仅在A上是有限的（在其他地方是负的），因此竞争均衡对A之外的点没有影响。另一方面，例3表明A=convZ（A）只是必要的，但不是有效的，保持竞争平衡。例2。设A={（0,0），（1,0）}，A={（0,0），（1,2）}。对于具有域A的任何估值函数u，u，分别而言，总估值u的域是Minkowski和A=A+A={（0,0），（1,0），（1,2），（2,2）}。但是convZ（A）包含点（1，1），而A不包含。因为（1，1）不在U的域中，U（（1，1））=-∞. 因此，对于UAN和u的任何估值，convZ（A）上的竞争均衡将在（1，1）点失败。例3。即使A=convZ（A），竞争均衡也可能不存在。假设我们有两种商品和两个代理人，估值函数如图1所示。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 06:05:47

尽管捆绑（1，1）在A中，但（1，1）处的总估值非常小，以至于总需求集中没有（1，1）处的价格。6 NGOC MAI TRAN和JOSEPHINE YU（0,2）+（0,1）（0,2）+（0,0）（0,1）+（0,0）（0,0）（1,2）+（0,0）（1,2）+（0,1）（1,2）+（0,1）（1,2）+（1,0）（0,0）+（1,0）图2。价格空间根据图1中代理的需求集进行划分，另见示例3。这些区域标记了两个代理中每个代理所需的束。请注意，总需求不等于（1,1）。如果一个价格落在多个地区的边界上，那么需求集中就有多个捆绑。区域之间的边界是热带超曲面并集的负数；注意（1）和（3）之间的负号。热带数学。现在，我们用热带几何学的术语重申产品混合拍卖中确定竞争平衡的问题。鲍德温和克伦佩尔[1]的鼓舞人心的论文中首次提到了这个公式。有关热带代数的详细介绍，请参阅麦克拉根和斯特姆费尔斯的专著[18]。作为一门语言，热带几何学给出了单模性定理（参见定理4.2）的清晰陈述和证明。此外，它还可以方便地分析已知的系列产品，并保证存在竞争均衡。我们在例5中演示了这样一个家庭。这里我们主要讨论max-plus半环（R∪ {-∞}, ⊕, ), 加了热带色彩的一套⊕ 热带繁殖这样的⊕ s:=max（r，s）和r s:=r+s表示所有r，s∈ R∪ {-∞}.就我们而言，任何函数u:A 锌→ 定义了三个重要对象：热带洛朗多项式fu、热带超曲面T（fu）和正则子划分uof A。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 06:05:50

如果函数u是估值函数，那么这三个对象在经济学文献[2]中分别称为效用、差异价格轨迹（LIP）和需求复合体。让我们详细说明一下。热带洛朗多项式在 Z和系数u（a）∈ 为了一个∈ A是（3）fu（x）=Ma∈Au（a）十、A产品组合拍卖和热带几何7，等于函数x 7→ max{u（a）+a·x | a∈ A} 。n个变量的热带多项式的热带超曲面T（fu）定义为x的集合∈ Rn其中集合arg max{u（a）+a·x | a∈ A} 至少有两个基数。也就是说，fu（x）的表达至少在两个术语中达到最大值。在通常的代数中，fu:Rn→ R是一个分段线性凸函数，t（fu）是函数f（x）不光滑的轨迹。规则细分u引起的uof A定义为u:={arg maxa∈A[u（A）十、a] |x∈ Rn}，它是a的子集的集合uare被称为亚分裂的细胞。细胞的凸出外壳称为面。请注意，单元格是一组有限的整数点，而面是一个多面体。A点A∈ 如果包含在一个单元格中，则称为细分的标记点或提升点。每个点都包含在细分的面中，但不一定包含在单元中。规则细分uis与热带超曲面Fu是对偶的，因为在正维曲面之间有一个自然的双射U和热带超曲面的面，如下所示。给定上述热带多项式fuas，考虑Rn上的以下等价关系：两点x，x∈ Rnare等价于arg max{u（a）+a·x | a∈ A} =arg max{u（A）+A·x | A∈ A} 。这给出了RN的一个划分，其中每个等价类是一个相对开放的凸多面体，由线性方程组和严格线性不等式定义。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 06:05:54

热带超曲面是这个划分中维数<n的等价类的并集。通讯录<-> arg max{u（a）+a·x | a∈ A} 是RN中等价类和u、当热带多项式fu的所有系数u（a）=⊕A.∈Au（a）十、A等于0（或任何其他固定常数），则热带超曲面仅依赖于牛顿多面体P=conv A。另一方面，给定一个积分多面体，设f是一个具有常数系数的热带多项式，其牛顿多面体为P。我们将T（P）定义为热带超曲面T（f），它是P的正规扇形的一个子分支，由正维inP面的法向锥组成。与上一节中的等式相比，与产品组合拍卖的联系是明确的。插入x=-p、傅(-p）是以p价格估价u的代理人的最大效用，-T（fu）是一组价格，其中，两个束中的代理和当我们改变价格p时，精确地计算所有可能的需求集du（p），也就是说，u={Du（p）|p∈ Rn}。更重要的是，用热带术语描述多个主体的聚集和竞争平衡很简单，如下所示。8 NGOC MAI TRAN和JOSEPHINE YULemma 3.1。让你，支持向量A上J代理的uJbe估值函数，AJ分别是。假设U是它们在A=PJj=1Aj上的总估值函数。以下保持ofU=fU . . . fuJ，oT（fU）=SJj=1T（fuJ），和oDU（p）=DU（p）+DuJ（p）对于任何价格向量p∈ Rno竞争均衡存在于a点∈ Znif且仅当它是例4。重温例3。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 06:05:57

图1显示了规则的细分在最左边，在中间，和规则的混合细分在极右翼。图2显示了蓝色的热带超曲面T（fu）和红色的热带超曲面T（fu）的负片。它们的集合并是热带超曲面T（fU）的负数。点（1，1）没有标记，因此竞争均衡失败。我们给出了一个几何解释，当一个给定的点在一个规则的细分uis标记（或提升）。想象一个函数u:a 锌→ R表示提升每个点a∈ 在一个新的维度中计算高度u（a），生成函数u（4）lift（a）：={（a，u（a））|a的图形∈ A} A×R.设eu为u的凹主函数，即conv（A）上的最小凹函数，使得eu（A）≥ u（a）代表所有a∈ A.将eu视为一个分段线性表面，通过将保鲜膜延伸到提升（A）上而形成。eu在conv（A）上的线性投影是u、由u.A点A诱导的A的正则细分∈ Znislifted（或marked）当且仅当eu（a）=u（a），也就是说，它确实被u提升到足够高的位置，从而接触到保鲜膜eu。基于这种观点，下面的引理是从定义出发的。引理3.2。让你，支持向量A上J代理的uJbe估值函数，AJ分别是。假设U是它们在A=PJj=1Aj上的总估值函数。以下是等价的（1）竞争均衡的存在。（2） A=convZ（A）和U=eU在A.（3）上每p∈ -T（fU），DU（p）=convZ（DU（p））。（4）对于每个顶点p∈ -T（fU），DU（p）=convZ（DU（p））。在计算上，第二个条件表示，检查竞争平衡涉及评估A中所有点的U和U。最后一个条件表示，这也可以通过检查一组有限的价格来完成，即那些显示为热带超曲面T（fU）顶点的负价格。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 06:06:00

这是因为这样的价格定义了包含最大面的支持向量U.如果所有格点都在Uare标记，则A的所有点都标记为我们说U:A 锌→ 如果A=convZA，u=u，则R是凹的。我们用下面的引理3.3得出结论，这是给定面上竞争平衡产品混合拍卖和热带几何9的特征。这个引理表明，竞争均衡等价于检验Minkowski和是否与取格点通勤。Danilov和Koshevoy在证明单模性定理[7,8]时使用了这一点。这样的问题也出现在复曲面的变种上[11]。我们在第6节中建立了这个联系，利用代数几何中的定理来获得竞争均衡的新定理和猜想。参见Baldwin和Klemperer[2，定理5.16，定理5.21]，了解通过晶格计数方法在给定面上实现竞争平衡的其他标准。引理3.3。让你，J代理的uJbe凹赋值函数，让U betheir聚集赋值函数。为了p∈ Rn，竞争均衡在alla成立∈ DU（p）当且仅当（5）convZ（DU（p））=convZ（DU（p））+…+convZ（DuJ（p））。证据证据根据引理3.1，DU（p）=DU（p）+杜杰（p）。由于估值是凹的，对于j=1，…，convZ（Duj（p））=Duj（p），因此，DU（p）=convZ（Duj（p））+…+convZ（Duj（p））。根据引理3.2，竞争均衡在所有情况下都成立∈ DU（p）当且仅当convZ（DU（p））=DU（p）。因此，这种竞争均衡成立的充要条件是（5）。 4.单模性定理。我们现在准备陈述并证明鲍德温和克伦佩尔[1]在2012年提出的单模性定理。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 06:06:04

另一个版本是2001年首次发现的达尼洛夫、科舍沃伊和穆罗塔[7，定理4]，这是受瓦尔拉斯经济的推动。这一节中给出的两个证明都依赖于相同的关键结果，引理4.3，霍华德[13]在2007年独立发现了引理4.3。我们将在§5中介绍对单模性定理的不同解释。如果非零整数向量坐标的最大公约数为1，则称其为基元。一组向量D 如果D中n个向量的每个线性依赖子集跨越Z定义4.1，则称Z为幺模。设D是zna中的一组本原整数向量锌。我们认为估值是u:a→ 如果细分的每一条边ui与D中的向量平行。换句话说，如果T（fu）的所有整数面法线都位于inD，则u为需求类型D。因为热带超曲面T（fu）是所有j=1的T（fuj）的并集，J、因此，总估值U为需求类型D，当且仅当所有J=1，J.定理4.2（单模性定理[2,7]）。本原整数向量幺模集D当且仅当需求类型D的每一个凹估值函数集合{uj | j=1，…，j}具有竞争均衡。10 NGOC MAI TRAN和JOSEPHINE YU+=图3。两个多面体的Minkowski和可以在不引入新的边方向的情况下进行细分，这样每个最大面就是互补维面的Minkowski和。例如，这可以通过将其中一个热带超曲面在ageneric方向上平移并进行对偶细分来实现。为了证明上述定理，我们首先回顾[2,8,13]中出现的一个引理。为了完整性，我们提供了一个受[2]启发的证明，这与以前的证明不同。引理4.3。假设D是单模的。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

可人4

2022-5-8 06:06:08

如果P和Q是D中边方向的晶格多面体，那么convZ（P+Q）=convZ（P）+convZ（Q）。证据证据将P和Q转换为包含原点，并将Zn替换为Panr（P+Q）∩zn如有必要，我们可以假定dim（P+Q）=n，但不失一般性。首先考虑P和Q包含在互补空间中的情况，即（6）dim（P+Q）=dim（P）+dim（Q）。设B和C分别是p和Q的本原边方向的最大线性独立子集。然后B∪ C是上述尺寸假设的Rn基础。此外，它形成了znd的Z基，因为D是单模的。关于这个基，P和Q位于互补坐标子空间中，因此Minkowskisum P+Q与笛卡尔积P×Q重合，我们得到了期望的结果。现在，假设（6）不成立。让v∈ Rn是一个一般位置的向量，使得热带超曲面T（P）和T（Q）- v横向相交，即只有当两个面的Minkowski和的维数等于n时，两个面才相交。然后，并集T（P）∪ （T（Q）- v）是P+Q的一个子集的对偶，其面具有形式σ+τ，其中σ和τ是具有互补维数的P和Q的面。参见图3。设a是P+Q中的任意格点，则a属于这样一个面σ+τ。由于σareτ是P和Q的面，它们的边缘方向也属于D。与上述相同的公式给出了σ+τ=σ×τ，因此（σ+τ）∩ Zn=（σ）∩ Zn）+（τ）∩ 锌），这给了∈ （P∩ Zn）+（Q∩ 锌）。产品组合拍卖和热带几何证明。单模性定理的证明（定理4.2）。假设集合D是单模的，并且所有的估值uj:Aj→ R是需求类型D的凹形。Foreach p∈ Rn，conv（Duj（p））是D.ByLemma 3.3和4.3中具有边方向的晶格多面体，竞争平衡适用于DU（p）中的所有点。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 06:06:11

因此，引理3.2的第4部分保持了竞争均衡。反之，假设不是单模的。我们需要构建一个需求型的、没有竞争均衡的产品组合拍卖。我们将构建一个估值很小的模型，也就是说，它们的支持度和支持度为零-∞ 在别处通过引理3.3，可以证明存在一个，应收账 zn具有D中的基本边，Aj=convZ（Aj），以及PjAj（convZ（PjAj）。因为D不是单模的，所以存在线性无关的向量v，越南∈ 其中spanZ{v，…，vn}（Zn.LetAi={0，vj}。然后A+···+Ancons是与边v，…，vn平行的顶点，但convZ（A+··+An）由于非单模性而由其他晶格点组成。例5（总替代品和M-凹估值）。在[14]中，Kelso和Crawford引入了集合函数的总替代条件，并证明了在此条件下存在竞争均衡。为了解释这一特性，让我们考虑一个特殊情况。假设每个代理的可用捆绑包集是{0，1}n，也就是说，每种类型只有一个商品可供销售。如果提高某些物品的价格并不会减少其他物品的需求，则估价u具有grosssubstitute财产。也就是说，对于任何价格向量p≤ q和a包a∈ Dp（u），有一束b∈ Dq（u）使得{i∈ a:pi=qi} 其中束A和b被认为是[n]的子集。这意味着UCA不能有两个正（或两个负）条目。所以基本边方向是ei或ei方向- 其中，ei是Zn中的标准单位向量。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 06:06:13

这些向量构成了单模系统A\\n，它是根系统AN={±（ei）的投影- ej）| 1≤ i<j≤ n+1} Zn+1沿坐标方向延伸。在[19，§4，§11]中，Murota定义了M-凹函数，将总替换性质推广到Zn中的其他丛集。特别是凹函数u:a→ R、哪里 Zn，A=convZ（A），如果它可以扩展为conv（A）上的凹函数，并且规则细分中的面是M-凹的M-凸集沿坐标方向的uare投影。M-凸集也被称为广义置换正六面体[20]或多面体。这意味着细胞的原始边缘方向由于A是单模的，根据单模性定理，竞争均衡成立。参见[19，§11]进一步讨论总替代品的等效特征以及与最小成本流动问题和算法的联系。5.通过整数规划实现竞争均衡。在本节中，我们证明了当且仅当下面的线性规划（P）有一个积分最优解（定理5.1），或等价地，由（15）-（18）定义的线性规划有一个积分最优解（命题5.5），在某一点上存在竞争均衡。第一个程序是新的，它明确了与需求类型D的单模块性的联系。特别是，通过整数规划[21，§19]中众所周知的单模块性结果，单模块性理论如下所示，是定理5.1的推论。第二个线性规划将产品组合拍卖视为多单元组合拍卖。虽然它不能立即证明单模性定理，但它在计算和直觉上可能更容易处理。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 06:06:16

作为一个例子，我们使用这些线性规划来考虑竞争均衡约束下的利润最大化问题。5.1. 单模性定理的整数规划证明。首先，我们简要介绍一下主要观点。回想一下，我们在一个通过八次函数U:A将zn转换为A×R→ R、然后以凹面majoranteU为例，它是conv（a）上的函数。我们说a点∈ 如果eu（A）=U（A），则A被提升。确定一个点*∈ 答：我们的目标是描述*被举起。不管它是否被提起*属于规则细分的某个面Uof由集合包含的U阶单元产生，如果σ小于τ，则表示σ小于τ τ . 出租*是最小的细胞*∈ conv（D）*). 然后D的所有顶点*在conv（A）×R中被提升到Eu图的同一面。点A*可以表达，但不一定是唯一的，作为一些参考点A∈ D*加上面D边缘方向的合理线性组合*. 集合估值函数U被定义为在分解a的情况下，个体估值的某些总和中的最大值*成整数束，而*), 这在conv（D）上是线性的*), 是某些有理线性组合上的最大值。是否*可以用一个特定的线性规划是否有一个整体解来表达。此外，当边集D是单模的时，面conv（D）的边集*) 也是单模的，我们可以用它来证明线性规划是有积分解的。在接下来的内容中，我们使上述想法更加精确，并表明参考点ea的选择并不重要，因此我们有一个定义良好的整数规划及其线性松弛。允许D*是conv（D）的顶点集*).

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 06:06:20

让我们（a）*) 表示支持conv（D）的价格向量集*), 也就是说，S（a）*) = {p∈ Rn |欧盟（ea）- p·ea≥欧盟（a）- 所有ea的p·a∈ D*, A.∈ A} 。对于顶点ea∈ D*, 单态集{ea}是因此{ea}=DU（p）=DU（p）+···+DuJ（p）对于某些p∈ Rn，所以ea可以唯一地写为ea=pjeaj，其中每个eaji都是细分的顶点ujof Aj。然后S（a）*) 是p的集合∈ Rn（7）uj（bj）- p·bj≤ uj（eaj）- p·EAJ适用于所有ea∈ D*, 北京∈ Aj，对于所有的j=1，J.产品组合拍卖和热带几何学13重写后，我们得到了P·（eaj）- （北京）≤ uj（eaj）- uj（bj）代表所有bj∈ Aj，j=1，J和所有ea∈ D*.假设p上总共有N个这样的约束，设V为N×N矩阵，其中列为向量eaj- bjas接管了所有的eajand bj，让c∈ 带有条目（8）uj（eaj）的RNbethe向量- uj（bj）对应于列eaj- 分别是BJV。然后我们可以重写*) 屁股（a）*) = {p∈ Rn | V>p≤ c} 。让ea成为任何一点D*. 考虑决策变量P中的以下程序∈ Rn：最大化p·（ea）- A.*)（D）以V>p为准≤ c、它是决策变量x中下列原始线性规划的对偶∈ RNC>x（P）受Vx=ea影响- A.*, 十、≥ 0.定理5.1。让我们*∈ A和ea∈ D*. {uj}存在的竞争均衡*当且仅当线性规划（P）在x上的最优解∈ r等于x上的最佳值∈ 锌。我们将定理5.1的证明分解为两个较小的引理。引理5.2说程序（D）和（P）的最优解独立于a的选择。引理5.3说，当a*被举起。引理5.2。每个可行解在（D）中都是最优的，目标函数值为u（ea）-欧盟（a）*).证据证据考虑conv（A）上函数eu的图，它是conv（A）×R的子集。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 06:06:24

脸上的所有点（D*) 相应地被提升到图的凸包的上切面。任何p∈ S（a）*), 向量(-p、 1）支撑该面。因为两者都是*ea属于conv（D）*), 我们有欧盟（a）*) - p·a*=欧盟（ea）- p·ea。那么（D）中目标函数的值是（9）p·（ea- A.*) =欧盟（ea）-欧盟（a）*) = U（ea）-欧盟（a）*).第二个等式如下，因为ea是细分中的一个顶点，因此是一个标记点U.自值U（ea）-欧盟（a）*) 不依赖于p，因此在（D）中所有可行解都是最优的。 14 NGOC MAI TRAN和JOSEPHINE YULemma 5.3。任何可行的解决方案∈ ZNof（P）satis（10）c>x≥ U（ea）-欧盟（a）*).对于某些可行的x，等式成立∈ ZNif且仅当U（a）*) =欧盟（a）*).证据证据通过引理5.2，我们知道U（ea）-欧盟（a）*) 等于最佳目标值p·（ea- A.*) 关于原始问题（P）。弱线性规划对偶[21，§7]则意味着（10）。它仍然需要显示平等发生的条件。任何可行的x满意度- vx=a*. 回想一下，V列是从A点指向A点的向量uj。因为ea是D的顶点*, 存在一个唯一的分解ea=ea+···+eaJsuch，eajis是Duj（p）的顶点，对于p，D*= 杜（p）。因此，任何可行的解决方案∈ ZN给出了一种写作方式（11）a*= （ea+v）+··+（eaJ+vJ），对于一些向量v，vj使每个eaj+vjlies在Aj的整数范围内。考虑eaj+vjto Rn×（R）的升力∪ {-∞}) 根据uj的估价。如果eaj+vj/∈ Aj，然后它被提升到-∞.

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 06:06:27

因为ujis凹面和(-p、 1）支撑D的提升*, 我们有（12）uj（eaj+vj）- p·（eaj+vj）≤ uj（eaj）- p·eaj相等的充要条件是eaj+vj∈ 杜杰（p）。对所有的j求和，我们得到（13）JXj=1uj（eaj+vj）- p·a*≤ U（ea）- p·ea。因此（14）U（ea）-欧盟（a）*)（9） =p·（ea）-A.*)(13)≤ U（ea）-JXj=1uj（eaj+vj）=JXj=1uj（eaj）- uj（eaj+vj）= c> x，其中x给出了将vj写成V列总和的系数；见（11）。（14）中的最后一个等式来自（8）中向量c的定义。在（10）和（14）中，对于某些可行的x，实现了相等∈ zn当且仅当（12）中每j=1，J.当且仅当*在（11）中，通过满足eaj+vj∈ Duj（p）表示一些p∈ S（a）*), 对于所有的j=1，J.但这是对*∈ 杜（p）。所以，假设（P）是可行的，等式出现在（10）中当且仅当U（a）*) =欧盟（a）*). 产品组合拍卖和热带几何证明。定理5.1的证明。考虑引理5.2。通过线性规划对偶，得到了x上线性规划（P）的最优值∈ RNis也是U（ea）-欧盟（a）*).如果（P）在x上可行∈ ZN，那么引理5.3意味着期望的陈述。如果（P）在x上不可行∈ 锌，然后是a*不在A中，因此不存在竞争均衡*, 线性规划和整数规划（P）不一致。因此，期望的陈述在这种情况下也成立。推论5.4。定理5.1暗示了单模性定理。证据证据假设所有的赋值函数都是凹的，并且是单模的。那么任何一点bj∈ 可以从子分区的任何顶点EAJO到达AJujby沿着细分的原始边方向行走，因为方向集是单模块的。因此，在（D）和（P）中，我们可以从V和c中删除所有列，除了那些对应于细分的原始边方向的列。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 06:06:30

然后我们得到了一个单模矩阵V，它给出了与之前相同的线性和整数规划的最优解。整数规划中的一个众所周知的结果表明，（P）总是有积分最优解（见[21，§19]），因此，根据定理5.1，A的所有点都存在竞争均衡*∈ 答：这正是单模性定理的困难方向。 5.2. 加权集合包装和凯利技巧。让我们确定一个供应捆绑a*假设0∈ aj对于每个j.考虑以下集合填充问题，其中j=1的决策变量为y（a，j），J和a∈ Aj。最大化ejxj=1Xa∈Ajy（a，j）uj（a）（15）受y（a，j）约束≥ 0表示所有j=1，J和a∈ Aj（16）Xa∈Ajy（a，j）=1表示所有j=1，J（17）JXj=1Xa∈Ajy（a，j）a=a*（18）为了一捆∈ Zn，y（a，j）=1意味着我们将束a分配给代理j。约束（16）、（17）和（18）分别表示，每个代理j被分配一个负的束分数，它们接收的束的总质量为一，并且*项目一起分配给所有代理。目标（15）要求分配一项使总估值最大化的任务。提议5.5。{uj}的竞争均衡存在于*当且仅当（15）-（18）定义的线性规划存在一个整数可选解，即所有y（a，j）都是整数的最优解。16 NGOC MAI TRAN和JOSEPHINE Yufolf。证据根据定义（2），总估值U（a*) 是整数程序（15）的最佳值。对于j=1，…，LeteU是U的凹主，eujbe是ujj的凹主，J.注意（19）欧盟（a）*) = 最大值（JXj=1euj（aj）：aj∈ conv（Aj）和xj∈Jaj=a*).由于每个ujis都是凹的，因此uj=eujon每个Aj。因为conv（A）=conv（A）++conv（AJ），适用于任何a*∈ conv（A）∩ Z凹面马约兰图（a）*) 是线性规划的最佳值（15）。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 06:06:34

竞争均衡的存在性*意思是你*) =欧盟（a）*), 我们有这个命题的陈述。线性规划（15）-（18）可以用“凯利把戏”来重新表述，如下所示。Cayley系列的配置A，AJ zn是ZJ×zn中的点配置，由点cay（a，…，AJ）=（{e}×a）组成∪ · · · ∪ （{eJ}×AJ）。Cayley技巧表示，在Minkowski和a=Piaian的混合细分和Cayley配置Cay（a，…，AJ）的细分之间存在一个自然的双射[22]。有强大的理论和软件来理解后面的[9]，因此这个技巧经常被用来计算和理解混合细分。设C为矩阵，其列为Cay（A，…，AJ）中的点。Letu是估值uj（a）的向量，其条目自然对应于ofC列。那么（15）-（18）可以简单地表示为最大化u·y（20），受y的约束≥ 0和Cy=A.*（21）其中1是ZJ中的所有一个向量。也就是说，竞争均衡是一个使用Cayley配置定义的特殊优化问题，它与加权集装箱问题一致。定理5.1和命题5.5中的两个线性规划是看待竞争均衡的不同方法。根据问题的不同，一个公式可能更容易使用。为了说明这一点，假设竞争均衡存在于*. 假设我们想要找到一个价格p，它能以一个合理的价格提供竞争均衡*同时最大限度地提高卖方的利润率。从程序（D）和（P）的观点来看，需要最大化P·a*（22）根据V>p≤ c、然而，形成V和c需要找到D的所有顶点ea*将它们的合成转化为顶点的和uj。在这种情况下，集合包装视图（15）-（18）给出了以下更有效的公式。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 06:06:37

Bikhchandani和Mamer在[3]中研究了类似的问题。产品组合拍卖和热带几何17引理5.6。让（y）*（a，j）j=1，。。。，JA.∈aj可能是（15）的最优积分解。均衡价格∈ 使卖方利益最大化的是以下线性规划的解决方案：使p·a最大化*（23）根据uj（a）- p·a≥ uj（b）- p·b，对于每j=1，J、每一天∈ 阿吉*（a，j）=1，且每b∈ a与a相邻uj。证据证据设F为线性规划在该问题中的可行解集。我们希望证明F=S（a*) = {p∈ Rn | a*∈ DU（p）}。如果p∈ F，然后{a∈ Aj | y*（a，j）=1} Duj（p），所以a*∈ 杜（p），辛恰*=Xaj∈Aj:y*（aj，j）=1aj∈JXj=1Duj（p）=DU（p）。这表明F S（a）*).现在假设p∈ S（a）*). 也就是说，有bj∈ Duj（p）使得*=PJj=1bj。对于每个j，让AJY成为AJY的唯一元素*（aj，j）=1。自从bj∈Duj（p），我们有uj（bj）- p·bj≥ uj（aj）- p·aj，安度（a）*) - p·a*=JXj=1uj（北京）- p·bj≥JXj=1uj（aj）- p·aj= U（a）*) - p·a*.这表明（7）中的所有不等式都是在相等条件下得到的，所以uj（bj）- p·bj=uj（aj）- p·aj代表所有j.因此aj∈ Duj（p）对于所有j，p是（23）的一个可行解。 5.3. 竞争均衡和子集和。我们对竞争均衡的各种表述导致了在给定点a上验证竞争均衡存在性的几种算法*. 没有进一步的假设，它们都涉及子集和问题，因此都是NP完全的。有不同层次的困难。首先，对于任意的bundle a*∈ Zn，正在验证*∈ A=PJj=1Ajis是一个子集和问题，即使只有一种类型的好（n=1）。其次，假设我们知道*∈ A.在命题5.5中，可以假设ujis凹，0∈ 每一个j。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 06:06:40

然后，对于n=1，allagents具有单模需求类型，因此竞争均衡在n=1时通常成立。然而，对于n>1，单模性定理可能不适用。通过外稃3。2.竞争均衡*当且仅当U（a）时成立*) =~U（a）*) 其中U是总估值，~U是其主要值。计算U（a）*) 又是一个集合和问题。这在5.5号提案中有详细说明。知道*∈ 虽然线性规划（15）在R上有一个可行的实解，但这并不保证是一个积分解。18 NGOC MAI TRAN和JOSEPHINE Yu或者，假设我们知道一个价格p∈ 因此*∈ 杜（p）。由于个体估值{uj}是凹的，我们可以计算Duj（p）。然后可以建立Integer程序（P），其解决方案通过定理5保证竞争均衡。1.程序（P）询问一个人是否能写一个*a加上一组给定向量V的积分组合。这是子集和的又一个例子。假设*∈ A、单模性定理将（15）和（P）中的子集和问题替换为一个有效且易于检查的条件（即一组向量的单模性），使竞争平衡保持在*.Baldwin和Klemperer[2，定理5.16]的子群指数定理给出了热带超曲面{Tuj}有横向相交时的一个替代判据。这意味着a的值uj（a）∈ a是非常普遍的，因此热带超曲面T（fuj）的所有截面局部看起来像是一个平面空间的横向交点。例如，可以通过向每个值uj（a）添加一个小实数来实现。假设知道面DU（p）及其分解为j=1时Duj（p）的Minkowski和，J、横向相交意味着所有面Du（p），DuJ（p）是顶点，比如，对于j=n+1，…，DuJ（p）={aj}，J

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

可人4

2022-5-8 06:06:43

这有效地降低了子集和问题的维数，从分解*转化为J项之和，最多为N项。参见[2]及其中关于该环境下竞争均衡的充分条件的讨论。从计算的角度来看，在某些给定条件下，横向交叉并不能保证竞争均衡*. 相反，它保证了对于固定n，可以在J.6中的时间多项式的所有点上联合检查竞争平衡。稳定拍卖和Oda猜想6。1.n=2的稳定拍卖和竞争均衡。考虑一个productmix拍卖，其中有J个代理和n个产品类型。让我们将代理划分为不相交的非空子集，并计算每个子集上的产品组合。这些子集拍卖的哪些性质将保证原始拍卖具有竞争均衡？这种分而治之的条件在理论上和计算上都很有吸引力。在本节中，我们给出了n=2时的有效条件（定理6.4）。高维中的类似陈述相当于复曲面几何中的Oda猜想，见第6.3节。假设所有的子集拍卖都有竞争均衡。这种条件显然不足以保证整体竞争均衡。例如，当每个子集只包含一个代理时，每个子集中竞争平衡的存在相当于个体估值是凹的。然而，也有产品组合拍卖，其个别估值呈凹形，但没有竞争均衡。与直觉相反，我们证明了子集拍卖中的个人竞争平衡甚至是不必要的。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 06:06:46

也就是说，我们在OREM 6.4中的条件允许部分子集拍卖的竞争均衡失败，但它们保证联合拍卖具有竞争均衡。乘积混合拍卖和热带几何学定理6.4与[2]中的结果是互补的，后者侧重于热带超曲面的横向相交。在某种程度上，我们的设置尽可能远离横截面：该假设意味着一个子集试剂的热带超曲面包含其余试剂的并集。定义6.1（稳定拍卖）。考虑与J≥ 1个估值为凹型的代理，n≥ 1.产品类型。将代理划分为K≤ Jdisjoint，非空集合，并在每个集合上分别运行产品组合拍卖。设Uk为第k组代理的总估值，为1≤ K≤ K.如果第一个子集拍卖具有竞争均衡，我们称这种划分为稳定的，并且（24）T（fUk） T（fU）对于所有k=1，K.如果产品组合拍卖有一个稳定的分区，我们说它是稳定的。直观地说，稳定条件（24）表明，第一个子集拍卖“丰富”，足以捕捉到关于原始拍卖的许多信息。请注意，我们要求竞争均衡仅适用于第一次子集拍卖。对于其他子交易，允许竞争均衡失败。相反，我们通过（24）对它们的热带超曲面进行了限制。有两种方法可以解释这种情况。首先，根据引理3.1，T（fU）=J[J=1T（fuj）=K[K=1T（fUk）=T（f（U））。换句话说，假设一个人通过一次添加一个代理来迭代计算价格差异集合T（fU）。然后（24）意味着在处理第一个代理子集后，该集合不会改变。也就是说，差异价格的轨迹稳定，因此称为稳定拍卖。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 06:06:51

稳定性的概念是关于热带超曲面的并集，不要与热带几何学中的稳定相交混淆。人们还可以理解（24）中的需求集DU，杜克。每种价格∈ R、在这个价格下，我们可以计算每个子产品中需要多少产品捆绑包，忽略按常量倍数进行的缩放。引理6.3指出，如果对于所有价格p，这个数字在第一次子集拍卖后没有上升，那么（24）成立。现在，我们给出了条件（24）的一个简单有效条件。以下定义概括了基本边方向的概念。定义6.2。为了P 锌，P的原始多面体，表示P↓, 是最小的多面体Q吗对于某些c，c·Q=P∈ 引理6.3。如果（25）|（DU（p））该陈述（24）为真↓| ≥ |（杜克（p））↓| 对于所有k=1，K.也就是说，无论价格是多少∈ R、在第一次拍卖中，至少有和其他拍卖中一样多的原始商品。20 NGOC MAI TRAN和JOSEPHINE YUProof。证据注意，对于任何多面体P 锌，磷≥ |P↓| ≥ 1和| P↓| = 1 i且仅当| P |=1时。如果-P∈ T（福），然后| DUk（p）|≥ 2，so |（DUk（p））↓| ≥ 2.由（25），|DU（p）|≥ 2.因此-P∈ T（fU），so（24）成立。定理6.4。对于n=2种产品类型，稳定的产品组合拍卖具有竞争平衡。证据证据考虑一个具有K子集的稳定划分。根据引理3.1，T（fU）=SKk=1T（fUk）=T（fU）。因此，在不丧失普遍性的情况下，我们可以选择第一次拍卖，并假设所有剩余的拍卖都由一个代理组成。现在，让p是的顶点-T（fU）。通过引理3.2，充分证明了竞争均衡对convZDU（p）中的所有点都成立。由于每个估值都是凹的，通过引理3.3，我们需要证明（26）convZ（DU（p）+…+DUK（p））=convZ（DU（p））+。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-8 06:06:54

+convZ（DUK（p））。As T（fU）=T（fU） T（fUk），DU（p）的正常风扇定义了所有k=1，[12]中的定理1精确地说明了这个正常的假设意味着（26）。证据到此结束。推论6.5。对于n=2种产品类型，如果所有代理都有相同的凹形估值，则无论需求类型如何，所有相关供应捆绑都存在竞争均衡。下一个例子表明，产品组合拍卖可以是稳定的，即使某些代理人的子集不存在竞争均衡。例6。假设n=2，J=3。设A={（0,0）、（1,2）、（1,0）、（1,1）、（2,2）}，A={（0,0）、（1,0）}，A={（0,0）、（1,2）}。让估值u，u，ube分别为零，onA，A和A，和-∞ 在别处将代理划分为K=2组，第一组由代理1组成，第二组由代理2和3组成。这里D={（1，0），（1，2）}不是一个单模集，实际上，对于第二个子集拍卖，竞争均衡在（1，1）处失败。只有经纪人1参与的首次拍卖具有竞争平衡。可以验证（25）是否成立。根据定理6.4，所有三个代理人的拍卖具有竞争均衡。图4.6.2对此进行了验证。相同的赋值和整数分解属性。推论6.5的类似物在三种或三种以上的产品类型中失败。也就是说，对于n≥ 3.存在产品组合拍卖，其中所有代理都有相同的凹形估值，是的，竞争均衡失败。直接的后果是，与REM 6.4类似的产品在尺寸上出现故障≥ 3.提案6.6。为了n≥ 3.有拍卖o所有代理人都有相同的凹估值，并且o竞争均衡失败。特别是对于n≥ 3.存在没有竞争均衡的稳定拍卖。产品组合拍卖和热带几何21图4。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝