LP-Duality and the Cores of Games

Published on ● Video Link: https://www.youtube.com/watch?v=7XdUm9x2URg



Category:
Let's Play
Duration: 44:31
851 views
21


Vijay 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.







Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Online and Matching-Based Market Design
Vijay V. Vazirani