Machine Learning for Mechanism Design: Learning Payment Rules via Discriminant-Based


March 28, 2013


John Lai




In mechanism design, we wish to find an allocation rule and payment rule that together maximize the designer’s objective and induce agents to reveal their private information truthfully. In this work, we consider the problem of finding a payment rule to pair with any given allocation rule. The allocation rule is not constrained to have the necessary properties to guarantee existence of an incentive-compatible payment rule.

To solve this problem, we establish a novel connection between multi-class classification in machine learning and incentive-compatible mechanisms. Given any allocation rule, we consider the multi-class classification problem of predicting the outcome chosen by the allocation given agent preferences. If we impose an appropriate structure on this multi-class classifier, then a classifier that perfectly predicts the allocation induces an incentive-compatible payment rule. In cases where perfect prediction is not possible, minimizing the generalization error of the classifier corresponds to finding a payment rule that minimizes the regret an agent experiences when making truthful reports and facing truthful agents. We report experimental results for multi-minded combinatorial auctions and the assignment problem, validating the approach on approximate and non-utilitarian allocation rules. Time permitting, I will discuss applications of our approach to combinatorial auctions where agents have graphical valuations. An interesting connection between graphical valuations and Markov random fields allows us to improve the scalability of the training problem.


John Lai

John Lai is a Ph.D. student in Computer Science at Harvard University. He is advised by Professor David Parkes and is a member of the EconCS group. He is interested in computational aspects of mechanism design and has published papers in Games and Economic Behavior, ACM EC, AAAI, IJCAI, SAGT, WWW, and HCOMP. He is a recipient of the best paper award at ACM EC ’12 and NDSEG and NSF graduate fellowships. John was a software engineer at Google and did his undergraduate work at Harvard College, where he graduated summa cum laude in computer science and mathematics.