精华内容
下载资源
问答
  • 我国辅助服务补偿机制市场化——从配合计划机制到现货市场 回顾我国辅助服务补偿机制建设工作,现行全国性辅助服务补偿机制酝酿于2004年,《并网发电厂辅助服务管理暂行办法》出台于2006年,各区域实施细则印发于...

    我国辅助服务补偿机制与市场化——从配合计划机制到现货市场

    回顾我国辅助服务补偿机制建设工作,现行全国性辅助服务补偿机制酝酿于2004年,《并网发电厂辅助服务管理暂行办法》出台于2006年,各区域实施细则印发于2009年,全国范围内落地1于2010年前后。该机制立足于计划体制下的电量分配机制,本质为发电侧辅助服务补偿机制,主要辅助服务品种包括调频(AGC)、调峰、无功、备用、黑启动等五种。2013年,东北地区出现了以竞价方式确定调峰承担主体的尝试。2015年中发9号文印发后,以竞价方式确定承担主体的调峰辅助服务补偿机制,被国内部分地区定义为“辅助服务市场2”的主要内容,尝试先于电能量市场建设“辅助服务市场”。实质上,现有的“辅助服务市场”试点,总体仍是辅助服务补偿机制,并未形成电能量市场化背景下的辅助服务市场化交易。未来的辅助服务市场建设,仍需要服从于电力现货市场建设,对辅助服务补偿机制进行“脱胎换骨”的改革。

    1、来路崎岖与效果明显

    我国辅助服务补偿机制的由来,与上轮电力体制改革密切相关。2002年,国发5号文推动厂网分开改革,对于新生的原国家电监会,从何处入手建立厂网界面的经济关系和监管制度缺乏直接经验可以借鉴。厂网分开两年后,原国家电监会组织了“厂网间突出问题调研”,这次调研覆盖了全国大部分省(区、市)电力企业,成为了原国家电监会为期近十年厂网界面监管工作的前奏,工作成果包括后续出台的辅助服务补偿机制、厂网间电费结算制度、信息披露与报送制度、电力调度与交易监管机制等。当时建立辅助服务补偿机制的初衷,是为了解决调研发现的辅助服务相关的两方面问题,一是电网企业以“喂鸡还需一把米”名义3保留的调峰调频专用机组承担辅助服务较少,主要从事发电业务盈利;二是各独立发电企业承担的辅助服务任务量苦乐不均,有“鞭打快牛”之嫌,以及与调度机构“远近亲疏”之分,独立发电企业意见较大。对于电网企业保留的调峰调频机组利用不充分问题,原国家电监会提出的解决办法分远近两个措施,近期措施是加强监管,要求电网企业保留机组必须在“第一顺位”无偿、优质的提供调峰调频服务,远期措施是剥离电网企业拥有的常规机组。对于发电企业之间辅助服务方面的“鞭快”与“亲疏”问题,原国家电监会有关部门认为属于公平问题,需要建立一套机制,即辅助服务补偿机制。

    今天看来似乎发电侧的辅助服务补偿机制顺理成章,倒退15年,辅助服务在国内连具体、权威的概念都没有,方方面面顾虑重重。设计者需要回答好电力调度机构、电力企业和价格管理部门的问题,才能实现“设计闭环”。

    首先是是否改变调用辅助服务的方式?由于电力调度机构承担全部安全责任,电力调度机构认为不能干预调度人员的决策过程。设计者考虑到当时电量计划分配、计划调度的机制没有变化(没有电力现货市场),建立辅助服务补偿机制如给调度人员额外增加压力,安全责任无法厘清,同时对解决问题也没有直接好处。因此,辅助服务补偿机制被设计为事后的经济补偿,不影响电力调度机构“按需调用”4。

    其次是谁来出钱?道理上讲,辅助服务成本是电力成本的一部分,“羊毛出在羊身上”,自然而然应当用户承担,但是原国家电监会并没有调整用户侧电价的职能,如想迅速推开,只能是电力企业暂时承担。其中,电网企业明确表示不承担(无出处),考虑到辅助服务补偿机制当时最为紧迫的是解决发电企业之间提供辅助服务的公平性问题,经与主要发电企业协商一致,暂时由发电企业承担。这种做法的立论形成了一个当时主要发电企业认可的假设:“目前核价体系没有明确是否考虑辅助服务成本进入上网电价,那么也可以粗略认为所有电源的核价都考虑了一定比例辅助成本,所以多干活的机组应当拿钱,没干活或少干活的机组把这个比例的电价拿出来”。

    最后是如何为辅助服务定价和限价?辅助服务补偿机制在一定程度上是为辅助服务定价,就是确定电价的一部分,而电价管理职能一直属于国家价格主管部门,也不在原国家电监会手中。当时国内刚刚开始推行标杆电价体系,经过协商,价格主管部门同意按照补偿一定辅助服务成本的原则5来定价,由原国家电监会派出机构提出标准,主要发电企业讨论同意的方式6(“集合侃价”)确定补偿标准,“以支定收”由发电企业按照上网电量(或电费)进行分摊,但是为保证对标杆电价不产生大的影响,辅助服务补偿的总费用(上限)不得高于当地总上网电费的1.5%。

    从当时情况看,不得不说辅助服务补偿机制是一个设计精妙又接地气的经济制度,用户侧电价没有发生改变,电网企业由于没有经济利益,积极发挥自身在行业内的影响力协助推动,力度合适的补偿标准让发电企业之间实现了公平,解决了“鞭快”和“亲疏”的问题。对辅助服务补偿机制评价最高的是电力调度工作人员,认为该制度减轻了调度人员的工作压力,调动了发电企业提供辅助服务的积极性,机组通过改造切实提高了系统安全稳定运行的能力。

    截至目前,各地“辅助服务市场建设试点”基本上7没有脱离上述辅助服务补偿机制的主要机理,费用仍取自发电企业,主要的改良在于个别品种(主要是调峰和调频)不再按照性能排序调用,而是划定性能范围,在性能范围内按照价格由低到高调用机组,但在为保证安全的情况下,仍然可以按需调度,只是按需调度不再是首选原则。

    2、先天不足与适用局限

    辅助服务补偿机制主要用于解决当时“厂网间突出问题调研”发现的实际问题,取得了切实的成绩,但是由于受到当时条件的限制,存在三方面先天不足,并且随着中国电源结构的快速变化,这些不足越发凸显:

    一是应承担辅助服务义务的电源类型覆盖不全。《并网发电厂辅助服务暂行办法》起草工作所处时期,我国非水可再生能源在电源结构中的占比微乎其微,“鞭快”与“亲疏”的问题又主要存在于火电和水电企业之中,所以顶层设计是围绕火电和水电展开的,对于其他类型电源并没有考虑(适用范围未涉及)。虽然在各区域细则实施的过程中,部分地区已陆陆续续将其他类型电源列入分摊范围,但是由于顶层设计未加以考虑,出现了很多实施过程难以解决的问题。其中最为突出的就是有偿服务和无偿服务的划分标准问题,现行补偿机制只考虑火电和水电机组参与辅助服务的情况下,有偿和无偿的“门槛值”是按照是否引起(水火发电)成本的变化予以区分的,而如果统筹考虑各类型机组均有辅助服务责任,应是各类型机组提供辅助服务能力最弱者的能力上限作为统一的有偿服务起点。门槛值划分的不合理,造成无调节能力机组无偿享受了部分有调节能力机组的辅助服务。具体反映在部分地区,某一辅助服务的度电价格,竟然远远高于消纳可再生能源(假定的辅助服务对象)全口径度电价格8。更大的麻烦是,长此以往可能会进一步加剧不惜代价消纳可再生能源的做法,使经济性消纳变成了“浪费型”消纳。

    二是同一调度关系不同经营关系的主体覆盖不全。辅助服务补偿机制的费用分摊随各电厂上网电费结算进行同步分摊,公用电厂上网电费均由电网企业结算,可以分摊的到辅助服务费用,而自备电厂的情况就要复杂得多。辅助服务补偿机制设计阶段,自备电厂没有蓬勃发展,大部分自备电厂装机容量较公用电厂小,并且拥有自备电厂的用户用电量大于拥有自备电厂的发电能力,造成绝大部分自备电厂没有上网电费结算,电网企业无法直接得到自备电厂的分摊费用,因此同一调度关系的自备电厂并未纳入辅助服务补偿机制,仅山西省进行过自备电厂分摊费用(要求电网代付)的短期尝试。

    三是不同调度关系而同一消纳市场的主体覆盖不全。厂网分开之初,跨省跨区电量主要以国家指令计划为主。辅助服务补偿机制设计阶段曾设想将跨省跨区电量一步纳入辅助服务费用分摊。当时主要的跨省跨区电源企业持反对意见,提出因其大部分电量为多省分电,且电价形成机制与省内电价形成机制不同,为受电省标杆电价倒推,应暂时不参加。跨省跨区电量中的跨区电量,主要通过直流输电通道输送,发电企业的大部分辅助服务只能提供给接入端的交流电网,电源企业确实仅能对受电地区的辅助服务承担经济责任。为加快推进辅助服务补偿机制建设,减少出台难度,《并网发电厂辅助服务管理暂行办法》未将跨省跨区电量应承担的辅助服务义务作为规范的重点。虽然后续国家能源局曾经以国能综监管〔2014〕456号文,印发《积极推进跨省区辅助服务机制建设工作的通知》,要求将跨省跨区电量纳入受电地区的辅助服务补偿机制,即跨省跨区消纳电源应承担受端省份辅助服务费用分摊,在送端交流网内提供的辅助服务可以获得与送端电网内电源相同标准的辅助服务补偿,但在具体实践中,仅苏浙沪三地在部分跨省跨区电量上予以落实。随着跨省跨区电量越来越大,受端省份辅助服务压力越来越大,矛盾越来越突出。

    四是仅考虑发电侧辅助服务使辅助服务的经济调用缺乏激励机制。辅助服务补偿机制要求发电侧具备调节能力的机组承担物理提供辅助服务的义务,要大部分发电机组承担辅助服务的经济责任9,但未明确如何量化衡量电力调度机构使用辅助服务的效率,包括使用辅助服务的成本是否能够小于消纳不稳定电源带来的红利。其实,在辅助服务补偿机制设计过程中,原国家电监会确定了“可计量、可监管、可交易”的三步走战略,即首先建立辅助服务是商品的概念,解决计量问题,然后摸索监管的激励相容方式,确定辅助服务使用总量与成本方面对电力调度机构的约束激励指标,最后配合电能量市场化建立辅助服务市场。遗憾的是受到机构更迭影响,原国家电监会的工作仅完成了第一步“可计量”,也就是今天看到的辅助服务补偿机制(“市场”)。电力调度机构使用辅助服务不受任何的经济限制和总量监管,缺乏提高使用效率、降低辅助服务总成本的动力。

    除了受当时条件制约以及机构改革,造成“三步走”计划停滞,而使现有的辅助服务补偿机制存在先天缺欠以外,新一轮电改使补偿机制的部分基础性条件10发生了改变。2006年,上一轮电改已经遇到瓶颈,区域电能量市场踟蹰不前,辅助服务补偿机制出台时的背景,已经由基于电能量市场化彻底改为基于计划的电量分配制度。各区域细则制定过程中,组织者近乎“挥泪”否定了当时华东区域提出的考虑电能量机会成本辅助服务定价机制,从后事看当时的判断是正确的,因为电能量市场的建设停滞了将近十年。正因如此,辅助服务补偿机制在新电改背景下,表现出多个亟需调整的方面:

    一是辅助服务补偿机制在电力直接交易开展后需要考虑容量备用服务。原有计划体制采用分配电量,同等类型机组利用小时数基本相同,发电机组轮流停机备用,容量备用(冷备用)服务不需要考虑在当时的辅助服务品种当中。因此,现行辅助服务补偿机制除南方区域部分涉及外,其他均未考虑容量备用辅助服务问题。电力直接交易开展后,发电机组之间由于成本不同,竞争中所处地位自然不同,优势机组与劣势机组利用小时数差距将越来越大,而利用小时数低的机组并不能退出运行,因为年度大负荷期间仍然需要这部分容量提供电力,所以这部分机组虽然电量减少,却用大量时间提供容量备用服务,该种辅助服务往往是最贵的辅助服务11。在水电较多送出地区,火电企业生存困难的核心原因之一,就是火电企业为水电企业丰枯季节或特枯年容量备用辅助服务费用没有得到补偿,而这恰恰应当是火电企业(能够列入开机组合)在水电富集地区“活下去、活的好”的合理收益。在受电地区,如果计及当地(由于外来水电丰枯引起)的容量备用费用(目前表现为燃机容量电费),远程输送丰枯出力差异明显的水电经济性会大打折扣。

    二是上网电价的放开使辅助服务补偿机制由发电企业承担的前置假设不再存在。随着上网电价逐步放开,发电侧承担辅助服务费用立论的假设(标杆电价体系考虑了一定比例的辅助服务成本)已经逐渐不存在。实际交易中,发用双方协商形成的电价确实均未考虑辅助服务费用。从经济学来讲,不论辅助服务的成本如何、费用高低,都应当由电力用户承担辅助服务费用。然而,部分地区不断加大发电企业承担辅助服务费用的力度,甚至部分用户提供可中断负荷服务也希望向发电企业收取费用,脱离了当时这个机制建立的边界条件。反对全部辅助服务费用都由用户承担的观点中,有一部分认为可再生能源也消耗了辅助服务,所以应当和用户一起承担辅助服务费用,这种观点偏颇之处在于,用户使用了占比更高的可再生能源,自然应当为此支付相应的费用,既应该包括可再生能源的电能量价格,也应该包括使用这些可再生能源需要的辅助服务费用。另一部分观点认为个别国家现代电力市场环境下,部分辅助服务品种的费用仍由发电企业按上网电量分担,经分析会发现这些国家均采用单边现货市场模式,由于其现货市场中用户为价格接受者,发电企业将度电辅助服务成本自然而然随电能量报价转移到了用户侧。

    三是电力现货市场条件下辅助服务品种相对补偿机制的辅助服务品种和定价方式发生很大改变。电力现货市场配套的辅助服务机制,通常主要品种为调频和备用,调频的价格将包括调频里程的价格和调频服务被调用引发的电量变化(按当时现货价格结算),备用价格将包括备用服务本身以及提供备用时段损失的机会成本(按当时现货价格计算),没有电力现货市场,调频服务引发的电量变化和备用时段损失的机会成本无法准确定价,不能准确定价自然调频和备用服务就无法真正市场化。从这个意义上来讲,真正的辅助服务市场化需要以现货市场建设为前置条件。另外,电力现货市场条件下,分散式市场要求发用双方保持发用功率曲线一致,集中式市场如发电机组不愿停机,随着低谷供大于求,价格一路降低,总有一个低价位让承受不了损失的机组降到足够低的功率,因此,与电力现货市场配套的辅助服务机制不需要调峰辅助服务。换句话说,从经济学上讲,电力交易进行过程中,某一主体的货(电)卖不出去,自然就不被允许生产出来,市场环境下何来的电力调峰呢?

    3、前路艰辛与秉道直行

    展望辅助服务机制的未来,到底如何走向市场化?回答这个问题,恐怕还是要回到辅助服务的定义上来,按照原国家电监会电监市场〔2006〕43号文12的定义:“辅助服务是指为维护电力系统的安全稳定运行,保证电能质量,除正常电能生产、输送、使用外,由发电企业、电网经营企业和电力用户提供的服务”,由这个定义能够清楚地知道,辅助服务的定义采用相对定义法,即需要定义正常的电能生产(输送、使用),才能确定辅助服务的含义;定义了正常的电能生产组织形式变化(由计划到市场),才能定义辅助服务的生产组织形式变化(由计划到市场)。因此,现代电力市场语境下的辅助服务市场化一定以电力现货市场建设为前提条件,即电力现货市场初期可能暂时沿用辅助服务补偿机制13,但真正的辅助服务市场却不能先于电力现货市场建设成功。从电力现货市场机制建设的情况来看,现代电力市场体系建设需要大量的时间和努力,中近期电力现货市场建设仍将以试点为主,在这些试点地区,辅助服务补偿机制将配合电力现货交易机制建设进行市场化;同时,部分地区在很长的一段时期内并不能完全具备建设电力现货市场为核心的现代电力市场体系的条件,“计划调度+直接交易”的计划改良模式还将长期在我国部分地区存在,受该模式影响,辅助服务补偿机制也将在非电力现货市场试点地区继续完善和改良。不论如何,可以肯定的是,辅助服务的经济机制是各地电力系统运营机制都不可或缺的,在下一步的工作中应抓紧按照所在地区所处市场建设阶段开展工作。

    一是把握窗口期尽快随着发用电计划放开将辅助服务费用疏导到用户侧。十几年前机制设计规定发电企业暂时承担,一承担就是十几年,随着无调节能力电源快速发展,居民和三产用电快速上升,辅助服务费用越来越高,但是发电企业却感觉辅助服务成本没有得到补偿,仍在呼吁提高辅助服务付费标准。这种怪现象究其根源是辅助服务的费用出在了发电身上。由于发电侧出钱、发电侧干活拿钱,类似“朝三暮四”的发电侧“零和游戏”,造成全国性的发电集团基本上没有绝对收益的感觉,因为很可能旗下甲电厂赚的就是自己旗下乙电厂的钱;同时,由于是发电企业承担辅助服务费用,新技术和新主体提供辅助服务都需要挂上一个发电企业的“户头”,否则没资格参加“游戏”。例如,世界上的化学储能电站都是独立接受调度指令参加辅助服务市场,而我国参与调频服务的化学储能电站全部是建设在发电企业内部,采用“机组-化学储能”联合调频,这样的“世界独创”并不代表创新,而是为了“落户口才嫁人”。“暂时性”的费用承担方安排,造成化学储能电站无法按照最优的技术模式(独立调度)提供调频服务。“寄生”模式虽然为新技术提供了发展渠道,但也同时在一定程度上限制了其快速发展的可能。特别要强调的是,目前是将辅助服务费用转移到负荷侧的最佳窗口期。辅助服务费用很类似房屋买卖的中介费,买方市场时一定是卖方承担(买房者承担中介费),卖方市场时一定是买方承担。今后一段时间,我们的电力市场仍处于买方市场(供大于求),辅助服务费用疏导(向用户侧)后,用户在绝对电价感受方面,不会感受到电价因计入辅助服务费用而发生上升,可是一旦供需恢复平衡或者局部时段局部地区紧张,则用户直接感受到的就是涨价,疏导的难度会大大增加。

    二是非现货试点地区继续深入完善已有的辅助服务补偿机制。已经印发的相关辅助服务补偿机制的文件,总体上看前瞻性、拓展性较好,大部分内容仍然适用。目前辅助服务补偿机制建设历经了十几年风雨,行业内为之付出了很多心血,对于已经成型的体系不应轻易做大的调整,但是深入完善工作必不可少。首先,水火风核等各类型机组、公用和自备多种资产形式机组应都纳入辅助服务补偿机制,采用各类型、各资产形式电源在同一补偿账户参与辅助服务补偿机制;将辅助服务补偿账户与并网运行管理账户分开设置,改变“辅助服务由考核引发”的错误概念;尽快将外来电全部纳入受入电网辅助服务补偿机制,外来电享受“特权”实质上也容易增强省间壁垒,通过承担应承担的义务,更有益于扩大省间交易,实现远程来电的“经济性消纳”。其次,将各类型机组中调节能力最差的机组辅助服务水平作为有偿辅助服务的起点,实现不同类型机组辅助服务提供能力衡量上的公平,并通过深入研究,科学确定有偿辅助服务计量公式,在现货市场建立前,引入对系统影响效果或性能参数,使发电机组提供的辅助服务能充分反映其每次动作对系统的连续性影响,将对系统影响的好坏“感性评价”进行量化计算,精确反映提供辅助服务的价值,才能在“干与不干不一样”的基础上解决“干好干坏一个样”的问题。再次,尽快引入容量备用辅助服务项目,让提供容量备用的机组获得其合理合法的收益。目前阶段,容量备用服务应当限制于可以调节机组,主要是火电和具备年调节能力的水电,并且要求该部分火电能够列入年度或多年年度机组组合,对于不能列入的部分机组不予补偿(因其属于过剩产能)。最后,条件合适的前提下可以尝试目前通过竞价选择辅助服务承担主体的“类辅助服务市场”模式,这里的条件合适是指通过竞价选择辅助服务承担主体能够降低该项目的辅助服务费用,如采用了竞价方式大幅增加该项目辅助服务总费用,那句“市场就是涨价”的玩笑话不是一语成谶?

    三是现货试点地区应按照电力现货交易的需要设计辅助服务机制。首先,要正确设置电力现货市场环境下的辅助服务交易品种,深度调峰不再作为辅助服务服务补偿机制或辅助服务市场交易内容,市场推动者与设计者要相信价格引导电力平衡的能力。目前,浙江省现货市场详细设计方案直接通过分时电价机制解决峰谷问题,其他已公布的市场详细设计方案均考虑了深度调峰服务,已有现货市场试点方案设计的不同选择,并不能表明调峰可以作为现货市场环境下辅助服务品种。因为不同选择存在的根本原因是,浙江市场是标准的(全部相同调度关系机组)全电量竞价市场,而其他市场详细设计方案采用的是“部分机组计划调度+部分机组全电量竞价”的双轨制模式,由于部分机组计划调度(电力统购统销)仍然存在,所以深度调峰服务难以避免。其次,结合输配电价机制设计等配套政策,设计好电力调度机构使用辅助服务的激励相容机制,建立电力调度机构日前辅助服务总量预测机制,制定辅助服务使用总量和使用效率的量化评价标准,适时引入辅助服务的第三方监管体系,对于低效使用辅助服务产生的不合理费用应由电力调度机构拥有者承担。最后,在采用集中式市场模式的地区,尽早实现调频、备用与电能量的联合优化出清。如分别投标而不是联合优化,用于调频和备用中标的容量不能用于电能量投标,同时调频中标容量不能用于提供备用服务,备用中标容量反之亦然,会造成调频备用容量的冗余,以及三者总成本的非最优。最好的办法还是将电能量、调频、备用进行联合出清,这应该作为集中式市场的目标,即使短期简化,也应给出现货市场和辅助服务市场联合优化的工作日程,用以提高市场效率。

    43号文印发十三年,弹指一挥间,创业艰难百战多。至今,管中窥豹仍然可以看到辅助服务补偿机制建立过程中的不易,看得到设计者、推动者清晰的理念和务实的态度。各区域通过辅助服务补偿机制建设,使辅助服务是可以单独计量电力产品的概念深入人心,为辅助服务的可监管和可交易打下了坚实的基础。相信在未来的辅助服务市场建设过程中,市场设计者们能够坚持现代电力市场体系的基本设计理念和原则,设计出符合当地特点、符合基本市场理论的方案。千里之行始于足下,不积跬步无以至千里,中国的辅助服务市场建设一定能够厚积薄发,配合电力现货市场机制一起优化资源配置,为新时代电力行业的高质量发展保驾护航!

    备注

    1.指真实结算。

    2.本文中未加引号的辅助服务市场和辅助服务交易指国际上通行现代电力市场体系下的辅助服务市场和辅助服务交易,下同。

    3.酝酿厂网分开工作期间,部分观点认为发电企业独立后提供调峰调频积极性可能不高(执行调度指令速度变慢),电网企业需保留一部分调峰调频机组。其中,国家电网保留的常规火电机组后来出售给原神华集团,常规水电与抽水蓄能保留至今。

    4.电力现货市场背景下,辅助服务是在满足安全约束条件下,按照价格从低到高调用,而非调度按照需求(性能最好)调用。

    1. 这条定价原则本身就限制了辅助服务补偿水平。

    6.该方式有别于核定辅助服务电价,被戏称为发电企业“集合侃价”。

    7.华东区域的省间低谷调峰机制本质是低谷发电权转让,更加适合市场化发展方向,已不在辅助服务补偿机制的原有范畴内。

    8.虽然最末一度电辅助服务费用超过该度电(换取的可再生能源最后一度电)的全口径电价(含补贴),但是由于有偿服务的起点很高,可以无偿享用的辅助服务与最末一度电辅助服务费用进行平均尚可接受,本质是部分提供辅助服务的电源(主要为水火电机组)未拿到应得的全部辅助服务费用。

    9.不具备调节能力的机组承担辅助服务经济责任,具备调节能力的机组在提供辅助服务阶段也需要承担辅助服务经济责任。

    10.计划电量分配机制和电能量统购统销机制。

    11.如不采用容量备用辅助服务付费方式,也可以采用大幅提高现货市场限价方式,通过大负荷时段的高电价获得补偿。考虑到我国现阶段很难接受数倍数十倍的大负荷时段电价,所以容量备用辅助服务付费是较为合适的方式。

    12.我国辅助服务概念确立的现行最高效力文件。

    13.为简化电力现货市场建设初期的工作,可以选择停止不适应现货市场需要的辅助服务项目维持补偿机制不变。

    文章转载于《电力决策与舆情参考》2019年3月1日第8期

    展开全文
  • 摘要: 层次分析法,称AHP,被广泛应用于安全科学、环境科学、经济管理等领域。但AHP一旦对准则层进行确定后,将无法更改相关内容一定程度的限制了该方法的应用,即...关键词: AHP、L-D机制、动态拓展、决策机制、信用

    本文已经发表,请详细下载完整版PDF:
    https://www.hanspub.org/journal/PaperInformation.aspx?paperID=31792
    欢迎引用!


    Research on L / D Mechanism based on AHP extension

    Feng Liu1, Xuanxuan Du2, Shiying Lu3
    Wuxi Prithink Information Technology Co., Ltd… Wuxi, China
    Email: lsttoy@163.com

    Abstract:
    Analytic hierarchy process, called AHP, is widely used in safety science, environmental science, economic management and other fields. However, once the AHP alignment layer is determined, it will not be able to change the relevant content to a certain extent limit the application of the method, that is, the AHP model determined under this method can only represent the state of a certain time. Therefore, this paper expands based on AHP, adds time T dimension into consideration, combined with the time series to suppose the AHP LD mechanism.
    Keywords:
    AHP, L-D mechanism, Dynamic expansion, Decision mechanism, Credit

    基于 AHP 拓展的 L-D 机制探究

    刘峰1 杜璇璇2 陆诗颖3
    无锡优级先科信息技术有限公司,无锡,中国
    Email: lsttoy@163.com

    摘要:
    层次分析法,称AHP,被广泛应用于安全科学、环境科学、经济管理等领域。但AHP一旦对准则层进行确定后,将无法更改相关内容一定程度的限制了该方法的应用,即该方法下确定的AHP模型仅能够代表某一时刻的状态。因此,本文基于AHP进行扩展,加入时间T维度的考虑,结合时间序列对AHP的L-D机制进行猜想。
    关键词: AHP、L-D机制、动态拓展、决策机制、信用

    一、简单AHP与扩展

    层次分析法,简称AHP,由美国运筹学家匹茨堡大学教授萨蒂于20世纪70年代初提出。AHP为决策层与决策对象,其中分为最高层、中间层和最低层。在确定各层次各因素之间的权重时,进行两两相互比较,同时采用相对尺度,来减少性质不同的诸因素相互比较的困难,从而提高准确度。如对某一准则,对其下的各方案进行两两对比,并按其重要性程度评定等级,即在这里插入图片描述
    对应于判断矩阵最大特征根的特征向量,经归一化后记为W(即层次单排序),而确认W时,则需要进行一致性检验。其中,n阶一致阵的唯一非零特征根为n;n 阶正互反阵A的最大特征根,当且仅当时,A为一致矩阵。由于连续的依赖于,则比n大的越多,A的不一致性越严重,一致性指标用CI计算,CI越小,说明一致性越大。用 -n 数值的大小来衡量A 的不一致程度。定义一致性指标为:CI=在这里插入图片描述, CI=0,则说明有完全的一致性;CI 接近于0,有满意的一致性;CI 越大,不一致越严重。为衡量CI 的大小,引入随机一致性指标RI=在这里插入图片描述。一般情况下,矩阵阶数越大,则出现一致性随机偏离的可能性也越大。
    因此,层次分析法能够满足多时期、多准则、多目标的系统评价,并且简单的数学计算也使得其推广得更快。在定性数据较多,指标过多,权重难以确定等等的问题上,目前存在诸多AHP与其他结合的方法,比如与模糊定价,大数据权重,logistics等,旨在解决定性不稳定,不具备说服力,权重制定的问题,最终使得该模型或者结果有效[1]。
    然后,上述改进对于AHP的关注点主要集中在优化其模型与结果,单个的AHP的优化固然重要,但是单个AHP的结果并无法永远代表某一事物或者系统,因此,考虑到时间T维度,将诸多个阶段性时间t的AHP结合,最终得到结果,可以显示出动态的变化,而不是单个AHP静态下的结果。本文基于对时间维度T的考虑,基于时间序列分析[2],对AHP进行了猜想,即AHP的L-D机制。

    二、AHP的L-D机制

    假定在一个时间T下,存在三阶段时间t,即t1、t2、t3,相应分别得出三个AHP,即。
    考虑到该三组数据的特点是现实的、真实的数据,即该数据将反映出某一现象的统计指标,观察其背后的变化规律,并且是动态的。因此,在假设通过观察、调查、统计抽样等方法取得三组AHP相关数据后,进行散点矩形图等图像分析,判断变化与趋势周期等特征,而后进行合适的模型建立,最后辨认合适的随机模型进行曲线拟合,出现的结果可能诸多,比如简单的时间序列,平稳时间序列等等。最终,将T时间下的AHP都整合在一个表达式中,实现了T下的动态变化。
    在这里插入图片描述

    三、L-D机制下的应用探索

    举例说明,对某一大学生进行征信测评[3],基于AHP的L-D机制阐述,考虑到用户的特殊性,即在该用户成长过程中,其准测层的变化并非巨大的,因此假设最终其结果服从时间序列回归,F检验显示整体显著。
    当用户成长周期T为大学招聘入职至入职后续的长期跟踪发展。初期进行校园招聘筛选时,企业可基于5C模型[4],以品质、能力、资产、社交、条件五个维度,分别收集大学生用户对应行为即网上支付、网上黑名单、信用卡违约记录、网络信用违约记录等;绩点、实习、比赛、学历、网上支付、网上外卖、生活费按时缴纳等;流动性资产、不动产、非理财保险等;社交范围、社交影响力等;学业成绩稳定性、网络负债额度变化、花呗支付额度变化等,而后将收集信息转化为评估指标,得到个人信用水平指标,进行门槛筛选简历[5]。
    后期企业内部人才管理时,该征信模型持续跟随职工人员,针对不同阶段的发展可进行维度的更改,可依旧基于5C模型,以品质、能力、资产、社交、条件五个维度,但收集用户行为可更改为网上支付、网上黑名单、信用卡违约记录、网络信用违约记录等;工作绩效、上下班时间、加班率、请假率等;流动性资产、不动产、理财保险等等;企业社交范围、社交影响力等;工作完成度、年终奖金变动等等,而后依旧而后将收集信息转化为评估指标,得到个人信用水平指标,对员工进行考核,时刻防范员工信用失信问题。此时,员工信用为:
    在这里插入图片描述
    因此,伴随时间t的变化,对该员工的信用形成了一个动态的长时间的观察,使得其信用判断更适合实际中的应用。

    四、总结

    社会的发展是快速的,单个AHP代表的某一时刻或某一小阶段的静态状态已经无法适应社会生活的应用,社会在变化,企业在变化,产业也在变化,对于长期动态变化的领域中,考虑时间T的因素对模型进行扩展明显更加符合社会发展的趋势[6],因此,在时间序列的猜想下,L-D的机制应用而生,旨在做到将组合,以T的形式呈现出结果,体现出某一事物或者系统的动态变化。
    参考文献
    [1] 李玲.层次分析法在企业权重管理中的应用研究[J].中国市场,2019(06):80-81.
    [2] 史文彬. 时间序列的相关性及信息熵分析[D].北京交通大学,2016.
    [3] 孙小刚,张世免.校园招聘存在的问题及对策探讨[J].科技风,2017(17):229-230.
    [4] 杜文军,朱亚丽.基于“5C”模型的核心素养培养案例分析[J].教学与管理,2019(06):98-101.
    [5] 叶珍. 基于AHP的模糊综合评价方法研究及应用[D].华南理工大学,2010.
    [6] 郑毅. 时间序列数据分类、检索方法及应用研究[D].中国科学技术大学,2015.

    展开全文
  • 在谈到任何一种数字资产时,我们最先考虑的往往是这个数字资产背后代表的技术机制到底是什么,以来评断它的应用价值与投资价值。 而在去中心化世界中,作为Token本身来讲,它所代表的价值其实更深。12月8日,CCF浦江...

    在谈到任何一种数字资产时,我们最先考虑的往往是这个数字资产背后代表的技术机制到底是什么,以来评断它的应用价值与投资价值。

    而在去中心化世界中,作为Token本身来讲,它所代表的价值其实更深。12月8日,CCF浦江大讲堂“区块链与数字金融”论坛在上海举行。中国万向控股副董事长肖风在题为“Token与数字资产”的演讲中提到了Token的五个价值。

    肖风博士认为:区块链项目商业上的成功Token是关键,必须用Token建立一套激励机制,然后分析这种激励机制以及相应的治理机制是不是可持续。

    “首先,构建一个激励机制是Token最核心的价值;第二,Token在去中心化的系统上帮助社区运营建立一个治理机制;第三,Token帮助实现市场的热启动;第四,Token是融资工具;第五,Token具有投资价值。”

    INE的激励机制

    在肖风博士对Token的诠释与INE智联生态的践行中,不免看到很多相似之处。

    INE作为Token激励机制贯通于整个的Mesh网络生态中,通过改进的 POS 共识机制,对提供服务的节点,根据共享出的流量结算,将会有相对应的 Token 作为回报;对智联生态网络的使用者来说,也有机会得到 Token 作为回报。接受内容发布,获取Token分成。例如:信息发布、广告发布、网络通讯,生态建设共享等。

    INE去中心化的社区治理模式

    在区块链项目中,社区运作的基本概念是去除上下级关系,纯粹为了一份信仰而努力。但是如何在社区中维护住这份信仰,并共识到更多人群,是一个值得探索的话题。在INE智联生态的社区治理理念中,致敬区块链去中心化的中心思想,加之分布式Mesh网络,呼之欲出的必将是一个高度自治的社区。

    INE智联生态拿出部分社区共识份额,以建立社区的治理机制。首先着手筹建INE社区自治委员会,发布《INE社区自治委员会橙皮书》,公开招募社区管理层。截止2018年12月02日,已完成第一届INE社区自治委员会管理层任选。

    INE自治委员会中下分四会,分别为共识建设委员会、落地应用委员会、社区扩员委员会、公正监督委员会。四会由社区成员自行组织参与,各司其职,INE作为工资和绩效奖励。

    INE市场的热启动

    市场的热启动其实和落地应用是互为一体的,根据INE智联生态的局域网生态铺设模式,每一个场景落地就是对市场最直接的刺激,所有用户可进行最真实的反馈。

    在这种商业应用的洽谈与实践中,INE智联生态从未停止过努力,包括目前已经达成合作关系的想念集团、深圳沙尾社区、宁夏壹加壹牧业、中科汇宸等等;以及正在洽谈合作澳门金沙集团、维也纳酒店等等。

    以下为肖风演讲内容,摘自火星财经,

    新的账户体系带来金融模式创新

    这两天加密数字货币跌得很厉害,我差点也要改变信仰了,我今天是来充值信仰的。

    我们目前有三类账户体系。一类是银行账户体系,另一类是互联网账户体系,像微信钱包、支付宝,它已经脱离了央行的账户体系,脱离了银行卡。最后是基于非对称加密算法,我们可以开立一个新的不需要中心化机构管理的区块链的账户体系。

    世界级的金融科技创新都来自于新的账户体系。传统的银行帐户体系不可能出现移动支付,也不可能出现余额宝,它们只有在新的账户体系上才能出现。没有账户的创新就不会有颠覆式的金融创新,没有账户的创新我们只有在原有的模式上做边际效益的改变。

    我们可以预见,在区块链这个账户体系上,新的金融创新,新的金融交易,甚至新的金融体系,它会有你现在完全无法预计的创新模式出来,就因为它是新的账户体系,它就会有新的金融模式。

    非对称加密算法实际上是数字世界的产权确认体系。只有基于分布式的记账方法和区块链账户,我们才能记录、运行数字化资产,非对称加密算法是源头。

    Token的演进:从计算机到区块链

    Token实际上有一个演进的过程。

    在计算机互联网世界,Token是指令牌,就是许可证、通行证、密码、口令。它跟所有权是分离的,许可你可以用,但不表示你拥有它。

    在儿童游乐场,你也可以去柜台买一个Token,然后用这个Token去玩所有的游戏。丢两个Token马可以旋转五分钟,马不是你家的,你只是拥有了五分钟的使用权。这时,儿童游乐场的Token具有了结算功能,这是计算机世界的Token所不具有的。这儿童游乐场的Token跟赌场筹码一样,假设每种玩法你都用现金玩,结算就非常复杂,换成赌场筹码后结算就非常简单。

    在网络游戏里天然有Token,网络游戏的Token有使用功能和结算功能外,实际上你是可以通过劳动获得系统发给你的金币,这时候,这个Token是有经济激励的。这是Token的新功能,经济激励,它激励你继续玩这个游戏。

    实际上,公有区块链你就可以看成是一个游戏。在区块链里,Token除了使用、结算、经济激励功能外,它还有支付、融资工具、导流等功能。拿导流功能来说,它能帮助项目热启动。比如Fcoin,依靠交易挖矿的设计,它在几天内成为全球交易量最多的交易所。但如果机制设计不好,这个游戏就变得不可持续。

    Token是使用权市场

    我们把市场分为三类,即所有权、收益权和使用权市场。

    所有权市场有股票市场,买卖股票,实际上交易的是所有权。收益权市场就是债券市场,持有债券可以获得一定比例的利息,但你不拥有这家公司。区块链是使用权市场。为什么呢?你想,我们说比特币是开源基金会,实际上任何一个区块链系统,它没有资产负债表,也没有股东和注册地址,但握有Token你就可以使用这个系统。区块链把Token的使用权剥离出来建立起了一个市场,大家交易比特币、ETH,它是有用处的。

    所有权、收益权、使用权的含义是非常不同的,所有权市场我们把它叫做权益,收益权是权利。有人跟你说Token可以分红,那它就和股票没有区别了。这中间有很大的不同。

    Token是使用权市场

    股票是把所有权证券化了,债券是把收益权证券化了,Token是把使用权证券化了。

    我们认为Token是证券,但Token不是股票,如果它是股票,那我们就没有必要弄一个Token出来,直接买股票,用股票交易就好了。Token是一个崭新的东西,它是很有价值的。之所以大家乐于讨论,是因为它意味着另外一个市场,这是一个使用权的市场。

    股票市场非常大,估计参与者有上百万人,它是一个百万亿美元的市场。债券这个收益权市场也非常大。我们有理由相信,基于使用权证券化的Token,它是使用权市场,这个市场不会小于前面两个市场,将来也会是百万亿美元的市场。也许20年,也许30年。比如优步是使用权市场,它是所有权被淡化使用权被重视的市场。任何使用权的许可都可以是Token,而且是有价值的,未来可能非常非常值钱。使用权不是免费的。

    而因为它是证券,它就会受证券法约束,任何想脱离中心化监管机制,想绕过监管部门的行为肯定是犯罪。1CO过后STO的讨论很热烈,这种讨论一是想把它往股票上靠,二是想绕过监管。不需要监管就等着坐牢。

    但是Token的证券化,即使用权的证券化,它在技术上非常不一样。股票的证券化是把股份变成一股股的份额,中国证券法规定,股票面额是一块钱。使用权的证券化不是面额化,是原子化,拆分到最细,这是两个证券化最大的不同,背后是两种货币最大的不同。有人说比特币固定2100万的发行量会造成经济上的通缩,他是站在法币的角度看数字货币,数字货币没有面额,它可以细分到小数点后很多位。ETH是小数点后18位,它照样可以通货膨胀,但通货膨行不是发货币,而是涨价。

    Token的核心价值:为区块链建立一个激励机制

    我们对Token的估值有很大的误区,我们把它当成股票或债券看,实际上我们无法按照过去的估值模型。因为它是使用权,我们要用使用价值去估值,这是它和股票、债券最大的差别。它不是融资工具,融资仅仅是附带的价值,Token真正的价值在于只有基于Token,你才能在区块链上构建一个经济激励模型。

    我们认为,互操性等技术上的成熟并不表示区块链上的商业就能获得成功,技术是基础。而且,技术不是一个开发者自己能解决的,它需要整个社区,需要计算机专家帮它解决。

    区块链项目商业上的成功Token是关键,必须用Token建立一套激励机制,然后分析这种激励机制以及相应的治理机制是不是可持续。

    因此,我们把Token的价值划归为如下几种。

    首先,构建一个激励机制是Token最核心的价值;第二,Token在去中心化的系统上帮助社区运营建立一个治理机制;第三,Token帮助实现市场的热启动;第四,Token是融资工具;第五,Token具有投资价值。

    但我们认为其投资价值在于系统的无限可扩展性。为什么呢?

    我们认为区块链上所有东西都是免费的,交易成本几乎为零,因此它具备了商业的无限可扩展性。如果设计的好,一个区块链系统可以服务20亿,乃至50亿人。这时,当你的Token供应量是固定的,其价格就会有巨大的涨幅。但是,你不是根据现金流在分析Token的价值,也不是分红、利息。这一套在Token领域统统无效,你是基于它的商业的可扩展新和Token在商业里面的价值进行分析。

    当你投资区块链项目,或者说公链项目时,你要看它的经济激励模型设计的好不好,不好就不具有投资价值,这是判断投不投区块链项目非常重要的因素。

    最好的Token应是“无限循环的游戏”

    Token设计实际上做的是在区块链上,把去中心化的商业设计成一个可以无限循环的游戏。所有参与者能持续得玩这个游戏,无限循环下去。

    比特币就是可以无限循环的游戏,因为它简单,边界清晰,目的明确只有一个,而且它是一个锁死的系统。以太坊就麻烦了,它是开放的,除了底层公链外它支持二次开发,甚至应用开发,它太复杂,没有人能在设计之初就完美得设计出它的激励机制,因此它的激励机制、治理机制只能不断优化。最近以太坊就在更改对全节点的激励,因为之前激励不够。

    我们认为说你激励谁,把Token分发给谁,最后会决定你的区块链里都是哪些人在参与。拿以太坊和EOS为例,EOS的激励给了投资者,EOS成了投资者为主的社区,围绕EOS全是炒币的人。以太坊的激励主要倾向于技术开发者,所以它的社区主要是数千个技术开发者。从这个角度说,以太坊比EOS更有前途,毕竟有那么多技术开发者参与其中,它会慢慢改进。

    来源:INE智联生态

    原文:Token最核心的价值是建立一套激励机制,INE智联生态一直在践行!

    展开全文
  • 【学习笔记】市场机制设计

    万次阅读 2020-10-10 13:22:59
    拍卖机制

    Lecture 1

    1. 博弈模型输入: ( S 1 , u 1 ) , ( S 2 , u 2 ) , . . . , ( S n , u n ) {(S_1,u_1),(S_2,u_2),...,(S_n,u_n)} (S1,u1),(S2,u2),...,(Sn,un)
    • S i S_i Si为第 i i i个参与者的策略集合
    • u i u_i ui为第 i i i个参与者的效用函数,参数为所有 n n n个参与者所有策略的集合 ( s 1 , s 2 , . . . , s n ) (s_1,s_2,...,s_n) (s1,s2,...,sn)
    1. 定义: 称策略 s i s_i si相对于 s i ′ s^{\prime}_{i} si强绝对占优的策略, 若对于任意 s − i ∈ S − i s_{-i}∈S_{-i} siSi, 有 u i ( s i , s − i ) > u i ( s i ′ , s − i ) u_i(s_i,s_{-i})\gt u_i(s^{\prime}_{i},s_{-i}) ui(si,si)>ui(si,si)
    2. 定义: 称策略 s i s_i si相对于 s i ′ s^{\prime}_{i} si弱绝对占优的策略, 若对于任意 s − i ∈ S − i s_{-i}∈S_{-i} siSi, 有 u i ( s i , s − i ) ≥ u i ( s i ′ , s − i ) u_i(s_i,s_{-i})\ge u_i(s^{\prime}_{i},s_{-i}) ui(si,si)ui(si,si)
    3. 定义: 称策略 s ∗ ∈ S 1 × S 2 × … × S n s^{*}∈S_1×S_2×…×S_n sS1×S2××Sn是一个纯纳什均衡(PNE)对于博弈 ( S 1 , u 1 ) , ( S 2 , u 2 ) , . . . , ( S n , u n ) {(S_1,u_1),(S_2,u_2),...,(S_n,u_n)} (S1,u1),(S2,u2),...,(Sn,un), 若对于任意 i i i以及任意 s i ∈ S i s_i∈S_i siSi,有 u i ( s i ∗ , s − i ∗ ) > u i ( s i , s − i ∗ ) u_i(s^{*}_{i},s^{*}_{-i})\gt u_i(s_{i},s^{*}_{-i}) ui(si,si)>ui(si,si)
    4. 定义: 称混合策略 σ ∗ ∈ Δ ( S 1 ) × Δ ( S 2 ) × … × Δ ( S n ) \sigma^{*}∈\Delta(S_1)×\Delta(S_2)×…×\Delta(S_n) σΔ(S1)×Δ(S2)××Δ(Sn)是一个纳什均衡对于博弈 ( S 1 , u 1 ) , ( S 2 , u 2 ) , . . . , ( S n , u n ) {(S_1,u_1),(S_2,u_2),...,(S_n,u_n)} (S1,u1),(S2,u2),...,(Sn,un)若对于任意 i i i以及任意 s i ∈ S i s_i∈S_i siSi,有 u i ( σ i ∗ , σ − i ∗ ) ≥ u i ( s i , σ − i ∗ ) u_i(\sigma^{*}_{i},\sigma^{*}_{-i})\ge u_i(s_{i},\sigma^{*}_{-i}) ui(σi,σi)ui(si,σi)
    • 如石头剪刀布博弈中的纳什均衡是混合策略 σ 1 = σ 2 = ( 1 3 , 1 3 , 1 3 ) \sigma_1=\sigma_2=(\frac{1}{3}, \frac{1}{3}, \frac{1}{3}) σ1=σ2=(31,31,31)

    课后习题

    1. 如果用绝对占优策略来删除行列的方法得到最后一个方格, 证明这是一个纳什均衡
    2. 证明: 石头剪刀布中(1/3,1/3,1/3)的混合策略是唯一的纳什均衡

    下节课的内容

    1. Single Item Auction: 单品拍卖
    • Setup: 1个商品, 1个卖家, n n n个买家
    • 买家 i i i对商品有一个价值估计 v i v_i vi, 约等于愿意付出的最高价额, v i v_i vi对除买家 i i i外的所有其他人都是未知
    • 效用模型: quaslinear utility, 准线性模型
      • 如果未能拍得商品, 则 u = 0 u=0 u=0
      • 如果最终拍得商品, 则 p = v i − p p=v_i-p p=vip
    1. Sealed-Bid Auctions 封存标价拍卖
    • Setup:
      • 每个买家同时提交竞价 b i b_i bi, 只有一次竞价机会且结果对除卖家外的所有人都不可见
      • 卖家决定谁是赢家
      • 卖家决定赢家应当付多少钱
    • 显然第二步应当选取出价最高者
    • 可能的第三步策略:
      • First-price-auction: 一价拍卖, 赢家出其所报的价钱
      • Second-price-auction: 次价拍卖

    Lecture 2

    1. 2nd-price/Vickrey Auction: 次价拍卖, 竞价最高者付第二高竞价者所出的价格
    • 一价拍卖机制存在漏洞, 不能使得每个人都足够诚实, 因而引出次价拍卖
    • Claim1: 在一个次价拍卖中, 每个竞价这有一个占优策略, b i ⇐ v i b_i\Leftarrow v_i bivi, 比如每个竞价这都出自己的估值 v i v_i vi, 事实上也是如此
      • 证明:
        • 对于给定的 i i i, v i v_i vi和其他的竞价 b − i b_{-i} bi, 显然第 i i i个人的效用在竞价出 v i v_i vi时得到了最大化
        • B = m a x j ≠ i b i B = max_{j\ne i}b_i B=maxj=ibi, 即除了第 i i i个人外所有人竞价的最大值
        • 注意因为在次价拍卖中, 第 i i i的效用要么是0, 要么是 B − v i B-v_i Bvi
    • Claim2: 在次价拍卖中, 如果说真话, 就不会得到负的效用
      • 因为成交价格对于竞价成功者来说一定是小于
    • 定理: Vickrey auction是awesome的
      • Vickrey action是dominant-strategy incentive compatible, 即SSIC
        • 即Claim1+Claim2的结论, 每个人说真话是占优策略, 且不会得到负的效用
      • 如果竞价者是可以信赖的, 则拍卖最大化了社会剩余/社会福利
        • 社会剩余/社会福利 = ∑ i = 1 n v i x i   x i ∈ { 0 , 1 } \sum_{i=1}^n v_i x_i \space x_i ∈ \{0,1\} i=1nvixi xi{0,1},当第 i i i个人赢得了拍卖, x i x_i xi为1, 否则为0
      • Vickrey auction是可以在多项式时间内实现的
        • 案例分析: Sponsored Search Auction
          • 每次搜索, 就会实时发生一次拍卖
          • 商品: 搜索结果页面上的 k k k个广告位
          • 竞价者: 对于搜索结果页面有兴趣的商家
          • 注意: k k k个广告位不是相同, 排在越靠前的广告位价值越高
          • α j \alpha_j αj为第 j j j个广告位被点击的概率, 即CTR
          • 假设:
            • α 1 ≥ α 2 ≥ . . . ≥ α k \alpha_1\ge \alpha_2\ge ... \ge \alpha_k α1α2...αk
            • α j \alpha_j αj 是相互独立的
            • 竞价者 i i i对每一次点击都有一个私有的评估价格 v i v_i vi, 搜索引擎与其他竞价者都无法知道, 搜索引擎与其他竞价者都无法知道, 从而会得到 v i ∗ α j v_i*\alpha_j viαj
          • 目标:
            • 设计一个DSIC拍卖
            • 最大化社会剩余, 即 m a x i m i z e ∑ i = 1 n v i ∗ α i maximize \sum_{i=1}^n v_i*\alpha_i maximizei=1nviαi, 其中 x i x_i xi是第 i i i个广告位目标被点击的概率(广告位 i i i被分配给了 i i i), 否则为0
            • 可以在多项式时间内得出结果
          • 方法:
            • Step1: 若竞价者诚信竞价, 那么应该怎么分配使得最大化剩余以及确保算法的时间复杂度为多项式时间
            • Step2: 给定Step1的回答, 需要确定定价策略使得是一个DSIC拍卖
          • 答案: 按照竞价高低的顺序从前到后依次分配各个广告位, 即第 j j j高的竞价者分配第 j j j个广告位
            • 假设最终是 α i \alpha_i αi v i v_i vi对应, 显然 v i v_i vi应当是单调不增的, 这样才能使得 ∑ i = 1 n v i ∗ α i \sum_{i=1}^n v_i*\alpha_i i=1nviαi取得最大值
        • Myerson’s引理:
          • Single-parameter environment
            • n n n个竞价者, 第 i i i个竞价者对拍卖品有一个私有的估值 v i v_i vi/单位
            • feasible allocations: X = { x 1 , x 2 , . . . , x n } X = \{x_1,x_2,...,x_n\} X={x1,x2,...,xn}, 其中 x i x_i xi是第 i i i个竞价者得到的单位商品数量
            • 举个例子:
              • Single-Item Auction: 所有可能的分配方案 X = { ( 1 , 0 , . . . , 0 ) , ( 0 , 1 , . . . , 0 ) , ( 0 , 0 , . . . , 1 ) } X=\{(1,0,...,0),(0,1,...,0),(0,0,...,1)\} X={(1,0,...,0),(0,1,...,0),(0,0,...,1)}
              • Sponsored Search Auction: X X X为如何分配 k k k个广告位的方法
            • 我们仍然在Sealed-Bid Auction的环境下研究这个问题
              • 收集所有的竞价 b ⃗ = { b 1 , b 2 , . . . , b n } \vec b=\{b_1,b_2,...,b_n\} b ={b1,b2,...,bn}
              • 分配规则, 选择 X ⃗ ( b ⃗ ) ∈ X ⊆ R n \vec X(\vec b)∈X\subseteq R^n X (b )XRn, X X X为一个N维向量
              • 付款规则: 选择 p ( b ⃗ ) ∈ R n p(\vec b)∈R^n p(b )Rn
              • i i i个人的效用在 b ⃗ \vec b b 上等于 v i ∗ x i ( b ⃗ ) − p i ( b ⃗ ) v_i*x_i(\vec b)-p_i(\vec b) vixi(b )pi(b )
              • 重点是如何确定付款规则使得 p i ( b ⃗ ) ∈ [ 0 , b i ∗ X i ( b ⃗ ) ] p_i(\vec b)∈[0, b_i*X_i(\vec b)] pi(b )[0,biXi(b )], 即确保卖家不会倒贴, 竞价者不会得到负的效用
              • 定义: 一个分配规则 X ⃗ ( ⋅ ) \vec X(·) X ()是可以实施的(implementable), 若存在一种付款规则 p ( ⋅ ) p(·) p()使得 ( X ⃗ , p ) (\vec X,p) (X ,p)是DSIC
                • 付款规则1: 将商品给到出价最高的竞价者?
                • 付款规则2: 将商品给到出价第二高的竞价者?
                • Sponsored Search Auction中的分配方案是否是DSIC的?
              • 定义: 一个分配规则 X ⃗ ( ⋅ ) \vec X(·) X ()是单调的(monotone), 若对于任意 i i i和任意 b − i b_{-i} bi, X ( z , b − i ) X(z,b_{-i}) X(z,bi)是不减的在它的所有竞价 z z z中, 即高竞价者将会获得更多的商品
          • Myerson’s引理内容
            • 一个分配规则 X ⃗ ( ⋅ ) \vec X(·) X ()是可以实施的等价于 X ⃗ ( ⋅ ) \vec X(·) X ()是单调的
            • 在这种情况下, 存在唯一的付款规则 p ( ⋅ ) p(·) p()使得 ( X ⃗ , p ) (\vec X,p) (X ,p)是DSIC
            • p ( ⋅ ) p(·) p()是可以被一个直接的公式给出(TBD)
          • 推论: 不会把商品出售给第二高的竞价者, Sponsored Search Auction中的策略是可以实施的
          • Myerson’s引理证明(Slide P.21)
            • 考虑一个分配规则 X ⃗ ( ⋅ ) \vec X(·) X (), 若 ( X ⃗ , p ) (\vec X,p) (X ,p)是DSIC, 那么 p ( ⋅ ) p(·) p()应该是什么样的?
            • 证明分配规则是单调的: 固定 i i i b − i b_{-i} bi, 写出 X ⃗ ( z ) , p ( z ) \vec X(z), p(z) X (z),p(z)对于 X i ( z , b − i ) X_i(z,b_{-i}) Xi(z,bi) p i ( z , b − 1 ) p_i(z,b_{-1}) pi(z,b1)
              • y ≥ z ≥ 0 y\ge z\ge 0 yz0, DSIC需要兼顾两种情况, 即对于竞价者 i i i来说, 不管高报或者低报都无法得到最高效用
                • [true value = z, false bid = y], z ∗ X ( z ) − p ( z ) ≥ z ∗ X ( y ) − p ( y ) z*X(z)-p(z)\ge z* X(y)-p(y) zX(z)p(z)zX(y)p(y)(注意不是 y ∗ X ( y ) − p ( y ) y*X(y)-p(y) yX(y)p(y))
                • [true value = y, false bid = z], y ∗ X ( y ) − p ( y ) ≥ y ∗ X ( z ) − p ( z ) y*X(y)-p(y)\ge y*X(z)-p(z) yX(y)p(y)yX(z)p(z)
                • 移项后 z ( X ( y ) − X ( z ) ) ≤ p ( y ) − p ( z ) ≤ y ( X ( y ) − X ( z ) ) z(X(y)-X(z)) \le p(y)-p(z) \le y( X(y)-X(z)) z(X(y)X(z))p(y)p(z)y(X(y)X(z)), 得到 X ( y ) ≥ X ( z ) X(y)\ge X(z) X(y)X(z) X ⃗ ( ⋅ ) \vec X(·) X ()是单调的
              • 证明单调的分配规则是有一个付款规则与其对应使得DSIC:
                • 书上的证明: 简单起见, 假设 X X X函数的图像是place-wise constant, 即图像上是一段一段都是常数, 但是整体是单调不减, 存在跳跃间断点; 从图像上来看, 给竞价值的点, 付款值应当等于 X X X函数的图像, y轴, 该点处的水平线围成的面积
                • 另一种证明: 在 z ( X ( y ) − X ( z ) ) ≤ p ( y ) − p ( z ) ≤ y ( X ( y ) − X ( z ) ) z(X(y)-X(z)) \le p(y)-p(z) \le y(X(y)-X(z)) z(X(y)X(z))p(y)p(z)y(X(y)X(z))各个位置除以 ( y − z ) (y-z) (yz), 当 y y y逼近 z z z时就会有 z X ′ ( z ) = p ′ ( z ) zX^\prime(z) = p^\prime(z) zX(z)=p(z), 且有卖家不会倒贴竞价者所以 p ( 0 ) = 0 p(0)=0 p(0)=0, 则 p ( ⋅ ) p(·) p()是可以被唯一确定的, p ( b ) = b X ( b ) − ∫ 0 b X ( z ) d z p(b)=bX(b)-\int_{0}^bX(z)dz p(b)=bX(b)0bX(z)dz
              • 最后我们证明 p p p是有效的当 X X X是单调的(充分性证明, 上面一步是必要性证明)
                • z X ( z ) − p ( z ) = z X ( y ) − p ( y ) + S zX(z)-p(z)=zX(y)-p(y)+S zX(z)p(z)=zX(y)p(y)+S, 其中S是图像上多出来的那块面积
                • 效用是曲线下方的面积, revenue是曲线上方的面积
                • 在Sponsored Search Auction中: p i ( b ) = ∑ j = i k b j + 1 ( α j − α j + 1 ) [ α k n = 0 ] p_i(b) = \sum_{j=i}^k b_{j+1}(\alpha_j - \alpha_{j+1})[\alpha_{kn}=0] pi(b)=j=ikbj+1(αjαj+1)[αkn=0] 实际情况中是真正点击了才会付钱, p i ( b ) α i = ∑ j = i k b j + 1 α j − α j + 1 α i \frac{p_i(b)}{\alpha_i} = \sum_{j=i}^kb_{j+1}\frac{\alpha_j-\alpha_{j+1}}{\alpha_{i}} αipi(b)=j=ikbj+1αiαjαj+1

    课后习题

    1. 如果在次价格拍卖中, 如果你不说真话, 总是存在一种情况使得你的效用比说真话要低?
    2. n n n个人 k k k个相同商品的拍卖问题, 应当以什么价格成交?

    Lecture 3

    1. Knapsack Auctions: 背包拍卖(对应背包问题)
    • n n n个竞价者, 第 i i i个竞价者有一个私有的估值 v i v_i vi和一个公开的背包大小 w i w_i wi
    • 卖家有一个商品总容量 W W W, 比如卖家是广告商, 广告总时长只有三分钟
    • 可行集合 X X X是一个零一向量 ( x 1 , x 2 , . . . , x n ) (x_1,x_2,...,x_n) (x1,x2,...,xn), 使得 ∑ i = 1 n w i ∗ x i ≤ W \sum_{i=1}^n w_i*x_i\le W i=1nwixiW
      • w i = 1   W = i w_i=1\space W=i wi=1 W=i or k k k, 则退化成单品或多品拍卖
      • 显然这里每个人的背包都是要被装满的, 不会存在背包不装满的情况
    • 按照社会福利最大化规则作为分配规则来分配所有的拍卖物: X ( b ⃗ ) = a r g m a x x ∈ X ∑ i = 1 n b i ∗ x i X(\vec b) = argmax_{x∈X}\sum_{i=1}^n b_i*x_i X(b )=argmaxxXi=1nbixi, 即解决背包问题
    • 背包问题是NP-hard, 因此不能在短时间内计算得出结果
    • ( X , p ) (X,p) (X,p)是awesome的吗?
      • ① DSIC(√)
      • ② 社会福利最大化(√)
      • ③ 多项式时间内求解(×)
      • 此时我们不可能relax①, 可以考虑relax②和③
    • 我们的方法: relax③ 如使用动态规划在伪多项式时间内解决
    • 另一种我们希望尽可能少的relax②, 使得服从①和③, 等价于relax②使得③依然单调, 比如使用近似算法(Approximate Algorithm)
    • Best-case scenario: match best-known guarantee without any monotinicity or DSIC constraints
    • 背包问题的贪心算法(一种近似算法)
      • ① 按照 b i / w i b_i/w_i bi/wi的值对竞价者进行降序排序, 即按照单位出价排序
      • ② 挑选该排序下的竞价者加入背包, 直到某个竞价者不再能被装入背包, 就停止(不会继续向后寻找, 否则不满足单调性)
      • ③ 返回两者之一: {the solution of ②, 出价最高的竞价者}, 选择那个可以得到最大化社会福利的选择
        • 之所以要选择出价最高者, 因为可能②的结果是相当差的, 假想有一个出价很高的也买很多, 但是排序前几的几个小买单太低使得大买单无法进入背包就显然不合适
      • 这种算法是2-approx的, 即至少可以达到最优解一半的目标函数值(社会福利)
      • 难点在于并非所有近似算法给出都可以给出单调的分配规则
    1. Revelation Principle: 显示原理
    • 至今为止我们都主要研究DSIC机制
      • ①每个竞价者都有一个占优策略
      • ②这个占优策略就是说真话(direct revelation)
    • 考虑relax①, 结果需要假设玩家是均衡的(equilibrium)
      • 纳什均衡, 贝叶斯纳什均衡
      • Pros: 有时可以得到更好的均衡表现
    • 考虑relax②, 不需要给定①, ②仍然是不失一般性的(WLOG)
    • 显示原理:
      • 任意一个拥有guaranteed占优策略的机制 M M M, 存在一个均衡的直接显示的(equilvalent direct-revelation, 可以理解为说真话)DSIC机制 M ′ M^{\prime} M
      • 证明: by simulation argument
        • 输入n个报价 { v 1 , v 2 , . . . , v n } \{v_1,v_2,...,v_n\} {v1,v2,...,vn}进入 M ′ M^{\prime} M, M ′ M^{\prime} M将它们变成 { s 1 ( v 1 ) , s 2 ( v 2 ) , . . . , s n ( v n ) } \{s_1(v_1),s_2(v_2),...,s_n(v_n)\} {s1(v1),s2(v2),...,sn(vn)}后输入 M M M, 得到 M M M的输出后再由 M ′ M^{\prime} M输出最终结果
        • 举个例子: 次价拍卖中将成交价改为第二名报价的两倍, 则每个人的报价将为估值的一半, 即 M M M M ′ M^{\prime} M中的出价总可以映射

          考虑一个拍卖, 所有竞拍方都只知道自己对物品的估值, 拍卖的结果由所有竞拍方的报价决定; 这是一个间接机制, 对物品估值为 a a a的竞拍方的策略是报价 f ( a ) f(a) f(a); 用另一个方式考虑这个拍卖, 竞拍方报出自己对物品的估值, 一个机器或者代理人自动根据报出的估值报价, 这就是直接机制, 竞拍方的策略变成了是否真实报估值;
          显示原理就是任何间接机制都可以以上述这种方式等价于一个直接机制; 直接机制比间接机制方便研究, 所以显示原理很重要;

    1. Revenue Maximization: (卖家)收益最大化(Slide P.33)
    • 至今为止, 我们只考虑了社会福利最大化的拍卖
    • 为什么?
      • DSIC
      • sourplus是特殊的, 甚至事后(ex-post)也是最大化的(若所有的报价都是实现知道的)
    • Example: 一个竞价者, 一个物品
      • DSIC拍卖为拍卖(posted price) r r r
      • 收益revenue R ∈ { r , 0 } R ∈ \{r, 0\} R{r,0}, 即 v ≥ r v\ge r vr时为 r r r, 反之为零
      • 为了最大化收益, 如果我们知道 v v v, 那就设成 r = v r=v r=v
      • Upshot: 对于收益来说, 不同的拍卖在不同的输入上做得更好
      • 所以需要一个模型来解释(reason about)不同输入间的trade-off
      • Bayes Analysis: 贝叶斯分析
        • 单变量环境
        • v i v_i vi是从分布 F i F_i Fi中采样得到的, 取值范围 [ 0 , v m a x ] [0,v_{max}] [0,vmax]
        • F i F_i Fi都是独立的, 对于机制设计者是可知的, 但是实际估值 v i v_i vi都是不可知的
        • 最大化期望收益
        • Example: 一个竞价者, 一个物品
          • 期望收益是 r ( 1 − F ( r ) ) r(1-F(r)) r(1F(r))
          • F F F U n i f o r m [ 0 , 1 ] Uniform[0,1] Uniform[0,1] r ∗ = 0.5 r^{*}=0.5 r=0.5
        • Example: 两个竞价者, 一个物品
          • 已知 v 1 , v 2 ∼ U n i f o r m [ 0 , 1 ] v_1,v_2 \sim Uniform[0,1] v1,v2Uniform[0,1]
          • Vickrey次价拍卖的收益为 E [ m i n ( v 1 , v 2 ) ] = 1 3 E[min(v_1,v_2)]=\frac{1}{3} E[min(v1,v2)]=31
          • 假若我们设定一个起拍价格 0.5 0.5 0.5, 则可以得到 5 12 \frac{5}{12} 125的期望收益
    • 目标: characterize最优拍卖
      • ①revelation principle⇒可以restrict to direct-revelation
        • ( X , p ) (X,p) (X,p)==>总是假设 b = v b=v b=v
        • Revenue: E v ⃗ ( ∑ i = 1 n p i ( v ⃗ ) ) E_{\vec v}(\sum_{i=1}^n p_i(\vec v)) Ev (i=1npi(v ))
      • ②拍卖期望收益的重要公式
        • 回顾: Myerson’s payment formula
          • p i ( v ⃗ ) = ∫ 0 v i z ∗ X i ′ ( z , v ⃗ − i ) d z = v i ∗ X i ′ ( v ⃗ ) − ∫ 0 v i X i ′ ( z , v ⃗ − i ) d z p_i(\vec v)=\int_{0}^{v_i}z*X_i^{\prime}(z,\vec v_{-i})dz=v_i*X_i^{\prime}(\vec v)-\int_{0}^{v_i}X_i^{\prime}(z,\vec v_{-i})dz pi(v )=0vizXi(z,v i)dz=viXi(v )0viXi(z,v i)dz即为 X i ( z ) X_i(z) Xi(z)关于 z z z的曲线左边的面积
      • (详细推导Slide P.38-40)固定 i i i v − i v_{-i} vi, 有
        E v i ∼ F i [ p i ( v ⃗ ) ] = ∫ 0 v m a x p i ( v ⃗ ) f i ( v i ) d v i = ∫ 0 v m a x [ ∫ 0 v i z X i ′ ( z , v ⃗ − i ) ] f i ( v i ) d v i = ∫ 0 v m a x [ ∫ z v m a x f i ( v i ) ] ) z X i ′ ( z , v ⃗ − i ) d v i = ∫ 0 v m a x ( 1 − F i ( z ) ) z X i ′ ( z , v ⃗ − i ) d z = ( 1 − F i ( z ) ) z X i ( z , v ⃗ − i ) ∣ 0 v m a x − ∫ 0 v m a x X i ( z , v ⃗ − i ) d ( z ( 1 − F i ( z ) ) ) = − ∫ 0 v m a x X i ( z , v ⃗ − i ) ( 1 − F i ( z ) − z f i ( z ) ) d z = ∫ 0 v m a x [ z − 1 − F i ( z ) f i ( z ) ] f i ( z ) X i ( z , v ⃗ − i ) d z E_{v_i\sim F_i}[p_i(\vec v)] = \int_{0}^{v_{max}}p_i(\vec v)f_i(v_i)dv_i\\ =\int_{0}^{v_{max}}[\int_{0}^{v_i}zX_i^{\prime}(z,\vec v_{-i})]f_i(v_i)dv_i\\ =\int_{0}^{v_{max}}[\int_{z}^{v_{max}}f_i(v_i)])zX_i^{\prime}(z,\vec v_{-i})dv_i\\ =\int_{0}^{v_{max}}(1-F_i(z))zX_i^{\prime}(z,\vec v_{-i})dz\\ =(1-F_i(z))zX_i(z,\vec v_{-i})|_{0}^{v_{max}}-\int_{0}^{v_{max}}X_i(z,\vec v_{-i})d(z(1-F_i(z)))\\ =-\int_{0}^{v_{max}}X_i(z,\vec v_{-i})(1-F_i(z)-zf_i(z))dz\\ =\int_{0}^{v_{max}}[z-\frac{1-F_i(z)}{f_i(z)}]f_i(z)X_i(z,\vec v_{-i})dz\\ EviFi[pi(v )]=0vmaxpi(v )fi(vi)dvi=0vmax[0vizXi(z,v i)]fi(vi)dvi=0vmax[zvmaxfi(vi)])zXi(z,v i)dvi=0vmax(1Fi(z))zXi(z,v i)dz=(1Fi(z))zXi(z,v i)0vmax0vmaxXi(z,v i)d(z(1Fi(z)))=0vmaxXi(z,v i)(1Fi(z)zfi(z))dz=0vmax[zfi(z)1Fi(z)]fi(z)Xi(z,v i)dz
      • 定义virtual valuation ϕ i ( z ) = z − 1 − F i ( z ) f i ( z ) \phi_i(z)=z-\frac{1-F_i(z)}{f_i(z)} ϕi(z)=zfi(z)1Fi(z)
        • 在均匀分布中有 F i ( z ) = z F_i(z)=z Fi(z)=z, f i ( z ) = 1 f_i(z)=1 fi(z)=1, ϕ i ( z ) = z − 1 − z 1 = 2 z − 1 \phi_i(z)=z-\frac{1-z}{1}=2z-1 ϕi(z)=z11z=2z1
      • E v i [ p i ( v ⃗ ) ] = E v i [ ϕ i ( v i ) ∗ X i ( v ⃗ ) ] E_{v_i}[p_i(\vec v)]=E_{v_i}[\phi_i(v_i)*X_i(\vec v)] Evi[pi(v )]=Evi[ϕi(vi)Xi(v )]对于任意的 i , v ⃗ − i i,\vec v_{-i} i,v i
      • apply E v ⃗ − i E_{\vec v_{-i}} Ev i E v ⃗ [ p i ( v ⃗ ) ] = E v ⃗ [ ϕ i ( v i ) ∗ X i ( v ⃗ ) ] E_{\vec v}[p_i(\vec v)]=E_{\vec v}[\phi_i(v_i)*X_i(\vec v)] Ev [pi(v )]=Ev [ϕi(vi)Xi(v )]
      • 由期望的线性, 有
        ∑ i = 1 n E v ⃗ [ p i ( v ⃗ ) ] = ∑ i = 1 n E v ⃗ [ ϕ i ( v i ) ∗ X i ( v ⃗ ) ] = E v ⃗ [ ∑ i = 1 n ϕ i ( v i ) ∗ X i ( v ⃗ ) ] \sum_{i=1}^{n}E_{\vec v}[p_i(\vec v)]=\sum_{i=1}^{n}E_{\vec v}[\phi_i(v_i)*X_i(\vec v)]=E_{\vec v}[\sum_{i=1}^{n}\phi_i(v_i)*X_i(\vec v)] i=1nEv [pi(v )]=i=1nEv [ϕi(vi)Xi(v )]=Ev [i=1nϕi(vi)Xi(v )]
        • i.e. 期望revenue 等于 期望的virtual surplus(EXPECTED REVENUE = EXPECTED VIRTUAL VALUE
        • 我们的想法就是逐点最大化这个式子, 比如对于每个 v ⃗ \vec v v , 定义 X ( v ⃗ ) X(\vec v) X(v )来最大化 ∑ i n ϕ i ( v i ) X i ( v ⃗ ) \sum_{i}^{n}\phi_i(v_i)X_i(\vec v) inϕi(vi)Xi(v )
        • i.e. 拍卖赢家是有最高 ϕ i ( v i ) \phi_i(v_i) ϕi(vi)的竞价者, 或者没有赢家如果所有的 ϕ i ( v i ) \phi_i(v_i) ϕi(vi)都是小于零的
        • Catch: is the rule X X X monotone? 即 ϕ \phi ϕ是单调的吗?
        • 事实上 ϕ i ( v i ) \phi_i(v_i) ϕi(vi)总是单调的, 上面的均匀分布的结果是 2 z − 1 2z-1 2z1即为单调, 这并非偶然
        • 定义: F F F是常规的(regular), 若 ϕ F ( z ) = z − 1 − F i ( z ) f i ( z ) \phi_F(z)=z-\frac{1-F_i(z)}{f_i(z)} ϕF(z)=zfi(z)1Fi(z)是严格递增的
        • Note: 假设 F F F是常规的且是独立同分布的, 即所有人的估值分布都是一样的, 则highest valuation( ϕ \phi ϕ) <==> highest virtual value( v v v)
        • 对于iid的常规竞价者, Vickrey of reserve price ϕ − 1 ( 0 ) \phi^{-1}(0) ϕ1(0)
        • 即两个人都比 ϕ − 1 ( 0 ) \phi^{-1}(0) ϕ1(0)低就不卖, 有一个高于则按照较低出价者的出价来成交
        • 但是有可能 ϕ \phi ϕ v v v并非是同大同小的, 这可能是不公正的

    课后习题

    1. 背包问题中的社会福利最大化规则是单调的(事实上这对于一切单变量环境都是单调的)==>由Myerson’s Lemma给出付款规则 p p p使得 ( x , p ) (x,p) (x,p)DSIC
    • 给定 i , b ⃗ − i i, \vec b_{-i} i,b i如果 X i ( b i ) = 1 X_i(b_i)=1 Xi(bi)=1 p i ( b ) = p_i(b)= pi(b)= critic bid = i =i =i竞价者赢得拍卖的最低出价, 曲线左边的面积是竞价者剩余
    1. 证明背包问题的贪心算法是2-approx
    • 提示: v ( A ) = ∑ i ∈ A v i ,   v ( B ) = v m a x = = > v ( A ) + v ( B ) ≥ O P T v(A)=\sum_{i∈A}v_i,\space v(B)=v_{max}==>v(A)+v(B)\ge OPT v(A)=iAvi, v(B)=vmax==>v(A)+v(B)OPT
    • slide P.31
    1. 背包问题的贪心算法是可以推导出一个单调的分配规则, 即竞价者仍然是出价越高或单位出价越高越容易得到更高的效用==>由Myerson’s Lemma可以给出付款规则 p p p使得 ( x , p ) (x,p) (x,p)DSIC
    • 单调的情况下意味着付款规则对于每个竞价者都存在一个critic bid使得高于该报价获胜, 低于该报价是失败的

    Lecture 4

    1. 上集回顾
    • [ ∑ i = 1 n p i ( v ⃗ ) ] = E v ⃗ [ ∑ i = 1 n ϕ i ( v ⃗ ) X i ( v ⃗ ) ] [\sum_{i=1}^{n}p_i(\vec v)] = E_{\vec v}[\sum_{i=1}^{n}\phi_i(\vec v)X_i(\vec v)] [i=1npi(v )]=Ev [i=1nϕi(v )Xi(v )]
    • EXPECTED REVENUE = EXPECTED VIRTUAL WELFARE
    • ϕ i ( v i ) = v i − 1 − F i ( v i ) f i ( v i ) \phi_i(v_i) = v_i - \frac{1-F_i(v_i)}{f_i(v_i)} ϕi(vi)=vifi(vi)1Fi(vi) 严格单调增
    • 要求分布 F i F_i Fi是regular的
    • 如果virtual welfare最大化分配规则是单调的, 则它是最优的
    • 应用: 单品拍卖, iid分布的regular竞拍者, 最优拍卖为Vickrey+reserve_price( ϕ − 1 ( 0 ) \phi^{-1}(0) ϕ1(0))
    • 举例: 若两个竞拍者A的分布为Uniform[0,2], B的分布为Uniform[0,3], A真实出价为2, B真实出价为2.4, 则算下来A的virtual revenue为2, B为1.8. 因此A赢得了拍卖, 付款为1.9, 因为A只要报出1.9就仍然可以赢B, 所以对于A来说Allocation Function在1.9处发生跳跃, 左侧面积刚好为1.9, 即为critic bid
      • 因此myerson理论在实际中存在缺陷, 出价低的人反而赢得了竞拍, 且付款额是一个很奇怪的数字
      • 因此我们希望找到一个更简单, 更实际, 更鲁棒的拍卖
      • 引出计算机领域的一个拍卖, 即牺牲一些社会福利, 如只要80%的福利, 但是我可以取得接近最优解的结果
    1. Prophet Inequality 先验不等式
    • 一个有 n n n轮的博弈
    • 在第 i i i阶段, 会提供一个价值为 π i \pi_i πi的奖励 π i ∼ G i \pi_i \sim G_i πiGi, 其中分布 G i G_i Gi是已知的(且各个阶段的prize相互独立)
    • 玩家在看到 π i \pi_i πi后, 可以接受(则博弈停止)或者继续, 最终要最大化自己的收益
    • 定理[Samel-Cahn’ 84]: 存在一种策略, 使得期望收益不小于 1 2 E π ⃗ [ max ⁡ i π i ] \frac{1}{2}E_{\vec \pi}[\max_i\pi_i] 21Eπ [maxiπi], 即至少为可能最优解的一半, 只要使用一个阈值策略, 即接受 π i \pi_i πi一旦 π i ≥ t \pi_i\ge t πit, t t t为给定的阈值
      • 证明:
        • 定义符号 z + = max ⁡ { 0 , z } z^{+}=\max\{0,z\} z+=max{0,z}, 考虑一个阈值 t t t, 使得 q ( t ) = P r ( π i < t , ∀ i ) q(t)=Pr(\pi_i\lt t, \forall i) q(t)=Pr(πi<t,i)
        • E [ E[ E[ t t t为阈值的收益] = t ( 1 − q ( t ) ) + ∑ i = 1 n E π i [ π i − t ∣ π i ≥ t , π j < t , ∀ j < i ] ⋅ P r ( π i ≥ t ) ⋅ P r ( π j < t , ∀ j < i ) ≥ t ( 1 − q ( t ) ) + ∑ i = 1 n E π i [ π i − t ∣ π i ≥ t ] ⋅ P r ( π i ≥ t ) ⋅ P r ( π j < t , ∀ j ≠ i ) = t ( 1 − q ( t ) ) + ∑ i = 1 n E π i [ ( π i − t ) + ] ⋅ P r ( π j < t , ∀ j ≠ i ) ≥ t ( 1 − q ( t ) ) + ∑ i = 1 n E π i [ ( π i − t ) + ] ⋅ q ( t ) =t(1-q(t))+\sum_{i=1}^{n}E_{\pi_i}[\pi_i-t|\pi_i\ge t, \pi_j\lt t, \forall j<i]·Pr(\pi_i\ge t)·Pr(\pi_j\lt t, \forall j<i)\\ \ge t(1-q(t))+\sum_{i=1}^{n}E_{\pi_i}[\pi_i-t|\pi_i\ge t]·Pr(\pi_i\ge t)·Pr(\pi_j\lt t, \forall j\ne i)\\ =t(1-q(t))+\sum_{i=1}^{n}E_{\pi_i}[(\pi_i-t)^{+}]·Pr(\pi_j\lt t, \forall j\ne i)\\ \ge t(1-q(t))+\sum_{i=1}^{n}E_{\pi_i}[(\pi_i-t)^{+}]·q(t) =t(1q(t))+i=1nEπi[πitπit,πj<t,j<i]Pr(πit)Pr(πj<t,j<i)t(1q(t))+i=1nEπi[πitπit]Pr(πit)Pr(πj<t,j=i)=t(1q(t))+i=1nEπi[(πit)+]Pr(πj<t,j=i)t(1q(t))+i=1nEπi[(πit)+]q(t)
        • E [ max ⁡ i π i ] = E [ t + max ⁡ i ( π i − t ) ] = t + E [ max ⁡ i ( π i − t ) ] ≤ t + E [ max ⁡ i ( π i − t ) + ] ≤ t + ∑ i = 1 n E [ ( π i − t ) + ] E[\max_i \pi_i]=E[t+\max_i(\pi_i-t)]=t+E[\max_i(\pi_i-t)]\le t+E[\max_i(\pi_i-t)^{+}]\le t+\sum_{i=1}^{n}E[(\pi_i-t)^{+}] E[maxiπi]=E[t+maxi(πit)]=t+E[maxi(πit)]t+E[maxi(πit)+]t+i=1nE[(πit)+]
        • 对比①②两种不同方式的放缩结果, 设置 t t t使得 q ( t ) = 1 2 q(t)=\frac{1}{2} q(t)=21就可以证明定理成立
    1. 应用:
    • 单品拍卖
    • regular的分布 F 1 , F 2 , . . . , F n F_1,F_2,...,F_n F1,F2,...,Fn
    • 考虑 π i = ϕ i ( v i ) + \pi_i=\phi_i(v_i)^{+} πi=ϕi(vi)+作为第 i i i轮的奖励
    • 由Myerson的理论知最优期望收益 = E v ⃗ [ ∑ i ϕ i ( v i ) X i ∗ ( v ⃗ ) ] = E v ⃗ [ max ⁡ i ϕ i ( v i ) + ] =E_{\vec v}[\sum_{i}\phi_i(v_i)X_i^{*}(\vec v)]=E_{\vec v}[\max_i \phi_i(v_i)^{+}] =Ev [iϕi(vi)Xi(v )]=Ev [maxiϕi(vi)+]
    • Simple action: 目前并没有一个确切的定义说什么样的拍卖机制是相对simaple的, 但我们可以相信这种拍卖机制比Myerson的virtual welfare拍卖要相对simple
      • 选择 t t t使得 P r ( max ⁡ ϕ i ( v i ) + ≥ t ) = 1 2 Pr(\max \phi_i(v_i)^{+}\ge t)=\frac{1}{2} Pr(maxϕi(vi)+t)=21
      • 将奖励商品授予一个 ϕ i ( v i ) > t \phi_i(v_i)\gt t ϕi(vi)>t的竞拍者(if any, 有virtual value都大于 t t t的就随便给了)
      • Observation about the P.I.
        • 假设 π i ≥ t \pi_i\ge t πit对于多个 i i i, 确保满足即使策略会选择最差的那个竞拍者
        • by P.I. 这个Simple action期望的virtual surplus不小于实际最优解的一半
      • Implement: 实现这个拍卖
        • ① 设置reserve price r i = ϕ i ( t ) r_i=\phi_i(t) ri=ϕi(t), 来筛去那些低于阈值的竞拍者
        • ② 将商品给到剩余竞拍者中出价最高的那个人即可(if any)
        • ③ 最后按照次价付款即可
        • 这个机制唯一不好的地方就是存在价格歧视
      • 进一步地, 如果 n n n个分布 F 1 , F 2 , . . . , F n F_1,F_2,...,F_n F1,F2,...,Fn对于卖方来说未知, 这称为prior-independent auction, 本节不讨论
    1. 定理[Bulow-Kemperer](Slide P.48): 单品拍卖, n个 iid regular的分布 F F F, 有EXPECTED REVENUE OF VICKREY(有 n + 1 n+1 n+1个人的拍卖) >= EXPECTED OPT UNDER F(有 n n n个人的拍卖)
    • 即有 n + 1 n+1 n+1个人的二价拍卖最有期望收益不小于 n n n个人的最优解, 且VA的收益为 ϕ i ( 0 ) \phi_i(0) ϕi(0)
      • Slide的表述: That is, O P T F OPT_F OPTF is the Vickrey auction with the monopoly reserve price ϕ i ( 0 ) \phi_i(0) ϕi(0), where ϕ \phi ϕ is the virtual valuation function of F F F
    • 推论: 额外的竞争比最优拍卖格式更加重要
    • 证明:
      • 定义拍卖 A A A(with n + 1 n+1 n+1 个竞拍者)
        • ① 现在模拟OPT在 n n n个bidders中: 1,2,…,n
        • ② 如果在①中没有卖出去, 将商品免费送给第 n + 1 n+1 n+1个bidder,
      • Note: A A A的期望收益与OPT相同(有 n n n个bidders)
      • Note: A A A总是会分配商品
      • Note: A A A是一个DSIC的拍卖机制
      • 作为结束, 声称Vickrey最大化了期望收益在所有的拍卖中, 并且能够总是卖出商品
      • E v ⃗ [ ∑ p i ( v ⃗ ) ] = E v ⃗ [ ∑ i ϕ i ( v i ) X i ( v ⃗ ) ] ≤ E v ⃗ [ max ⁡ i ϕ i ( v i ) ] E_{\vec v}[\sum p_i(\vec v)]=E_{\vec v}[\sum_i \phi_i(v_i)X_i(\vec v)]\le E_{\vec v}[\max_i \phi_i(v_i)] Ev [pi(v )]=Ev [iϕi(vi)Xi(v )]Ev [maxiϕi(vi)] if always saling,
        • 第一个等号是对 A A A而言: EXPECTED REVENUE=EXPECTED VIRTUAL VALUE
        • 不等式右端其实就是Vickrey
        • ∑ i X i ( v ⃗ ) = 1 , ∀ v ⃗ \sum_i X_i(\vec v)=1, \forall \vec v iXi(v )=1,v
      • 原因: 为了最大化收益使得总是卖出商品, 则分配给竞拍者with最高的 ϕ i ( v i ) \phi_i(v_i) ϕi(vi)
      • Vickrey将商品给到竞拍者with最高的 v i v_i vi
    1. 更一般的多变量机制设计
    • n n n个竞拍者
    • 有限集合 Ω \Omega Ω of outcomes
    • i i i有一个私有的估值 v i ( ω ) v_i(\omega) vi(ω) 对于每个 ω ∈ Ω \omega∈\Omega ωΩ
    • 定理[Vickrey Clarke Graves]: 在每个环境中, 都有一个DSIC surplus-maximizing 机制
      • 这里并不能保证一定有一个多项式时间内能计算出的机制, 即relax了第三点
      • 证明:
        • ① 假设每个人都还是诚实竞价(truthful bids): { b ⃗ i } ∣ 1 n \{\vec b_i\}|_{1}^{n} {b i}1n, 其中 b ⃗ i \vec b_i b i根据 Ω \Omega Ω来索引, 注意这里的每个人的报价已经是要报出一串数, 而非一个数
          • 定义分配规则: X ( b ⃗ ) = arg max ⁡ ω ∈ Ω ∑ i = 1 n b i ( ω ) X(\vec b)=\argmax_{\omega∈\Omega}\sum_{i=1}^{n}b_i(\omega) X(b )=ωΩargmaxi=1nbi(ω)
        • ② 定义付款规则来达到DSIC: 前提要求分配规则是单调的
          • 问题: 单调分配规则的定义并不明确
          • 想法: 经济学上的外部性, 及向竞拍者 i i i要价externality
            • P i ( b ⃗ ) = max ⁡ ω ∈ Ω ∑ j ≠ i b i ( ω ) − ∑ j ≠ i b j ( ω ∗ ) P_i(\vec b)=\max_{\omega∈\Omega}\sum_{j\ne i}b_i(\omega)-\sum_{j\ne i}b_j(\omega^{*}) Pi(b )=maxωΩj=ibi(ω)j=ibj(ω)
            • max ⁡ ω ∈ Ω ∑ j ≠ i b i ( ω ) \max_{\omega∈\Omega}\sum_{j\ne i}b_i(\omega) maxωΩj=ibi(ω)是如果 i i i不在市场里面其他人的surplus是多少
            • ∑ j ≠ i b j ( ω ∗ ) \sum_{j\ne i}b_j(\omega^{*}) j=ibj(ω)是如果 i i i在市场里面其他人的surplus是多少, 其中 ω ∗ = X ( b ⃗ ) \omega^{*}=X(\vec b) ω=X(b )
            • 即由于 i i i的存在, 其他人的surplus变差了多少, 则 i i i需要付出多少钱
          • 证明这种外部性的想法是正确的: 即证明这种VCG的机制是DSIC的(surplus maximizing)
            • 固定 i , b ⃗ − i i, \vec b_{-i} i,b i, 其中 ω ∗ = X ( b ⃗ ) \omega^{*}=X(\vec b) ω=X(b ), 第 i i i个人的效用 = v i ( ω ) − p i ( b ⃗ ) = [ v i ( ω ) + ∑ j ≠ i b j ( ω ) ] − max ⁡ ω ∈ Ω ∑ j ≠ i b j ( ω ) =v_i(\omega)-p_i(\vec b)=[v_i(\omega)+\sum_{j\ne i}b_j(\omega)]-\max_{\omega∈\Omega}\sum_{j\ne i}b_j(\omega) =vi(ω)pi(b )=[vi(ω)+j=ibj(ω)]maxωΩj=ibj(ω)
            • 注意 max ⁡ ω ∈ Ω ∑ j ≠ i b j ( ω ) \max_{\omega∈\Omega}\sum_{j\ne i}b_j(\omega) maxωΩj=ibj(ω)这部分与 b ⃗ i \vec b_i b i是独立的
            • Best case for i i i, 机制挑选 ω ∗ ∈ arg max ⁡ ω ∈ Ω [ v i ( ω ) + ∑ j ≠ i b j ( ω ) ] \omega^{*}∈\argmax_{\omega∈\Omega}[v_i(\omega)+\sum_{j\ne i}b_j(\omega)] ωωΩargmax[vi(ω)+j=ibj(ω)]
            • VCG做了什么? VCG选择 ω ∗ ∈ arg max ⁡ ω ∈ Ω ∑ j = 1 n b j ( ω ) \omega^{*}∈\argmax_{\omega∈\Omega}\sum_{j=1}^{n}b_j(\omega) ωωΩargmaxj=1nbj(ω)
            • 从而推导出bidding b ⃗ i = v ⃗ i \vec b_i=\vec v_i b i=v i导致这个发生, 如果真实报价的话, VCG的选择就是你真实的选择
      • 另一种推论解释:
        • p i ( b ⃗ ) = b i ( ω ∗ ) − ( ∑ j = 1 n b j ( ω ∗ ) − max ⁡ ω ∈ Ω ∑ j ≠ i b j ( ω ) ) p_i(\vec b)=b_i(\omega^{*})-(\sum_{j=1}^{n}b_j(\omega^{*})-\max_{\omega∈\Omega}\sum_{j\ne i}b_j(\omega)) pi(b )=bi(ω)(j=1nbj(ω)maxωΩj=ibj(ω))
        • ∑ j = 1 n b j ( ω ∗ ) \sum_{j=1}^{n}b_j(\omega^{*}) j=1nbj(ω)是有你的社会surplus
        • max ⁡ ω ∈ Ω ∑ j ≠ i b j ( ω ) ) \max_{\omega∈\Omega}\sum_{j\ne i}b_j(\omega)) maxωΩj=ibj(ω))是没有你的社会surplus
        • 类似一价拍卖, 但是最后会给你一些补偿

    Lecture 5

    1. 回顾VCG
    • 总是可以找到一个DSIC的社会福利最大化机制
    • 每个人的付款应该是有他和没有他两种情况下, 整个社会surplus的差值
    • VCG举例:
      • Ex1: 单品拍卖
        • 3个bidders, Ω = { \Omega=\{ Ω={allocate to A , B , C } A, B, C\} A,B,C}
        • 分配情况收益是分配给 i i i的效用 v i v_i vi, 其中 i ∈ { A , B , C } i∈\{A,B,C\} i{A,B,C}, 其余情况都是零, 即outcome矩阵是一个对角阵, 对角线上是各个人的valuation
      • Ex2: 双边贸易 Bilateral Trade
        • 一个卖家, 成本 v S v_S vS
        • 一个买家, 估值 v B v_B vB
        • 但是一个中介想要促成交易(但是中介不知道 v S v_S vS v B v_B vB, 当然 v S < v B v_S<v_B vS<vB, 否则不应当去促成交易), 由VCG payment来看应当多少钱使得他们都会真实报价?
        • 解决方案: Ω = { \Omega=\{ Ω={成交, 不成交 } \} }, outcome矩阵是, 不成交买卖双方都是零, 成交的话卖家为 − v S -v_S vS, 买家为 v B v_B vB, 但是用VCG要求矩阵的数值非负, 此时我们将outcome矩阵平移, 即将卖家这行都加上 v S v_S vS(注意我们会选择outcome之和最大的那一种 ω \omega ω, 因此将某个参与者的outcome全都加一个数不影响最终的选择), outcome矩阵又变成了和单品拍卖一样的对角矩阵, [ ( 0 , − v S ) , ( 0 , v B ) ] → [ ( v S , 0 ) , ( 0 , v B ) ] [(0,-v_S),(0,v_B)] \rightarrow [(v_S,0),(0,v_B)] [(0,vS),(0,vB)][(vS,0),(0,vB)]
        • VCG付款规则: P S ( v ) = h S ( v B ) − u B ( ω ∗ ) P_S(v)=h_S(v_B)-u_B(\omega^{*}) PS(v)=hS(vB)uB(ω), h S h_S hS是卖家不在时别人的最大值
        • 直观上成交的话应该向卖家收一笔钱, 然后向买家付一笔钱,
        • 注意如果没有成交, VCG应该确保是不付钱 P S ( v ) = h S ( v B ) − u B ( P_S(v)=h_S(v_B)-u_B( PS(v)=hS(vB)uB(不成交 ) = 0 )=0 )=0, 因为 u B ( u_B( uB(不成交 ) = 0 )=0 )=0, 则 则 h_S$应该恒等于0
          • 在上节课里我们看到 h S h_S hS就是 max ⁡ ω ∈ Ω ∑ j ≠ i b i ( ω ) \max_{\omega∈\Omega}\sum_{j\ne i}b_i(\omega) maxωΩj=ibi(ω), 是可以随便取的, 但是后面一项不行与 b i b_i bi独立是不行的
        • 对于买家来说很容易证明是DSIC的, 因为诚实报价最优解, 放低报价不会增加收益
        • VCG付款规则: P B ( v ) = h B ( v S ) − u S ( ω ∗ ) P_B(v)=h_B(v_S)-u_S(\omega^{*}) PB(v)=hB(vS)uS(ω), h B h_B hB是买家不在时别人的最大值
        • 注意如果没有成交, VCG应该确保是不付钱 P B ( v ) = h B ( v S ) − u S ( P_B(v)=h_B(v_S)-u_S( PB(v)=hB(vS)uS(不成交 ) = 0 )=0 )=0, 因为 u S ( u_S( uS(不成交 ) = v S )=v_S )=vS, 则 h B h_B hB应该恒等于 v S v_S vS
        • 郭远方的一个想法: 中介要使得双方的付款都与他们自己的成本或估值是无关的, 因为要让他们诚实报价
      • Ex3: 造桥(公共品)
        • 造桥成本为 C C C
        • 桥造出来对城市中每个人都会有一个效用, 假设有 n n n个玩家, 每个人的效用是 v i v_i vi
        • 直观上应该是当 ∑ i = 1 n v i ≥ C \sum_{i=1}^{n}v_i\ge C i=1nviC时会造桥, 那么政府应当如何向这些人收钱?
        • ① 一种特殊情况: C = 100 C=100 C=100, n = 200 n=200 n=200, v i = 1 v_i=1 vi=1
          • 因为无论有没有某个 i i i, 决策是不会变的(199>100), 因此根据VCG来说是不付钱的
        • ② 一种特殊情况: 将①中的某个 i i i的效用是50, 其余99个人都是1, 那么向这个效用50的应当给他1块钱
        • 用VCG研究这个场景时应当去把政府也作为一个玩家加进来, 造桥的outcome是 − C -C C, 不造是0, 因此在②中应当是向这个效用50的人付款1元(有他就造, 其余人总效用为-100+99, 没有他就不造, 其余人效用为0, 发现效用变好了, 所以要付给他1块钱)
      • Ex4: 在一个网络图中买一条路径
        • 有向图中的每条边是一个player, 它会有一个cost, 起始点为 s s s, t t t
        • VCG的思想就是有这条边和没有这条边有多大路径增长, 以此来对每条边付钱
        • 以下面这个图为例: V = { A , B , C , D , E , F } V=\{A,B,C,D,E,F\} V={A,B,C,D,E,F}, E = { ( A , B , 3 ) , ( B , D , 2 ) , ( D , F , 2 ) , ( A , C , 2 ) , ( C , E , 3 ) , ( E , F , 1 ) , ( B , E , 1 ) , ( C , F , 5 ) } E=\{(A,B,3),(B,D,2),(D,F,2),(A,C,2),(C,E,3),(E,F,1),(B,E,1),(C,F,5)\} E={(A,B,3),(B,D,2),(D,F,2),(A,C,2),(C,E,3),(E,F,1),(B,E,1),(C,F,5)}
          • 最优解 A B E F ABEF ABEF, 成本为5
          • 当缺少 A B AB AB时变成 A C E F ACEF ACEF, 成本为6, 因此付给 A B AB AB 6 − 2 = 4 6-2=4 62=4, 因为 A B E F ABEF ABEF中要把 A B AB AB扔了
          • 同理给 B E BE BE的付款为2, 给 E F EF EF的付款为3
    1. 介绍一些VCG失败的场景
    • Ex1
      • n n n个bidders
      • M = { 1 , 2 , . . . , m } M=\{1,2,...,m\} M={1,2,...,m}是物品集合
      • Ω = { ( S 1 , S 2 , . . . , S n ) } \Omega =\{(S_1,S_2,...,S_n)\} Ω={(S1,S2,...,Sn)}为outcome, 注意不一定所有的物品都会被卖出去, S i S_i Si包含于 M M M代表第 i i i个人的bundle
      • i i i个bidder有一个私有的估值 v i ( S ) v_i(S) vi(S)对于每个bundle S S S包含于 M M M
        • v i ( ∅ ) = 0 v_i(\emptyset)=0 vi()=0
        • v i ( S ) ≥ v i ( T ) v_i(S)\ge v_i(T) vi(S)vi(T) T T T包含于 S S S
      • surplus目标函数: ∑ i = 1 n v i ( S i ) \sum_{i=1}^{n}v_i(S_i) i=1nvi(Si)
      • VCG无法计算这个问题:
        • ① 该问题求解是NP-hard, 难以求解目标函数最优解
        • ② 难以收集bid, 因为当有 m m m个物品时每个bidder需要提供 2 m 2^m 2m个报价
          • 因此引出ascending auctions: learn info on “need-to-know” basis, indirect auction
        • ③ 即时①②都不是问题, VCG可能有一个坏的收益属性
          • 举例说明: 比如只有两个物品 { A , B } \{A,B\} {A,B}, 两个bidder
          • bidder 1: v 1 ( A B ) = 1 v_1(AB)=1 v1(AB)=1, 其余为0
          • bidder 2: v 2 ( A B ) = v 2 ( A ) = 1 v_2(AB)=v_2(A)=1 v2(AB)=v2(A)=1, 其余为0
          • 显然VCG revenue为1, 不管踢掉哪个bidder, outcome差都是1
          • 假设现在加入一个bidder 3: v 3 ( A B ) = v 3 ( B ) = 1 v_3(AB)=v_3(B)=1 v3(AB)=v3(B)=1, 其余为0, 此时会把商品分给2和3, 但是此时revenue掉到了0, 多出一个人反而使得revenue减少了
          • 结论: VCG很容易使得bidder间发生勾结
        • ④ Relaxing DSIC 使得能导致一个新的gaming possibilities
          • Ex[Cromton/Schwartz '02] 频谱拍卖: 如5G的频段拍卖
            • #378 Rochester, USWest and Mcleod
            • 一种简单的解决方案: 本来我有几百个东西一起卖, 现在我分下来卖, 转化成单品拍卖
              • 注意拍卖顺序会对结果产生影响的
              • ① 单品拍卖总是生效吗?
                • A. 若商品是(mostly)替代品, 则大概有 v ( A B ) ≤ v ( A ) + v ( B ) v(AB)\le v(A)+v(B) v(AB)v(A)+v(B), 比如同一个地区的5G执照, 这种情况下分开卖一般不会影响revenue
                • B. 若商品是互补品, 则会有 v ( A B ) ≥ v ( A ) + v ( B ) v(AB)\ge v(A)+v(B) v(AB)v(A)+v(B), 比如不同地区的5G执照, 这种情况下就很有意思了
                • 错误1: 序列式的拍卖 sequentially auction
                  • 一种简单的案例:
                    • 相同的商品, 每个bidder只想要其中一个
                    • 问题: 不是DSIC的, 需要猜测拍卖价格, 比如估值最高者未必会在第一轮进场, 因为如果估值第二高者第一轮进场, 最高者第二轮进场就可以至多以第三高价成交
                    • Ex: Swiss 2000 March ① 28MHZ block (121 mil) ② 28MHZ block (134 mil) ③ 56MHZ block (55 mil) <-- double bid
                • 错误2: 密封式拍卖 sealed auction
                  • Ex: NewZealand 1990 roughly identical goods, 一个bidder可能会要多个商品
                    • 使用同时的二价密封拍卖, 即bidder要同时提交所有商品的竞价
                    • 对于bidders来说很难来玩这个博弈, 新西兰政府预计能收到250mil, 但是结果只收到了36m
                    • 有一场, 第一名出了十万, 第二名出了6块, 结果第一名只需要付出6块就可以拿到商品
                    • 一种解决方案是不要次价拍卖, 就用一价拍卖来搞, 但是仍然会有一些问题
    1. 解决上面频谱拍卖的目前一个解决方案: Simultaneous ascending auction (SAA)
    • 每一轮, 每个bidder可以对任何一个商品集合的子集进行报价
    • 最高报价的bidder和他的bid将被展示
    • 当某一轮没有人再出价, 结束拍卖
    • 行动规则: roughly, number of items you are bidding on only drops with time
    • Big win: price discovery
    • 举个例子: 2个相同商品, 3个bidders, 其实本质上大家都会在较低的那个商品上竞价, 两个商品会稳步上升, 直到超过第三名的估值
      • allows mid-course corrections: 允许中间修正
      • fixes miscoordination with smaller goods: 修正竞价低的商品的不协调性
      • minor merit: valuation discovery
    • 总体来说, SAA运行的还不错, 现在美国政府基本都按照SAA来竞拍
      • 接近最优的剩余(near-optimal surplus): 事实上其实很难评价是否接近最优, 甚至最优是什么都难以有定论, 不过是可以通过一些现象来评价:
        • no resale: 没有发生转卖
        • similar price: 竞拍价格类似
        • bidders get closed areas: bidder都拿到了离他们较近的区域
    • 问题:
      • ① demand reduction
        • 2个相同商品, 2个竞拍者(好像只卖出一个)
        • v 1 ( 1 ) = 10 v_1(1)=10 v1(1)=10, v 1 ( 2 ) = 20 v_1(2)=20 v1(2)=20, v 2 ( 1 ) = v 2 ( 2 ) = 8 v_2(1)=v_2(2)=8 v