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

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.