טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentRozen Rakefet
SubjectEx Post Equilibrium for Two Buyers in the VCG Combinatorial
Auctions
DepartmentDepartment of Mathematics
Supervisor Professor Ron Holzman


Abstract

The research deals with combinatorial auction mechanisms in which a socially optimal outcome is desired. The desired result is attained by mechanisms where truth telling is a dominant strategy. A well-known class of truth revealing mechanisms is the Vickrey-Clarke-Groves (VCG) mechanisms. However, these mechanisms raise a problem of high communication and computational complexity. In search of a solution to this problem, R. Holzman, N. Kfir-Dahav, D. Monderer, M. Tennenholtz analyzed a type of ex post equilibrium called bundling equilibrium. They showed that if the number of buyers is at least three, S - a set of subsets of the set A of goods - induces a bundling equilibrium if and only if it is a quasi field. Holzman and Monderer showed that if the number of players is at least three, every ex post equilibrium in the VCG combinatorial auction mechanisms is a bundling equilibrium and is symmetric.


             This study extends their solution by characterizing the ex post equilibria in the VCG combinatorial auction mechanisms for two players. It is shown that there are two families of equilibria. The first is when players reveal their true value of A. Then the resulting equilibria are bundling but not symmetric. The second is when the players do not reveal their true value of A. Then we show that the players report their value for proper subsets of A as zero. Their reported value of A follows a parallelogram scheme, which is subject to certain rules.


             These results complement their research, and give a full characterization of ex post equilibrium in the VCG combinatorial auction mechanisms.