M.Sc Thesis | |

M.Sc Student | Rozen Rakefet |
---|---|

Subject | Ex Post Equilibrium for Two Buyers in the VCG Combinatorial Auctions |

Department | Department of Mathematics |

Supervisor | PROF. Ron Holzman |

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.