||Introduction to automated mechanism design, with a case study on auctions with artificial payments
2017-01-25 , 奈良先端科学技術大学院大学
Algorithmic game theory is the study of interdisciplinary topics that lie in the intersection of computer science and microeconomics. In this talk, we introduce one subfield of algorithmic game theory, which is called automated mechanism design. Automated mechanism design studies how to use computational techniques to design economic mechanisms (rules for social decision problems). This talk does not assume any prior knowledge in game theory or mechanism design, as we will introduce all the basic concepts in the beginning of the talk. Besides the basic concepts, we will also focus on one main case study, as detailed below:We study the problem of allocating a single item repeatedly among multiple competing agents, in an environment where monetary transfers are not possible. We design (Bayes-Nash) incentive compatible mechanisms that do not rely on payments, with the goal of maximizing expected social welfare. We introduce an artificial payment system, which enables us to construct repeated allocation mechanisms without payments based on one-shot allocation mechanisms with payments. We evaluate mechanisms based on their competitive ratios. Our resulting mechanisms are proved to achieve very high competitive ratios, which implies that for repeated allocation, artificial payments may be used to replace real monetary payments, without incurring too much loss in social welfare.