This paper addresses two deficiencies of models in the area of matching-based market design. The first arises from the recent realization that the most prominent solution that uses cardinal utilities, namely the Hylland-Zeckhauser (HZ) mechanism, is intractable; in particular, the problem of computing even an approximate equilibrium for it is PPAD-complete. The second is the extreme paucity of models that use cardinal utilities; this stands in sharp contrast with general equilibrium theory, which has defined and extensively studied several fundamental market models to address a number of specialized and realistic situations. Our paper addresses both these issues by proposing Nash-bargaining-based matching market models. Since the Nash bargaining solution is captured by a convex program, efficiency follow; in addition, it possesses a number of desirable game-theoretic properties. Our approach yields a rich collection of models: for one-sided as well as two-sided markets, for Fisher as well as Arrow-Debreu settings, and for a wide range of utility functions, all the way from linear to Leontief. We also give very fast implementations for these models which solve large instances, with $n = 2000$, in one hour on a PC, even for a two-sided matching market. A number of new ideas were needed, beyond the standard methods, to obtain these implementations.


翻译:本文论述基于匹配的市场设计领域模式的两个缺陷,第一个原因是,最近认识到使用主要公用事业的最突出解决办法,即Hylland-Zeckhauser(HZ)机制是棘手的;特别是,甚至计算一个近似均衡的问题也是PPAD的完整。第二个问题是,使用主要公用事业的模式极为缺乏;这与一般均衡理论形成鲜明对照,后者界定并广泛研究了若干基本市场模式,以解决一些专门和现实的情况。我们的文件通过提出基于纳什的基于谈判的匹配市场模式来处理这两个问题。由于纳什讨价还价方案被一个康韦克斯方案所抓住,效率随后;此外,它拥有一些理想的游戏理论性能。我们的方法产生了丰富的模型汇编:单面市场和双面市场,渔业和箭头-Debreu环境,以及从线性到莱昂蒂伊夫等一系列广泛的实用功能。我们还非常迅速地执行这些模型,这些模型解决了大实例,而价格=2000年标准价格,在1小时后,这些标准在1个市场中获得了新的标准。

0
下载
关闭预览

相关内容

ACM/IEEE第23届模型驱动工程语言和系统国际会议,是模型驱动软件和系统工程的首要会议系列,由ACM-SIGSOFT和IEEE-TCSE支持组织。自1998年以来,模型涵盖了建模的各个方面,从语言和方法到工具和应用程序。模特的参加者来自不同的背景,包括研究人员、学者、工程师和工业专业人士。MODELS 2019是一个论坛,参与者可以围绕建模和模型驱动的软件和系统交流前沿研究成果和创新实践经验。今年的版本将为建模社区提供进一步推进建模基础的机会,并在网络物理系统、嵌入式系统、社会技术系统、云计算、大数据、机器学习、安全、开源等新兴领域提出建模的创新应用以及可持续性。 官网链接:http://www.modelsconference.org/
深度强化学习策略梯度教程,53页ppt
专知会员服务
175+阅读 · 2020年2月1日
强化学习最新教程,17页pdf
专知会员服务
166+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
186+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
96+阅读 · 2019年10月9日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
计算机类 | ISCC 2019等国际会议信息9条
Call4Papers
5+阅读 · 2018年12月25日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
15+阅读 · 2018年12月24日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
18+阅读 · 2019年1月16日
VIP会员
相关资讯
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
计算机类 | ISCC 2019等国际会议信息9条
Call4Papers
5+阅读 · 2018年12月25日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
15+阅读 · 2018年12月24日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员