Local stability in kidney exchange programs

• Tipo: Artigo em Revista Científica Internacional
• Data: 2025

Autores

Baratto, M (Autor) Outra; Crama, Y (Autor) Outra; Joao Pedro Pedroso (Autor) FCUP; Viana, A (Autor) Outra

Revista

A Revista está pendente de validação pelos Serviços Administrativos.

Título: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH

Vol. 320

Páginas: 20-34

ISSN: 0377-2217

Indexação

ISI Web of Knowledge - 0 Citações

Scopus - 1 Citação

Outras Informações

ID Authenticus: P-011-48P

DOI: 10.1016/j.ejor.2024.07.031

Abstract (EN): When each patient of a kidney exchange program has a preference ranking over its set of compatible donors, questions naturally arise surrounding the stability of the proposed exchanges. We extend recent work on stable exchanges by introducing and underlining the relevance of a new concept of locally stable, or L-stable, exchanges. We show that locally stable exchanges in a compatibility digraph are exactly the so-called local kernels (L-kernels) of an associated blocking digraph (whereas the stable exchanges are the kernels of the blocking digraph), and we prove that finding a nonempty L-kernel in an arbitrary digraph is NP-complete. Based on these insights, we propose several integer programming formulations for computing an L-stable exchange of maximum size. We conduct numerical experiments to assess the quality of our formulations and to compare the size of maximum L-stable exchanges with the size of maximum stable exchanges. It turns out that nonempty L-stable exchanges frequently exist in digraphs which do not have any stable exchange. All the above results and observations carry over when the concept of (locally) stable exchanges is extended to the concept of (locally) strongly stable exchanges.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 15