We design novel mechanisms for welfare-maximization in two-sided markets. That is, there are buyers willing to purchase items and sellers holding items initially, both acting rationally and strategically in order to maximize utility. Our mechanisms are designed based on a powerful correspondence between two-sided markets and prophet inequalities. They satisfy individual rationality, dominant-strategy incentive compatibility, budget-balance constraints and give constant-factor approximations to the optimal social welfare. We improve previous results in several settings: Our main focus is on matroid double auctions, where the set of buyers who obtain an item needs to be independent in a matroid. We construct two mechanisms, the first being a $1/3$-approximation of the optimal social welfare satisfying strong budget-balance and requiring the agents to trade in a customized order, the second being a $1/2$-approximation, weakly budget-balanced and able to deal with online arrival determined by an adversary. In addition, we construct constant-factor approximations in two-sided markets when buyers need to fulfill a knapsack constraint. Also, in combinatorial double auctions, where buyers have valuation functions over item bundles instead of being interested in only one item, using similar techniques, we design a mechanism which is a $1/2$-approximation of the optimal social welfare, strongly budget-balanced and can deal with online arrival of agents in an adversarial order.


翻译:我们设计了在双面市场实现福利最大化的新机制。也就是说,有买家愿意购买物品和卖主最初持有物品,既合理又具有战略意义,以便最大限度地发挥效用。我们的机制是建立在双面市场和先知不平等之间强有力的对应关系基础上的。它们满足个人理性、主导战略激励兼容性、预算平衡制约和对最佳社会福利的一贯因素近似。我们在若干环境下改进了以往的结果:我们的主要重点是双向拍卖:我们主要关注的是机器人双向拍卖,获得物品的买主需要独立地使用配机。我们建立了两个机制,第一个机制是用1/3美元达成最佳社会福利满足强有力的预算平衡,要求代理商按定制的顺序进行交易,第二个机制是1/2美元达标,预算平衡薄弱,能够应对由对手决定的在线抵达。此外,当买主需要履行Knapsack限制时,我们在双面市场上可以建立固定的近相近。此外,在双向拍卖中,在组合的双向价格中,一个项目中,购买者只能使用一美元最佳预算交易的排序,在一款上,购买者是最佳预算交易中,一个对1美元进行最佳预算交易。

0
下载
关闭预览

相关内容

【经典书】算法博弈论,775页pdf,Algorithmic Game Theory
专知会员服务
148+阅读 · 2021年5月9日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
【Java实现遗传算法】162页pdf,Genetic Algorithms in Java Basics
专知会员服务
43+阅读 · 2020年7月19日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
已删除
将门创投
4+阅读 · 2018年6月26日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
Arxiv
0+阅读 · 2021年7月22日
Incentivizing Compliance with Algorithmic Instruments
VIP会员
相关VIP内容
【经典书】算法博弈论,775页pdf,Algorithmic Game Theory
专知会员服务
148+阅读 · 2021年5月9日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
【Java实现遗传算法】162页pdf,Genetic Algorithms in Java Basics
专知会员服务
43+阅读 · 2020年7月19日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
相关资讯
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
已删除
将门创投
4+阅读 · 2018年6月26日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
Top
微信扫码咨询专知VIP会员