LP-Duality and the Cores of Games
21Vijay V. Vazirani (UC Irvine)
https://simons.berkeley.edu/talks/vijay-v-vazirani-uc-irvine-2023-10-27
Online and Matching-Based Market Design
Even though LP-duality has played a central role in the study of the core, right from its early days to the present time, basic gaps still remain. I will summarize three papers which address these gaps:
Paper 1 defines new matching-based games, with important applications, and characterizes their cores.
It also gives efficient algorithms for computing core imputations with enhanced fairness properties: min-max fair, max-min fair and equitable core imputations.
Paper 2 extends the scope of the notion of core beyond profit --- equivalently cost or utility --- sharing.
The game in this paper is not a cooperative game, it is a game against nature.
Paper 3 rectifies the fact that the general graph matching game has an empty core by giving the notion of 2/3-approximate core.
This talk will be self-contained.