IJCAI-2021 Tutorial
Mechanism Design without Money:
Matching, Facility Location, and Beyond
Aug 21 20:00 – 2:00 (Next day) Montreal Time (UTC-4)
Presenters:
Haris Aziz
UNSW Sydney
Hau Chan
University of Nebraska-Lincoln
Hadi Hosseini
Pennsylvania State University
Chenhao Wang
University of Nebraska-Lincoln
Tutorial Description:
Algorithmic mechanism design is the study of designing efficient mechanisms that elicit private information from self-interest and rational agents in order to achieve desirable outcomes while satisfying desirable properties. While the area of mechanism design is originated from the economic literature, computer scientists and AI researchers have made significant contributions to this area from the algorithmic and computational perspectives in the last decades. In a typical setting, the designed mechanism takes agents’ private information and incentives into consideration (as input), and computes/outputs, in polynomial time, an (approximately) optimal outcome that provides necessary incentives for the agents to reveal their private information truthfully.
In essence, a mechanism is a function that selects an outcome given the reports of the agents, and it is strategy-proof if it guarantees the truthful reports of agents. Usually, money is a useful tool to guarantee the strategy-proofness, however, it is noticed that “there are many important environments where money cannot be used as a medium of compensation” (Schummer and Vohra), due to ethical considerations (e.g., in political decision making) or legal considerations (e.g., in kidney exchange). While truthfulness/strategy-proofness is arguably the most important property for the mechanisms, social planners seek other important properties for the mechanisms in various settings without using money as well. As a result of its applicability to model realistic settings, mechanism design without money has been widely studied in the last few decades, especially in the AI communities, where we see tremendous growth in both the published literature and applications. Moreover, numerous applications of mechanism design without money have been deployed in the real world. For example, the celebrated Nobel-prize works of Shapley and Roth for stable matching apply to many domains such as school choice and marriage matching, and the mechanisms proposed have been successful used by the National Resident Matching Program (a system that matches residency applicants to hospitals) of the USA.
Stable Matching
In the proposed tutorial on Mechanism Design without Money: Matching, Facility Location, and Beyond, the audiences will be
(1) introduced to fundamental classical mechanism design settings without money,
(2) exposed to the design of mechanisms to ensure desirable properties (such as strategy-proofness, efficiency, and performance),
(3) exposed to the main applications of mechanism design without money as well as its current trends and future directions
Presenters' Short Bios:
Haris Aziz, School of Computer Science and Engineering, UNSW Sydney, Barker St, Kensington NSW 2052, Australia. Email: haziz@cse.unsw.edu.au.
Dr. Aziz's research interests lie at the intersection of artificial intelligence, theoretical computer science, and mathematical social sciences, especially computational social choice and algorithmic game theory.
Dr. Aziz is a Scientia Associate Professor at UNSW Sydney, leader of the Algorithmic Decision Theory group, and director of the Sydney EconCS network.
Dr. Aziz has given a tutorial on topics in computational game theory, market design and social choice theory at various conferences and summer schools including Canberra AI Summer School, PRICAI, and Australasian AI.
Hau Chan, Department of Computer Science and Engineering, University of Nebraska-Lincoln, 1400 R St, Lincoln, NE 68588. Email: hchan3@unl.edu.
Dr. Chan has worked at the intersection of multi-agent systems and economics. His earlier work focuses on applying graphical games to model and study interdependent security domains (e.g., security investment decisions). His recent and ongoing work includes the study of games with complex strategy spaces (e.g., compact representations and computations), the application of game theory to social science domains (e.g., security, network congestion, and self-organization), and the study of facility location problems (from the mechanism design perspective). The relevant work includes facility location problems with capacity constraints, facility location from the fairness perspective, and facility location from the network perspective.
Dr. Chan is currently an assistant professor in the Department of Computer Science and Engineering at the University of Nebraska-Lincoln. He has taught Networks, Markets, and Crowds, Computational Game Theory and Its Applications, and Data Structures and Algorithms.
Dr. Chan has given a tutorial on topics in computational game theory at AAMAS 2019, IJCAI 2019, AAMAS 2020, IJCAI 2020, and the Summer School on Game Theory and Social Choice 2021 (organized by the Department of Computer Science, City University of Hong Kong).
Hadi Hosseini, College of Information Sciences and Technology The Pennsylvania State University Westgate Building, University Park PA 16802, USA. Email: hadi@psu.edu.
Dr. Hosseini's research interest is at the interface of artificial intelligence and economics. In particular, he studies theoretical and algorithmic aspects of a variety of problems in matching, fair division, and computational social choice.
Dr. Hosseini is an assistant professor at the Pennsylvania State University. He has developed and taught courses on multi-agent systems, computational social choice, and algorithm design. He is the founder of MatchU.ai, a not-for-profit publicly available website that blends education and research by offering an interactive platform for socially desirable decision-making.
Chenhao Wang, Department of Computer Science and Engineering, University of Nebraska-Lincoln, 1400 R St, Lincoln, NE 68588. Email: chenhwang4-c@my.cityu.edu.hk.
Dr. Wang has a research interest in algorithmic game theory and approximation algorithms. His recent and ongoing work extensively studies mechanism design for facility location games, voting, and fair division. The relevant work includes characterizing strategyproof mechanisms for dual-role facility location games, providing tight bounds for two opposite-facility location games, and designing voting rules with low distortion.
Dr. Wang is currently a postdoc researcher in the Department of Computer Science and Engineering at the University of Nebraska-Lincoln.
Tutorial Notes:
Tutorial Recordings and Slides [link]