产品组合拍卖和热带几何

热带超曲面是这个划分中维数<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。

图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）顶点的负价格。

这是因为这样的价格定义了包含最大面的支持向量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年提出的单模性定理。

另一个版本是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是单模的。

如果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）中的所有点。

因此，引理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中的标准单位向量。

这些向量构成了单模系统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的推论。第二个线性规划将产品组合拍卖视为多单元组合拍卖。虽然它不能立即证明单模性定理，但它在计算和直觉上可能更容易处理。

作为一个例子，我们使用这些线性规划来考虑竞争均衡约束下的利润最大化问题。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）的顶点集*).

让我们（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的子集。

脸上的所有点（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，然后它被提升到-∞.