The power of randomness in Bayesian optimal mechanism design

被引：49
作者：
Chawla, Shuchi [1 ]
Malec, David [1 ]
Sivan, Balasubramanian [1 ]
机构：
[1] Univ Wisconsin, Dept Comp Sci, Madison, WI 53706 USA
来源：
GAMES AND ECONOMIC BEHAVIOR | 2015年 / 91卷
基金：
美国国家科学基金会;
关键词：
Mechanism design; Randomness; Revenue; Lotteries; Screening; Multi-product pricing; FIRM;
D O I：
10.1016/j.geb.2012.08.010
中图分类号：
F [经济];
学科分类号：
02 ;
摘要：
We investigate the power of randomness in the context of a fundamental Bayesian optimal mechanism design problem a single seller aims to maximize expected revenue by allocating multiple kinds of resources to "unit-demand" agents with preferences drawn from a known distribution. When the agents' preferences are single-dimensional Myerson's seminal work (1981) shows that randomness offers no benefit the optimal mechanism is always deterministic. In the multi-dimensional case, when agents' preferences are arbitrarily correlated, Briest et al. (2010) showed that the gap between the expected revenue obtained by an optimal randomized mechanism and an optimal deterministic mechanism can be unbounded even when a single agent is offered only 4 services. We show that when the agents' values involve no correlation or a specific kind of positive correlation, the benefit of randomness is only a small constant factor. (C) 2012 Elsevier Inc. All rights reserved.
引用
收藏
页码：297 / 317
页数：21
相关论文
共 29 条
[1]  
Aigner M, 1997, CLASSICS MATH
[2]   Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers [J].
Alaei, Saeed .
2011 IEEE 52ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2011), 2011, :512-521
[3]   Price discrimination by a many-product firm [J].
Armstrong, M .
REVIEW OF ECONOMIC STUDIES, 1999, 66 (01) :151-168
[4]  
Balcan MF, 2008, EC'08: PROCEEDINGS OF THE 2008 ACM CONFERENCE ON ELECTRONIC COMMERCE, P50
[5]  
BALCAN MF, 2006, P 7 ACM C EL COMM, P29, DOI [10.1145/1134707.1134711, DOI 10.1145/1134707.1134711]
[6]  
Briest P., 2006, EL C COMP COMPL ECCC
[7]  
Briest P, 2010, PROC APPL MATH, V135, P585
[8]  
Brualdi RichardA., 1969, B AUST MATH SOC, V1, P161
[9]   Extreme-Value Theorems for Optimal Multidimensional Pricing [J].
Cai, Yang ;
Daskalakis, Constantinos .
2011 IEEE 52ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2011), 2011, :522-531
[10]  
Cai Yang., 2012, Proceedings of the forty-fourth annual ACM symposium on Theory of computing, P459
123