[Sequence announcement] Introduction to Mechanism Design

Mechanism de­sign is the the­ory of how to con­struct in­sti­tu­tions for strate­gic agents, span­ning ap­pli­ca­tions like vot­ing sys­tems, school ad­mis­sions, reg­u­la­tion of mo­nop­o­lists, and auc­tion de­sign. Think of it as the en­g­ineer­ing side of game the­ory, build­ing al­gorithms for strate­gic agents. While it doesn’t have much to say about ra­tio­nal­ity di­rectly, mechanism de­sign pro­vides tools and re­sults for any­one in­ter­ested in world op­ti­miza­tion.

In this se­quence, I’ll touch on

  • The ba­sic mechanism de­sign frame­work, in­clud­ing the rev­e­la­tion prin­ci­ple and in­cen­tive com­pat­i­bil­ity.

  • The Gib­bard-Sat­terth­waite im­pos­si­bil­ity the­o­rem for strat­e­gyproof im­ple­men­ta­tion (a close analogue of Ar­row’s The­o­rem), and re­stricted do­mains like sin­gle-peaked or quasilin­ear prefer­ence where we do have pos­i­tive re­sults.

  • The power and limi­ta­tions of Vick­rey-Clarke-Groves mechanisms for effi­ciently al­lo­cat­ing goods, gen­er­al­iz­ing Vick­rey’s sec­ond-price auc­tion.

  • Char­ac­ter­i­za­tions of in­cen­tive-com­pat­i­ble mechanisms and the rev­enue equiv­alence the­o­rem.

  • Profit-max­i­miz­ing auc­tions.

  • The My­er­son-Sat­terth­waite im­pos­si­bil­ity for bilat­eral trade.

  • Two-sided match­ing mar­kets à la Gale and Shap­ley, school choice, and kid­ney ex­change.

As the list above sug­gests, this se­quence is go­ing to be semi-tech­ni­cal, but my fore­most goal is to con­vey the in­tu­ition be­hind these re­sults. Since mechanism de­sign builds on game the­ory, take a look at Yvain’s Game The­ory In­tro if you want to brush up.

Var­i­ous re­sources:

I plan on fol­low­ing up on this se­quence with an­other fo­cus­ing on group ra­tio­nal­ity and in­for­ma­tion ag­gre­ga­tion, sur­vey­ing scor­ing rules and pre­dic­tion mar­kets among other top­ics.

Sugges­tions and com­ments are very wel­come.