טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentMarina May
SubjectThe Incompatibility of Strategy-Proofness and Pareto-
Optimality in Quasi-Linear Settings with Public
Budget Constraints
DepartmentDepartment of Industrial Engineering and Management
Supervisor Professor Lavi Aharon Ron
Full Thesis textFull thesis text - English Version


Abstract

Almost all of the studies regarding auction theory focus on the player's value of getting one specific alternative or another and completely ignore the existence of players' maximum upper bound on their possible payment to the auction - their budgets. This fact often causes a mismatch between practice and theory while attempting actual implementation of last. The existing literature studying budgets indicates that addressing them properly to the model breaks down the usual quasi- linear setting and causes significant changes in it's conception and techniques.

We study the problem of allocating multiple identical items that may be comple- ments to budget-constrained bidders with private values. We show that there does not exist a deterministic mechanism that is individually rational, strategy-proof, Pareto-efficient, and that does not make positive transfers. This is true even if there are only two players, two items, and the budgets are common knowledge. The same impossibility naturally extends to more abstract social choice settings with an ar- bitrary outcome set, assuming players with quasi-linear utilities and public budget limits. Thus, the case of infinite budgets (in which the VCG mechanism satisfies all these properties) is really the exception.