Events
New Insights into the Classic Shapley-Shubik Work: the Core of the Matching Game
Vijay Vazirani, Distinguished Professor at the University of California, Irvine
Attend Virtually or In Person @ SEC LL2. 224.
The core is a quintessential solution concept in cooperative game theory --- it contains all ways of distributing the total profit of a game among individual agents in such a way that the grand coalition remains intact, i.e., a sub-coalition will not be able to generate more profit by itself and therefore has no incentive to secede. The classic 1971 paper of Shapley and Shubik characterized the core of the assignment game using ideas from matching theory and LP-duality theory and their highly non-trivial interplay.
We pose and resolve two basic questions:
1). Do core imputations spread the profit more-or-less evenly or do they restrict them to certain chosen agents?
If the latter, what characterizes these ``chosen'' agents?
2). Whereas the core of the assignment game is always non-empty, that of the general graph matching game can be empty.
Is there a way of salvaging the situation via the notion of an approximate core? This talk is completely self-contained. It is based on:
https://www.sciencedirect.com/science/article/pii/S0899825622000239?via%3Dihubhttps://arxiv.org/pdf/2202.00619.pdf
Vijay Vazirani got his undergraduate degree from MIT in 1979 and his PhD from the University of California, Berkeley in 1983. He is currently a Distinguished Professor at the University of California, Irvine.
Vazirani has made fundamental contributions to several areas of the theory of algorithms, including algorithmic matching theory, approximation algorithms and algorithmic game theory, as well as to complexity theory, in which he established, with Les Valiant, the hardness of unique solution instances of NP-complete problems. Over the last four years, he has been working on algorithms for matching markets.
In 2001 he published Approximation Algorithms, which is widely regarded as the definitive book on the topic. In 2007, he published the co-edited book Algorithmic Game Theory. Another co-edited book, Online and Matching-Based Market Design, will be published by Cambridge University Press in Fall 2022; see its flyer: https://www.ics.uci.edu/~vazirani/flyer.pdf
