没有合适的资源?快使用搜索试试~ 我知道了~
ACM Transactions on Economics and Computation,卷。号74、第二十条。出版日期:2020年1月多单位市场定价TOMER EZRA和MICHAL FELDMAN,特拉维夫大学Tim Roughgarden,哥伦比亚大学WARUT SUKSOMPONG,牛津大学我们研究的权力和限制张贴价格在多单位的市场,代理商到达顺序在任意顺序。我们证明了最优社会福利的最大部分,可以保证与张贴的价格在一系列的假设下,设计师的信息和代理人的估值的上限和下限。我们的研究结果提供了关于统一和非统一价格的相对力量,不同估值类别的相对难度以及不同信息披露的影响的见解。在其他结果中,我们证明了常数因子保证代理商的子加性估值相同的项目,即使在不完全信息设置和统一的价格。我们还表明,没有恒定的因素保证是可能的一般估值相同的项目,即使在充分的信息设置和非统一的价格。CCS概念:·计算理论→数学机制设计;计算定价和拍卖;附加关键词和短语:公布价格,简单拍卖,福利最大化,机制设计ACM参考格式:Tomer Ezra,Michal Feldman,Tim Roughgarden,and Warut Suksompong.2020年。多单位市场定价。ACM Trans.经济Comput. 7,4,第20条(2020年1月),29页。https://doi.org/10.1145/33737151介绍我们考虑的问题,分配相同的项目,以最大限度地提高社会福利的目标代理有一些相同的项目,每个代理人都有一个估值,描述她的价值为给定数量的项目,我们的目标是计算非负的和整数数量的项目,应分配给每个代理人,以最大限度地提高所有代理人的总价值该问题是多单位拍卖设计的基础,在经典机制设计和算法机制设计领域,无论是在理论上还是在实践中,多单位拍卖都扮演着重要的角色正如任何这项工作得到了欧洲研究理事会(拨款号337122和639945)、以色列科学基金会(拨款号317/17)、美国国家科学基金会(NSF)奖(CCF-1524062和CCF-1813188)以及斯坦福大学研究生奖学金的部分支持。该文章的初步版本发表在2018年12月的第14届网络和互联网经济学会议论文集作者以斯拉,哈代拉32,公寓。12,Petach Tikva 4972629,Israel; email:tomer.ezra@ gmail.com; M.Feldman,布拉瓦特尼克计算机科学学院,检查站大楼(办公室432),特拉维夫大学,邮政编码。39040,Ramat Aviv,TelAviv , Israel; email : mfeldman@post.tau.ac.il; T.Roughgarden , Department of Computer Science , ColumbiaUniversity,500 West 120th Street,Room 450,MC0401,New York,NY 10027,USA; email:tr@cs.columbia.edu;W.Suksompong,计算机科学博士,牛津大学,Wolfson Building,Parks Road,Oxford OX 1 3QD,UK;电子邮件:warut。suksompong@cs.ox.ac.uk.允许免费制作本作品的全部或部分的数字或硬拷贝,以供个人或课堂使用,前提是制作或分发副本的目的不是为了盈利或商业利益,并且副本的第一页上有本声明和完整的引用。必须尊重作者以外的其他人拥有的本作品组件的版权。允许使用学分进行摘要。以其他方式复制、重新发布、在服务器上发布或重新分发到列表,需要事先获得特定许可和/或付费。从permissions@acm.org请求权限。© 2020版权归所有者/作者所有。授权给ACM的出版权。2167-8375/2020/01-ART20 $15.00https://doi.org/10.1145/337371520ACM Transactions on Economics and Computation,卷。号74、第二十条。出版日期:2020年1月二十:2T. Ezra等人福利最大化问题,原则上可以使用VCG机制来解决该问题。在设计和分析更实用的多单位拍 卖 方 面 已 经 做 了 大 量 的 工 作 。 VCG 机 制 有 一 些 间 接 的 实 现 , 最 著 名 的 是Ausubelsubmodular)估值[Ausubel2004]。 算法机制设计中的工作已经确定了这样的机制,其保持VCG机制的主导策略激励兼容性,同时以代理数量和项目数量的对数的时间多项式(而不是数量和项目数量的多项式)运行。代理人和项目),以社会福利的有限损失为代价。事实上,Nisan [2015]认为,算法机制设计领域可以通过多单元拍卖的镜头进行富有成效的观察。在实践中使用的多单位拍卖形式通常牺牲主导策略激励相容性来换取简单和公平;一个典型的例子是米尔顿·弗里德曼(Milton Friedman)提出的统一价格拍卖(见弗里德曼[1991]),并被美国财政部用于出售政府证券。统一价格拍卖并不总是最大化社会福利(例如,因为需求减少),但它们确实承认良好的上述所有机制的一个主要缺点是,它们要求所有代理人同时参与,以协调其分配并遵守供应限制。比如说,在统一价格拍卖中,所有代理人的出价被用于计算每单位市场出清价格,然后该价格确定所有代理人的分配。从我们的日常经验中可以明显看出,在许多不同的市场中,买家的到来和离开是不同步的,他们根据自己的偏好和待售商品的当前价格做出购买决定。1本文的目标是发展理论,解释在市场中,代理人顺序到达而不是同时到达的这种张贴价格的有效性 如何设定价格以实现福利最大化的结果。1.1模型我们考虑一个设计师必须在任何代理商到来之前提前发布价格的设置。我们假设供应量是已知的。设计师被给予关于代理商估价的全部或不完全的信息,然后必须为每个项目设定价格。2代理然后到达一个任意的(最坏情况)的顺序,每个代理采取效用最大化的捆绑(任意打破领带),给定剩余的项目集。这些价格是静态的,因为它们在整个过程中保持固定。实施例1.1. 假设有三个物品和两个代理,每个代理的价值为5,获得一个物品,价值为9,获得两个物品,价值为11,获得所有三个物品,并假设设计师为每个物品定价4。第一个代理将选择一个或两个项目(打破平局任意)。如果第一个代理选择2个项目,那么第二个代理将采取唯一的项目剩余;如果第一个代理选择一个项目,那么第二个代理将采取一个或两个项目。一般来说,我们允许不同的物品获得不同的价格(例如,在这个问题的VCG机制中就是这种情况然而,对于相同的物品,很自然地会关注统一的价格,即每个物品都有相同的价格。一般来说,我们最感兴趣的是统一价格的正结果和非统一价格的负结果[1]对于涉及相同物品的例子,想想普通入场的音乐会门票,Una Pizza Napoletana的比萨饼(面团用完的晚上就关门了),或者IPO股票(除了谷歌[Ritter2014])。[2]如果没有至少部分关于代理人估值的知识,就不可能有非平凡的保证多单位市场二十:3ACM Transactions on Economics and Computation,卷。号74、第二十条。出版日期:2020年1月表1.结果总结(a) 全部信息统一价格非统一价格子模块1(4.7、4.8、4.9)22(4.2,4.3)[2项]3≥5−17m(4.4),≤ 0. 802(4.5)[m个项目]XOS1(8.2)2≤1−1(5.1)e次加1(6.1,6.7)233(6.5,6.9)[2个相同的买家]≤1(6.6)[即使有2个买家]03 -04 -2013(2[2个相同的买家](第46.8段)一般1(7.1)M1(7.2)M(b) 不完全信息统一价格非统一价格XOS1(8.2)2≤1−1(5.1)e次加≥1(8.4)4≤1(6.6)[即使有2个买家]2≤34(6.8)[即使有两个相同的买家]所有结果都是本文的新结果括号中的数字是指相应的定理或命题的编号。参数m表示项目的数量。本文的首要目标是在一系列关于设计者信息和代理人估值的假设下,描述最优社会福利的最大部分,这些福利可以通过公布价格来保证。这一目标本质上是定量的,但我们的研究结果也提供了关于统一和非统一价格的相对力量,不同估值类别的相对难度以及不同信息假设的影响的定性见解。例如,我们证明了在完全信息设置下,在统一价格下,次可加估值比XOS估值更难,而XOS和次模估值同样难(这些估值类的精确定义见第2节)。另一个例子是,虽然不统一的价格可以用来获得更好的保证子模块的估值,这不是一般的估值的情况。1.2我们的结果我们的大部分结果总结在表1中;下面我们重点介绍其中的一个子集。首先,考虑具有XOS代理估值的贝叶斯设置的情况(定义见第2节)。也就是说,每个代理的估值是独立于XOS估值的已知(可能是特定于代理的)分布得出的。Feldman et al. [2015]表明,即使是不相同的物品,张贴的价格总是可以获得至少是最大可能的1/2倍的预期福利。即使对于单个项目和i.i.d.的特殊情况,1/2的因子也是紧的。剂. Feldman等人[2015]使用的公布价格是不统一的,即使结果是专门针对案例的相同物品的价格(物品的价格基于其对最优分配的预期边际贡献,这在物品之间可能会有所不同)。我们在定理8.2中证明了,对于相同的物品,以及具有独立(不一定相同)XOS估值的代理人,统一价格足以实现最优预期福利一半的最佳保证。此外,这个结果还可以推广到任何一类c-接近XOS估值的估值,但损失了一个因子c(定理8.3)。虽然上面的1/ 2近似对于不完全信息设置是严格的,但是在完全信息的情况下,这个问题已经很有趣了,因为买家我们能在1/ 2的近似因子上改进吗?二十:4T. Ezra等人ACM Transactions on Economics and Computation,卷。号74、第二十条。出版日期:2020年1月这个更强的信息假设我们证明,统一价格不能达到一个近似因子优于1/ 2,即使是更严格的类的子模块的估值,甚至有两个代理(命题4.8)或相同的代理(命题4.9)。相反,对于非一致价格(仍然是子模赋值),我们证明了2/ 3的近似是可能的(定理4.2),这又是紧的。接下来我们考虑次可加赋值族,它严格地推广了次模赋值和XOS赋值,并且被认为是禁止补集的最具挑战性的赋值类。例如,对于不相同的物品,不知道标价是否能保证最佳社会福利的一个恒定部分。对于相同的项目,我们证明这确实是可能的。在不完全信息设置(和相同的项目),我们表明,次可加估值是2-接近XOS估值(命题3.4),这导致近似因子为1/ 4(定理8.4)。在完全信息的情况下,我们也可以做得更好:统一价格可以保证最优社会福利的1/3(定理6.1),并且近似是紧密的(命题6.7),而即使是非统一价格也不能保证大于1/ 2的因子,即使只有两个代理人(命题6.6)。在两个相同的代理人的情况下,统一的价格可以保证最优福利的2/ 3(定理6.5),这是紧的(命题6.9)。有了所有这些积极的结果,读者可能会想,是否可以为一般估值提供常数因子保证。不幸的是,情况并非如此。对于一般估值,我们表明,即使在充分信息设置和非统一的价格,即使只有两个代理人和到达顺序是已知的,张贴的价格不能保证超过一个最优社会福利的1/m分数(命题7.1),其中m表示项目数。然而,如果卖方能够控制到货顺序,那么即使统一价格也能保证最优社会福利的一半(定理7.3)。没有更好的界限是可能的,即使对于相同的估值和不统一的价格(命题7.4)。除了结果本身,我们在这篇文章中开发的一个经常性的技术是考虑包含所有代理的边际值的多集,并根据这个多集设置适当的价格。这是一个强大的技术,正如我们在本文中所展示的那样,可以用来在多单位市场定价中获得广泛的保证。例如,将价格设定为略低于或略高于阈值通常是有帮助的,在阈值处,基于边际价值将出售足够的物品。然而,我们还需要仔细选择每种价格出售的商品数量,这有时是一项具有挑战性的任务。对于次模赋值,我们可以直接考虑边际值的多集,因为每个主体对于每个后续项目都有递减的边际然而,对于次可加和一般估值,我们需要处理这些估值的“次模闭包”,它们对应于限制我们估值的最小次模估值。我们相信,这些技术可以是有用的,在一般设置相同的项目得出的结果。1.3其他相关工作简单机构的设计和分析一直是算法机构设计的一个活跃的研究领域,特别是在过去的十年中。这种关注部分是由于在实际情况中高度期望简单的机制。在实践中使用的简单机制的例子是用于在线广告的广义第二价格拍卖(GSP)[Edelman等人,2007; Lucier和PaesLeme,2011; Lucier等人,2012; Paes Leme和Tardos,2010; Varian,2007]和同时物品拍卖(代理人分别和同时对多个物品出价)[Bhawalkar和Roughgarden,2012; Christodoulou等人,2008; Feldman等人,2009]。2013; Hassidim et al.2011年]。这些机制是不真实的,并在平衡评估使用无政府状态的价格措施。公布价格机制可能是实际上最普遍的销售商品的方法。通过简单地公布单个项目的价格,这些机制极其容易多单位市场二十:5ACM Transactions on Economics and Computation,卷。号74、第二十条。出版日期:2020年1月→≥∈≤⊆∅|∪−i=1≥≥去理解和参与。因此,不应该感到惊讶的是,公布的价格机制已被广泛研究的各种目标函数(例如,福利、收入、完工时间),价值的信息结构(例如,全信息、贝叶斯、在线),以及评估类(例如,单元需求、子模块化、XOS)。例如,一长串的工作集中在收入最大化的顺序公布价格上,并且已经表明,除其他外,一种形式的公布价格机制可以为具有单位需求估值的代理人实现最优收入的恒定部分[Chawla et al.2007,2010 a,2010 b]。还研究了单个项目的序列公布价格的收入最大化,无论是在大型市场[Blumrosen andHolenstein2008]还是在分布未知的情况下[Babaioff et al.2011],对于加法估值[Babaioff etal.2014; Bateni et al.2015],以及对于有补充的买家[Eden et al.2017]。Dütting等人[2017]为公布价格机制提供了一个总体框架在其中的一些作品中,允许采用公布价格机制来区分代理人,并为每个代理人设定不同的价格相反,在这项工作中,我们不考虑歧视性价格。与我们的工作相关的另一个研究方向是考虑市场均衡,例如,瓦尔拉斯价格所实现的市场均衡关于Kelso Jr.Crawford [1982]指出,对于总替代估价类,总是存在瓦尔拉斯均衡,这意味着人们可以为物品分配价格,以实现最佳社会福利。然而,这一结果是基于代理人以特定方式打破关系的假设因此,瓦尔拉斯价格的存在并不能将福利保证转移到我们的设定中,即使是对于单位需求估值。我们认为,在我们的环境中,我们采取的最坏情况的观点更现实,我们无法控制代理人如何打破关系。除了上述工作之外,一项新的研究还考虑了在线设置中的动态发布价格,例如k服务器和停车问题[Cohen et al.2015]。此外,在匹配市场中福利最大化的背景下研究了公布价格机制,其中价格是动态的可以在机制过程中发生变化),但不取决于药物的特性[Cohen-Addad et al.2016]。对于静态价格,最近的研究表明,在完全信息设置下,使用二进制单位需求估值,可以实现严格超过一半的福利[Eden et al. 2018年]。在发布价格机制中考虑的代理的顺序到达适合在线机制的框架,该机制处理具有多个代理的动态环境,这些代理具有私有信息[Babaioff et al.2015; Hajiaghayi et al.2004;Parkes2007]。我们的工作表明,对于相同的物品和代理商与次加性估值,张贴的价格可以保证一个恒定的福利比例,即使设置(统一)的价格在前面。2预赛我们考虑一个设置与一组M的m个相同的项目和一组N的n个买家。每个买家都有一个估值vi:2M 表示他对每一组项目的价值。由于物品是相同的,估价只取决于物品的数量。我们假设估值是非递减的(即,v i(T) v i(S)for T S)和归一化(即,vi()=0)。我们使用v i(S T)=v i(ST)vi(T)表示给定丛T的丛S的边际值。买方估价简档由v=(v1,.,v n)。分配是不相交集合x=(x1,. .,xn),其中xi表示与买方i相关联的捆绑[n]注意:不需要分配所有项目)。与估值一样,由于我们考虑相同的项目,分配可以由分配给每个购买者的物品的数量来表示社会福利(SW),其中阳离子x是SW(x,v)=。n vi(xi),最优社会福利由下式确定:被占领土㈤。当从上下文中清楚时,我们省略v,分别写SW和OPT为社会福利和最优社会福利对于两个赋值v,vJ,我们说vvJ当且仅当v(S)vJ(S)对每个集合S。Lehmann etal.给出了无补赋值的层次结构[2006年]。二十:6T. Ezra等人ACM Transactions on Economics and Computation,卷。号74、第二十条。出版日期:2020年1月.∈J{}→≥⊆||||图1.一、属于定义2.3中不同类别的估值示例。赋值v1是加法的,v2是次模的,v3是XOS的,v4是次加法的。除了v1之外的每个赋值都不属于它的类之下的任何定义2.1. 一个估值v是• 如果v(S)=i,则可加 Sv({i})对于每个集合S M。• 次模的,如果v({i}|S)≥v({i}|T),且设S,T使得S <$T<$M。• XOS如果存在加法赋值v1,. ,v k,使得v(S)= max j=1,.,kv j(S),对于每个集合S∈ M。• 次可加的,如果对任意集合S,T<$M,v(S)+v(T)≥v(S<$T)。由于我们在整篇文章中假设所有项目都是相同的,所以我们只处理相同项目的估值。定义2.2.一 个赋值v被称为是对相同项的赋值,如果对于每个集合S,T,M,v(S)= v(T),使得S=T。因此,对相同项目的估价可以用非递减估价v:0,1,.表示。,mR0,它为[ m ]中的任何整数分配一个非负实值(回想v(0)= 0,因为我们假设归一化赋值)。除非另有说明,本文中的所有估值均假定为同一项目的估值。在下文中,我们调整了定义2.1中的加法、次模、XOS和次加法赋值的定义,以适应对相同项目赋值的情况。XOS估值的简化定义来自XOS和分数次可加性之间的等价性[Feige2009]。定义2.3. 对相同项目v的估值被称为• 可加的,如果v(i)=a·i,对于任意整数0≤i≤m,对于某个常数a。• 子模的,如果对每个整数1≤i≤m− 1,v(i)−v(i− 1)≥v(i+ 1)−v(i)• XOS,如果对任意整数1≤ij≤m,v(i)≥ i·v(j)<。• 次可加的,如果对任意整数1≤i,j≤m,其中i+j≤m,v(i)+v(j)≥v(i+j)。属于这些类别的估值示例见图1。我们假设特工是按顺序到达的。我们将在大多数情况下为物品设定静态价格,每个到达的代理人从剩余物品中拿走一捆,使她的效用最大化,并任意打破关系。对于某些结果,我们将假设动态价格,即,卖方可以为每次迭代的剩余物品设置新的价格(但不知道哪个代理将多单位市场二十:7ACM Transactions on Economics and Computation,卷。号74、第二十条。出版日期:2020年1月.|− ∈|−∈≥≥JJ--ˆ ˆˆ{−− |{\fn方正粗倩简体\fs12\b1\bord1\shad1\3cH2F2F2F}J·j≥iKJJ我JJv是次模, vvvvvv下一篇) 如果价格p =(p1,. ,p m)是在m个物品上设置的,并且代理人购买其中的子集S,则她的效用由v(S)iSp i给出。对于本文的大部分内容,我们将假设代理的到达顺序是未知的,但我们也将考虑我们知道此顺序或我们甚至可以控制顺序的设置我们感兴趣的社会福利,我们可以通过设置价格相比,最优的社会福利方面的最坏的情况下到达顺序。给定一个买方估值概况,子模块估值为v1,... ,v n,我们通常会考虑多重集V=v i(j)v i(j 1)i [n],j [m],它由所有买家和物品的所有边际值组成。设δ是V中任意两个值之间的最小正差,且令δ=δ/2。请注意,最优分配是以非递增顺序对V中的边际值进行排序,并以该顺序分配项目因此,OPT是V中m个最高边际值的和。对于每个值x,设G(x)是V中严格大于x的边缘值的数量,设E(x)是V中等于x的边缘值的数量。不失一般性,我们将假设G(0)m,因为否则我们可以通过将所有价格设置为0来获得最优社会福利,这保证了所有产生正边际效用的G(0)产品都被出售。设b是满足G(b)m和G(b)+E(b)m的唯一值.<令mJ=G(b);即,mJ是严格大于b的边际值的个数。实施例2.1. 假设m = 3,有两个代理人。第一个代理人的估值为v(1)= 5,v(2)= 9,v(3)= 11,而第二个代理的估值为v(1)= 2,v(2)= 4,v(3)= 5。然后我们有V = 5,4,2,2,1,δ = 1,且δ = 0。5. 最优福利是11(通过将所有三个项目分配给第一个代理,或者将两个项目分配给第一个代理,将一个项目分配给第二个代理来获得)。此外,我们有G(2)= 2,E(2)= 3,b=2,并且mJ=G(2)= 2。3恒等项在本节中,我们考虑相同项目的估值性质。除了它们本身的有趣性之外,这些性质以后还将帮助我们为标价建立福利保证(定理8.4)。首先,我们证明了(在相同项上的)每个赋值都有唯一的极小XOS赋值和唯一的极小子模赋值,后者有时被称为前者赋值的我在3.1上。设v是有界整环上的一个赋值,设 v∈v∈ v ∈(i)=max j≥ii·v(j)。则v∈ XOS,v ∈ ≥ v,且对于每个XOS赋值v使得v ≥ v,我们有v ≥ v ∈。PR oF.我们首先证明v是一个XOS估值。通过定义2.3,足以证明,对于任何i,j,使得ij,v∈(i)≥i·v ∈(j)成立。<设i,j是这样的,使得i,j。<我们知道存在k≥j,使得v∈(j)=j·v(k),根据v∈的定义,因此v∈(i)≥i·v(k)=K Ki·k·v(j)= i·v(j),根据需要。 它保持v <$i ≥ v,因为对所有i,v <$i(i)≥ i·v(i)。现在,设v是一个XOS估值,使得v v,设i m。令j = argmaxi v(j)。我们有v(j)≥v(j),并且由定义2.3,v(i)≥i·v(j)≥i·v(j)=v(i),这是已知的.□我在3.2上。设v是有界整环上的一个赋值,设 v_i是赋值v_i(i)=max j≥i,k≤i(i−k·(v(j)− v(k))+v(k))(当j = i = k时,最大值的表达式是v(i))。然后吉克并且对于每个亚模赋值,使得,我们有≥。PR oF. 我们首先证明v是一个子模赋值。为此,我们提出了一种另类的方式来定义v,使其子模块清晰。在图上画出所有i∈[m]的点(i,v(i)),并定义vJ(0)= 0。如果我们已经定义了vJ(j),对于所有j≤i,则考虑最小k>iv二十:8T. Ezra等人ACM Transactions on Economics and Computation,卷。号74、第二十条。出版日期:2020年1月≤≥ ≥∈j−ks-r∈V∈V ≤≤V Vj≤i,k≥iv(j)+(v(k)−v(j))·i−j。 我们有v_(r)≥v(r)和v_(s)≥v(s). 在这之前,s-rs-rs-r−图二、一个赋值v及其XOS和子模闭包的例子,如命题3.1和3.2所构造的。v的XOS闭包用vXOS表示,它的子模闭包用vsubmod表示。使得v的任何点都不严格位于连接(i,v(i))和(k,v(k))的直线上方。对于所有j,ij k,定义vJ(j),使得点(j,vJ(j))位于这条线上。<由于直线的斜率不能在这个过程中增加,所以vJ是次模的。它认为v<$v,因为v<$(i)v(i)对所有i。我们证明,实际上v∈vJ。固定任何i[m],并假设vJ(i)由连接(r,v(r))和(s,v(s))的直线定义,对于某些rs。<我们有vJ(i)=v(r)+(v(s)−v(r))·i−r,所以vJ(i)≤v<$(i)。此外,由于v的所有点都位于或低于这条线,最大的s-r–·达到了和,所以J。现在让v(j)+(v(k))(v(j))k−jj=rk=sv(i)=v(i)argmaxv∈M是满足v∈M≥v且i≤m的任意亚正则赋值. Letr,s=k−jv(i) ≥v(r)+(v(s)−v(r))·i−r=v(r)·s−i+v(s)·i−r≥v(r)·s-i+v(s)·i-r=v(r)+(v(s)-v(r))·i-r=v(i),根据需要s-rs-rS R□赋值及其XOS和子模块闭包的例子可以在图2中找到。我们感兴趣的是用“更简单”的估值来近似估值具体地说,对于两类估值1 2,我们要确定最小常数c,使得对于任何估值v2,都存在一个估值v<$1,使得v v<$cv。我们回答这个问题的每一对从类的subadditive,XOS,和submodular估值,并表明,最好的常数是c=2的所有这些对。(注意,由于所有三个类都在标量下是封闭的,乘法,上面的不等式v≤v≤cv也可以用v/c≤v≤v代替。我在3.3上写的。 对于每个次可加赋值v,存在一个次模赋值v <$,使得v <$≥v且v<$≤2 ·v。PR oF. 考虑命题3.2中定义的上界v的最小次模赋值v。 对于给定的i,设s,r = argmaxj≥i,k≤ii−k·(v(j)− v(k))+v(k)。它认为v(i)=i−r·(v(s)−v(r))+v(r)多单位市场二十:9ACM Transactions on Economics and Computation,卷。号74、第二十条。出版日期:2020年1月我≤s·(v(s)−v(r))+v(r)二十:T. Ezra等人ACM Transactions on Economics and Computation,卷。号74、第二十条。出版日期:2020年1月42−14+14+1S2如果我S我SS我S我4如果i∈{4,.,42}+1L+1我≤s·(v(i·我≤s·(≤i.. s +1<$·v(i)− v(r)<$+ v(r)我.. s +1<$·v(i)<$+ v(r).1−i≤i.. s +1<$·v(i)<$+ v(i).1−i=2·v(i),其中第二个和最后一个不等式是由v是非减的这一事实得出的,第三个不等式是由v是次加的这一事实得出的。□命题3.3立即产生以下两个结果。我在3.4上。 对于每个次可加赋值v,存在一个XOS赋值 v,使得v ∈ ≥ v和v ∈ ≤ 2·v。我在3.5频道上。 对于每一个XOS赋值v,存在一个子模赋值 v,使得v ∈ ≥ v和v ∈ ≤ 2·v。接下来,我们证明常数2对于所有三对类都是最好的命题3.7直接由命题3.6推导而来。我在3.6上写对每一个0 ≤ c− 1产生所需的结果。□我在3.7上。 对于每一个0 ≤ c得到所需的结果。□多单位市场二十:ACM Transactions on Economics and Computation,卷。号74、第二十条。出版日期:2020年1月我J≥•M−MMM ≥M{}M| {∈}|M−M ≤ MM≤•MM4亚模值在本节中,我们考虑子模赋值。我们首先展示了从次模块化到单位需求估值的减少特别地,我们展示了如何将n个子模块化估值转换为nm个单位需求估值,使得m个项目的每个静态定价都保证单位需求估值的最优社会福利的一个分数ρ,也将保证子模块化估值的最优社会福利的一个分数ρ考虑到这一减少,为了得到4.1节和4.2节中的积极结果,可以不失一般性地假设所有估值都是单位需求。设M是一个有m个商品和n个代理人的市场,每个代理人的价值为vi。设OPT(M)为福利最大化分配的社会福利。同样,给定价格p,设SW(M,p)为市场M在价格p下获得的最坏情况社会福利。4.1. blog 设M是一个有n个代理人的市场,其子模估值为v i在[m]上. 考虑一个有n·m个代理人的市场Mj,记为(i,j),其中i ∈ [n],j ∈ [m],单位需求估值为v j值为v i(j)− v i(j − 1)。以下观点成立:• OPT(M)= OPT(MJ)J• 对于每个定价p,SW(M,p)≥SW(M,p).PR oF. 我们按顺序证明这两部分考虑分配x i的分配 物品交给代理人i. 在J中分配物品给代理人(i,j)的分配,如果jxi产生相同的社会福利,因此OPT() OPT(J)。相反,考虑在j中的分配,其将项目分配给代理集合A=(i1,j1),.,(i m,j m). 中的分配,j:(i,j)A项给代理i至少产生相同的社会福利,因此OPT()OPT()。因此,我们有OPT()=OPT(J)。设σ为市场的最坏订单价格为p的情况下,代理人i依次到达σ(i),且令(x1,.,xn)是产生最坏情况的社会福利的分配。设σJ是市场j的到达顺序,其中agent(i,j)到达回合m(σ(i)) 1)+j。 我们可以检查,当且仅当xi j时,代理(i,j)被分配一个项目的分配是关于到达顺序σJ和定价p的有效分配。这种分配的社会福利是SW(M,p)。因此,SW(M,p)≥SW(MJ,p)。这就完成了证明。□备注。如果所有购买者的边际价值没有联系(事实上,第m个最高边际价值与第(m+1)个最高边际价值不同就足够了),那么通过将所有价格设定为b,可以实现最优社会福利,其中b和b的定义见第2节。然而,正如我们所看到的(例如,在命题4.3),边际价值联系可以导致福利从公布的价格显着下降。4.1非统一定价我们首先表明,我们可以获得2/ 3的最优福利的子模块化的估值,如果我们被允许设置非统一的价格。第4.2章. 对于每一个具有次模块化估值的市场,都存在一个静态的项目定价p至少保证三分之二的最优社会福利。PR oF.通过引理4 - 1,我们可以充分地说明具有单位需求估值的购买者的结果。如第2节所述定义b、m、J和m。考虑以下定价结构:二十:T. Ezra等人ACM Transactions on Economics and Computation,卷。号74、第二十条。出版日期:2020年1月–{−−−≤≤–––(P1)对所有项目设定b−1(P2)对M-MJ个项目设置b-1/2的价格,并对mj个项目设置b+1/2我们声称,这些定价结构的最大值至少为OPT 2/ 3在定价(P1)下,所有m个物品都将被出售,并且每个物品的边际价值至少为b;因此,至少有百万美元的社会福利得到保证。我们接下来证明定价(P2)保证至少max OPT(mmJ)b,OPTmJb的 社 会 福 利 。第一个观察结果是,每一个价值大于b的买家都会购买一件商品。这是因为当买家到达时,至少有一个价格为b+b的物品可用(最初有mJ个这样的物品,其他买家最多可以购买其中的mJ-1个),并且一个物品对她来说价值超过b+b。因此,这些项目的社会福利至少为OPT−(M-MJ)b。这也意味着定价下的社会福利(P2)至少为OPT−(M-MJ)b。第二个观察结果是,至少有m-2mJ件商品会被出售,这些商品的价值恰好为b。(Itm−2mJ可能为负,但这并不影响我们的分析。这是因为所有价格为bJ−k的m−mJ个物品都将被出售(因为这些物品是最便宜的物品,需求至少为m),并且m-mj个项目中至多有m个项目将产生大于B卖的时候因此,这些项目的社会福利至少为(m2mJ)b.由于第一次和第二次观察中考虑的项目集是不相交的,因此(P2)获得的总社会福利至少是它们的总和,即OPT(m)mJ)b+(m2 mJ)b=OPTMJ湾因此,定价下的社会福利(P2)至少是最大OPT (m) mJ)b,OPTB、如所述。定价保证(P1)和两个定价保证(P2)的平均值则为(mb+OPT(m mJ)b+OPTmJb)/3= 2OPT/ 3。因此,这两种定价结构中最好的给社会福利至少2 OPT/3。□下面的命题表明这个界是紧的。我在4.3上写 存在两个物品和两个购买者的市场,具有次模估值,使得每个静态定价可以保证最多2/3的最优社会福利。PR oF.考虑一个有两个物品和两个买家的市场,其估值如下:买家1的单位需求估值为每个物品的价值2。买方2具有每个物品的价值为1最优福利是OPT=3,通过向每个购买者分配单个物品获得我们表明,没有定价可以保证超过2的福利设p=(p1,p2)为某个定价。区分以下情况:(1) 如果p1,p21,那么如果加法购买者先到,她会买下这两样东西,结果社会福利为2.(2) 如果其中一个价格是1,另一个价格>1,那么如果单位需求购买者首先到达,她将购买更便宜的商品。那么添加剂购买者将不会购买任何东西,导致社会福利为2。(3) 如果p1,p2>1,则添加剂购买者将不购买任何物品,因此社会福利不能超过2。这就结束了论证。□命题4.3中的否定结果是在有两个商品的市场中得到的。在下文中,我们证明了当项目数量大时,保证的社会福利更高4.4. 对于每一个具有次模估值的m个商品的市场,存在一个静态商品定价p,它保证至少5/7 - 1/m的最优社会福利。多单位市场二十:ACM Transactions on Economics and Computation,卷。号74、第二十条。出版日期:2020年1月≥|{∈|联系我们|−.J]12i≤m/2].−−.−−≤........≤≥PR oF. 通过引理4 - 1,我们可以充分地说明具有单位需求估值的购买者的结果定义V、b、m、J和m,如第2节所述。另外,设k=x V x2b。回想一下,OPT是V中m个最高值的总和,因此是OPT mb。设f(i,V)是返回多重集V中第i个最高值的函数。设α1是V中最高mJ/2值之和(即,α=f(i,V)),令α为剩余的“m j / 2个值(i. 例如,α2=m J/2]
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- C++标准程序库:权威指南
- Java解惑:奇数判断误区与改进方法
- C++编程必读:20种设计模式详解与实战
- LM3S8962微控制器数据手册
- 51单片机C语言实战教程:从入门到精通
- Spring3.0权威指南:JavaEE6实战
- Win32多线程程序设计详解
- Lucene2.9.1开发全攻略:从环境配置到索引创建
- 内存虚拟硬盘技术:提升电脑速度的秘密武器
- Java操作数据库:保存与显示图片到数据库及页面
- ISO14001:2004环境管理体系要求详解
- ShopExV4.8二次开发详解
- 企业形象与产品推广一站式网站建设技术方案揭秘
- Shopex二次开发:触发器与控制器重定向技术详解
- FPGA开发实战指南:创新设计与进阶技巧
- ShopExV4.8二次开发入门:解决升级问题与功能扩展
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功