Arrow Research search

Author name cluster

Péter Biró

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

13 papers
1 author row

Possible papers

13

JAAMAS Journal 2024 Journal Article

Computing balanced solutions for large international kidney exchange schemes

  • Márton Benedek
  • Péter Biró
  • Xin Ye

Abstract To overcome incompatibility issues, kidney patients may swap their donors. In international kidney exchange programmes (IKEPs), countries merge their national patient–donor pools. We consider a recently introduced credit system. In each round, countries are given an initial “fair” allocation of the total number of kidney transplants. This allocation is adjusted by a credit function yielding a target allocation. The goal is to find a solution that approaches the target allocation as closely as possible, to ensure long-term stability of the international pool. As solutions, we use maximum matchings that lexicographically minimize the country deviations from the target allocation. We perform, for the first time, a computational study for a large number of countries. For the initial allocations we use two easy-to-compute solution concepts, the benefit value and the contribution value, and four classical but hard-to-compute concepts, the Shapley value, nucleolus, Banzhaf value and tau value. By using state-of-the-art software we show that the latter four concepts are now within reach for IKEPs of up to fifteen countries. Our experiments show that using lexicographically minimal maximum matchings instead of ones that only minimize the largest deviation from the target allocation (as previously done) may make an IKEP up to 54% more balanced.

Details DOI

AAMAS Conference 2024 Conference Paper

Computing Balanced Solutions for Large International Kidney Exchange Schemes when Cycle Length is Unbounded

  • Márton Benedek
  • Péter Biró
  • Gergely Csáji
  • Matthew Johnson
  • Daniël Paulusma
  • Xin Ye

In kidney exchange programmes (KEP) patients may swap their incompatible donors leading to cycles of kidney transplants. Countries try to merge their national patient-donor pools leading to international KEPs (IKEPs). Long-term stability of an IKEP can be achieved through a credit-based system. The goal is to find, in each round, an optimal solution that closely approximates this target allocation. We provide both theoretical and experimental results for the case where the cycle length is unbounded.

PDF

AAMAS Conference 2022 Conference Paper

Computing Balanced Solutions for Large International Kidney Exchange Schemes

  • Márton Benedek
  • Péter Biró
  • Walter Kern
  • Daniël Paulusma

To overcome incompatibility issues, kidney patients may swap their donors. In international kidney exchange programmes (IKEPs), countries merge their national patient-donor pools. We consider a recent credit system where in each round, countries are given an initial kidney transplant allocation which is adjusted by a credit function yielding a target allocation. The goal is to find a solution in the patient-donor compatibility graph that approaches the target allocation as closely as possible, to ensure long-term stability of the international pool. As solutions, we use maximum matchings that lexicographically minimize the country deviations from the target allocation. We first give a polynomial-time algorithm for computing such matchings. We then perform, for the first time, a computational study for a large number of countries. For the initial allocations we use, besides two easy-to-compute solution concepts, two classical concepts: the Shapley value and the nucleolus. These are hard to compute, but by using state-of-the-art software we show that they are now within reach for IKEPs of up to fifteen countries. Our experiments show that using lexicographically minimal maximum matchings instead of ones that only minimize the largest deviation from the target allocation (as previously done) may make an IKEP up to 52% more balanced.

PDF

AAAI Conference 2022 Conference Paper

Matching Market Design with Constraints

  • Haris Aziz
  • Péter Biró
  • Makoto Yokoo

Two-sided matching is an important research area that has had a major impact on the design of real-world matching markets. One consistent feature in many of the real-world applications is that they impose new feasibility constraints that lead to research challenges. We survey developments in the field of two-sided matching with various constraints, including those based on regions, diversity, multi-dimensional capacities, and matroids.

PDF Details

AAMAS Conference 2019 Conference Paper

Generalized Matching Games for International Kidney Exchange

  • Péter Biró
  • Walter Kern
  • Dömötör Pálvölgyi
  • Daniel Paulusma

We introduce generalized matching games defined on a graph G = (V, E) with an edge weighting w and a partition V = V1 ∪ · · · ∪ Vn of V. The player set is N = {1, .. ., n}, and player p ∈ N owns the vertices in Vp. The value v(S) of coalition S ⊆ N is the maximum weight of a matching in the subgraph of G induced by the vertices owned by players in S. If |Vp | = 1 for every player p we obtain the classical matching game. We prove that checking core nonemptiness is polynomial-time solvable if |Vp | ≤ 2 for each p and co-NP-hard if |Vp | ≤ 3 for each p. We do so via pinpointing a relationship with b-matching games and also settle the complexity classification on testing core non-emptiness for b-matching games. We propose generalized matching games as a suitable model for international kidney exchange programs, where the vertices in V correspond to patient-donor pairs and each Vp represents one country. For this setting we prove a number of complexity results.

PDF

AAMAS Conference 2016 Conference Paper

Optimal Reallocation Under Additive and Ordinal Preferences

  • Haris Aziz
  • Péter Biró
  • Jérôme Lang
  • Julien Lesca
  • Jérôme Monnot

Reallocating resources to get mutually beneficial outcomes is a fundamental problem in various multi-agent settings. In the first part of the paper we focus on the setting in which agents express additive cardinal utilities over objects. We present computational hardness results as well as polynomial-time algorithms for testing Pareto optimality under different restrictions such as two utility values or lexicographic utilities. In the second part of the paper we assume that agents express only their (ordinal) preferences over single objects, and that their preferences are additively separable. In this setting, we present characterizations and polynomial-time algorithms for possible and necessary Pareto optimality. General Terms Economics, Theory and Algorithms

PDF