טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentFeldman Ido
SubjectOptimal Auctions for Correlated Bidders: Ex-Post
vs. Ex-Interim Individual Rationality
DepartmentDepartment of Industrial Engineering and Management
Supervisor ASSOCIATE PROF. Aharon Ron Lavi


Abstract

We study Dominant-Strategy Incentive-Compatible (DSIC) revenue-maximizing auctions (“optimal” auctions) for a single-item and correlated private values. We analyze two questions that naturally arise from a comparison of the more recent literature on auctions that are Ex-Post Individually Rational (EPIR) versus the classic literature that requires only Ex-Interim Individual Rationality (EIIR). First, we give tight lower and upper bounds on the ratio of the revenue of the optimal EPIR auction and the revenue of the optimal EIIR auction. This bound is expressed as a non-decreasing function of the expected social welfare of the underlying distribution. Second, we give a simple characterization of DSIC and EIIR auctions, which yields several implications and open questions. In particular, we present a set of simple auctions that can approximate a constant fraction of the revenue of the optimal DSIC and EIIR auction for any constant number of bidders and any distribution. We also show that there exist distributions that “almost” satisfy the full rank assumption of Cr?emer and McLean for which the revenue of the optimal DSIC and EIIR auction is only an unboundedly small fraction of the social welfare.