产品组合拍卖和热带几何

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

英文标题：
《Product-Mix Auctions and Tropical Geometry》
---
作者：
Ngoc Mai Tran and Josephine Yu
---
最新提交年份：
2017
---
英文摘要：
  In a recent and ongoing work, Baldwin and Klemperer explored a connection between tropical geometry and economics. They gave a sufficient condition for the existence of competitive equilibrium in product-mix auctions of indivisible goods. This result, which we call the Unimodularity Theorem, can also be traced back to the work of Danilov, Koshevoy, and Murota in discrete convex analysis. We give a new proof of the Unimodularity Theorem via the classical unimodularity theorem in integer programming. We give a unified treatment of these results via tropical geometry and formulate a new sufficient condition for competitive equilibrium when there are only two types of product. Generalizations of our theorem in higher dimensions are equivalent to various forms of the Oda conjecture in algebraic geometry.
---
中文摘要：
在最近正在进行的一项研究中，鲍德温和克伦佩尔探索了热带几何学与经济学之间的联系。他们给出了不可分割商品的产品组合拍卖存在竞争均衡的充分条件。这个结果，我们称之为单模性定理，也可以追溯到Danilov、Koshevoy和Murota在离散凸分析中的工作。通过整数规划中的经典单模性定理，给出了单模性定理的一个新证明。我们通过热带几何学对这些结果进行了统一处理，并在只有两类产品的情况下给出了竞争平衡的一个新的充分条件。我们的定理在高维上的推广等价于代数几何中各种形式的Oda猜想。
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Computer Science and Game Theory        计算机科学与博弈论
分类描述：Covers all theoretical and applied aspects at the intersection of computer science and game theory, including work in mechanism design, learning in games (which may overlap with Learning), foundations of agent modeling in games (which may overlap with Multiagent systems), coordination, specification and formal methods for non-cooperative computational environments. The area also deals with applications of game theory to areas such as electronic commerce.
涵盖计算机科学和博弈论交叉的所有理论和应用方面，包括机制设计的工作，游戏中的学习（可能与学习重叠），游戏中的agent建模的基础（可能与多agent系统重叠），非合作计算环境的协调、规范和形式化方法。该领域还涉及博弈论在电子商务等领域的应用。
--
一级分类：Mathematics        数学
二级分类：Combinatorics        组合学
分类描述：Discrete mathematics, graph theory, enumeration, combinatorial optimization, Ramsey theory, combinatorial game theory
离散数学，图论，计数，组合优化，拉姆齐理论，组合对策论
--
一级分类：Quantitative Finance        数量金融学
二级分类：Economics        经济学
分类描述：q-fin.EC is an alias for econ.GN. Economics, including micro and macro economics, international economics, theory of the firm, labor economics, and other economic topics outside finance
q-fin.ec是econ.gn的别名。经济学，包括微观和宏观经济学、国际经济学、企业理论、劳动经济学和其他金融以外的经济专题
--

---
PDF下载：
--> Product-Mix_Auctions_and_Tropical_Geometry.pdf (502.44 KB)

2022-5-8 06:05:20 上传

扫码加我 拉你入群

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

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

分享0 收藏0 回帖

关键词：产品组合 Environments Optimization Quantitative Coordination

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

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

他们在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猜想。

定理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至德克萨斯大学奥斯汀分校）和豪斯多夫数学中心波恩青年奖学金的资助。

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）。

我们说，如果竞争均衡存在于每一个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设置为相应的捆绑。

多面体复合体是规则的细分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所示。

尽管捆绑（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。

如果函数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的一个划分，其中每个等价类是一个相对开放的凸多面体，由线性方程组和严格线性不等式定义。