Show simple item record

EPTAS for stable allocations in matching games

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorGarrido-Lucero, Felipe
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorLaraki, Rida
HAL ID: 179670
ORCID: 0000-0002-4898-2424
dc.date.accessioned2022-02-28T09:14:22Z
dc.date.available2022-02-28T09:14:22Z
dc.date.issued2021
dc.identifier.urihttps://basepub.dauphine.psl.eu/handle/123456789/22784
dc.language.isoenen
dc.subjectEPTASen
dc.subjectStable Matchingen
dc.subjectGeneralized Nash Equilibriumen
dc.subjectZero-sum Gamesen
dc.subjectInfinitely repeated Gamesen
dc.subjectMatching with Transferen
dc.subject.ddc004en
dc.titleEPTAS for stable allocations in matching gamesen
dc.typeDocument de travail / Working paper
dc.description.abstractenGale-Shapley introduced a matching problem between two sets of agents where each agent on one side has a preference over the agents of the other side and proved algorithmically the existence of a pairwise stable matching (i.e. no uncoupled pair can be better off by matching). Shapley-Shubik, Demange-Gale, and many others extended the model by allowing monetary transfers. In this paper, we study an extension where matched couples obtain their payoffs as the outcome of a strategic game and more particularly a solution concept that combines Gale-Shapley pairwise stability with a constrained Nash equilibrium notion (no player can increase its payoff by playing a different strategy without violating the participation constraint of the partner). Whenever all couples play zero-sum matrix games, strictly competitive bi-matrix games, or infinitely repeated bi-matrix games, we can prove that a modification of some algorithms in the literature converge to an ε-stable allocation in at most O(1ε) steps where each step is polynomial (linear with respect to the number of players and polynomial of degree at most 5 with respect to the number of pure actions per player).en
dc.publisher.cityParisen
dc.relation.ispartofseriestitlePreprint Lamsadeen
dc.subject.ddclabelInformatique généraleen
dc.description.ssrncandidatenon
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.date.updated2022-02-28T09:13:11Z
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
2107.07440.pdf
Size:
401.9Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record