Stablity Scores: Measuring Coalitional Stability

We introduce a measure for the level of stability against coalitional deviations, called \emph{stability scores}, which generalizes widely used notions of stability in non-cooperative games. We use the proposed measure to compare various Nash equilibria in congestion games, and to quantify the effect of game parameters on coalitional stability. For our main results, we apply stability scores to analyze and compare the Generalized Second Price (GSP) and Vickrey-Clarke-Groves (VCG) ad auctions. We show that while a central result of the ad auction literatures is that the GSP and VCG auctions implement the same outcome in one of the equilibria of GSP, the GSP outcome is far more stable. Finally, a modified version of VCG is introduced, which is group strategy-proof, and thereby achieves the highest possible stability score.

Authors

• Michal Feldman Tel Aviv University Microsoft ILDC
• Reshef Meir Technion--Israel Institute of Technology
• Moshe Tennenholtz Technion - Israel Institute of Technology

Keywords

• Game theory
• Auctions
• Mechanism design
• Solution concepts