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

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

TCS Journal 2022 Journal Article

Stable matching with uncertain pairwise preferences

Haris Aziz
Péter Biró
Tamás Fleiner
Serge Gaspers
Ronald de Haan
Nicholas Mattei
Baharak Rastegari

We study a two-sided matching problem under preferences, where the agents have independent pairwise comparisons on their possible partners and these preferences may be uncertain. Preferences may be intransitive and agents may even have cycles in their preferences; e. g. an agent a may prefer b to c, c to d, and d to b, all with probability one. If an instance has such a cycle, then there may not exist any matching that is stable with positive probability. We focus on the computational problems of checking the existence of possibly and certainly stable matchings, i. e. , matchings whose probability of being stable is positive or one, respectively. We show that finding possibly stable matchings is NP-hard, even if only one side can have cyclic preferences. On the other hand we show that the problem of finding a certainly stable matching is polynomial-time solvable if only one side can have cyclic preferences and the other side has transitive preferences, but that this problem becomes NP-hard when both sides can have cyclic preferences.

Details DOI

TCS Journal 2019 Journal Article

Efficient reallocation under additive and responsive 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. While finding an arbitrary Pareto optimal allocation is generally easy, checking whether a particular allocation is Pareto optimal can be much more difficult. This problem is equivalent to checking that the allocated objects cannot be reallocated in such a way that at least one agent prefers her new allocation to her old one, and no agent prefers her old allocation to her new one. We consider the problem for two related types of preference relations over sets of objects. 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 individual objects, and that their underlying preferences are additively separable. In this setting, we present characterizations and polynomial-time algorithms for possible and necessary Pareto optimality.

Details DOI

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

AIJ Journal 2019 Journal Article

Pareto optimal allocation under uncertain preferences: uncertainty models, algorithms, and complexity

Haris Aziz
Péter Biró
Ronald de Haan
Baharak Rastegari

The assignment problem is one of the most well-studied settings in multi-agent resource allocation. Agents express preferences over indivisible items and then the items are allocated based on these preferences. Pareto optimality is regarded as a desirable property for the chosen allocation, requiring that no other allocation exists in which no agent is worse off and at least one agent is better of. We consider the assignment problem with the additional feature that agents' preferences involve uncertainty. The setting with uncertainty leads to a number of interesting questions including the following ones. How to compute an assignment with the highest probability of being Pareto optimal? What is the complexity of computing the probability that a given assignment is Pareto optimal? Does there exist an assignment that is Pareto optimal with probability one? We consider these problems under five natural uncertainty models. For all of the models, we present a number of algorithmic and complexity results highlighting the differences and similarities in the complexity of the models. We also present some general characterization and algorithmic results that apply to large classes of uncertainty models.

Details DOI

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

TCS Journal 2014 Journal Article

Solutions for the stable roommates problem with payments

Péter Biró
Matthijs Bomhoff
Petr A. Golovach
Walter Kern
Daniël Paulusma

The stable roommates problem with payments has as input a graph G = ( V, E ) with an edge weighting w: E → R ≥ 0 and the problem is to find a stable solution. A solution is a matching M with a vector p ∈ R ≥ 0 V that satisfies p u + p v = w ( u v ) for all u v ∈ M and p u = 0 for all u unmatched in M. A solution is stable if it prevents blocking pairs, i. e. , pairs of adjacent vertices u and v with p u + p v < w ( u v ), or equivalently, if the total blocking value ∑ u v ∈ E max { 0, w ( u v ) − ( p u + p v ) } = 0. By pinpointing a relationship to the accessibility of the coalition structure core of matching games, we give a constructive proof for showing that every yes-instance of the stable roommates problem with payments allows a path of linear length that starts in an arbitrary unstable solution and that ends in a stable solution. This generalizes a result of Chen, Fujishige and Yang (2011) [4] for bipartite instances to general instances. We also show that the problems Blocking Pairs and Blocking Value, which are to find a solution with a minimum number of blocking pairs or a minimum total blocking value, respectively, are NP-hard. Finally, we prove that the variant of the first problem, in which the number of blocking pairs must be minimized with respect to some fixed matching, is NP-hard, whereas this variant of the second problem is polynomial-time solvable.

Details DOI

TCS Journal 2012 Journal Article

“Almost stable” matchings in the Roommates problem with bounded preference lists

Péter Biró
David F. Manlove
Eric J. McDermid

An instance of the classical Stable Roommates problem need not admit a stable matching. Previous work has considered the problem of finding a matching that is “as stable as possible”, i. e. , admits the minimum number of blocking pairs. It is known that this problem is NP-hard and not approximable within n 1 2 − ε, for any ε > 0, unless P = NP, where n is the number of agents in a given instance. In this paper, we extend the study to the Stable Roommates problem with Incomplete lists. In particular, we consider the case that the lengths of the lists are bounded by some integer d. We show that, even if d = 3, there is some c > 1 such that the problem of finding a matching with the minimum number of blocking pairs is not approximable within c unless P = NP. On the other hand, we show that the problem is solvable in polynomial time for d ≤ 2, and we give a ( 2 d − 3 ) -approximation algorithm for fixed d ≥ 3. If the given lists satisfy an additional condition (namely the absence of a so-called elitist odd party–a structure that is unlikely to exist in general), the performance guarantee improves to 2 d − 4.

Details DOI

TCS Journal 2010 Journal Article

Size versus stability in the marriage problem

Péter Biró
David F. Manlove
Shubham Mittal

Given an instance I of the classical Stable Marriage problem with Incomplete preference lists (smi), a maximum cardinality matching can be larger than a stable matching. In many large-scale applications of smi, we seek to match as many agents as possible. This motivates the problem of finding a maximum cardinality matching in I that admits the smallest number of blocking pairs (so is “as stable as possible”). We show that this problem is NP-hard and not approximable within n 1 − ε, for any ε > 0, unless P=NP, where n is the number of men in I. Further, even if all preference lists are of length at most 3, we show that the problem remains NP-hard and not approximable within δ, for some δ > 1. By contrast, we give a polynomial-time algorithm for the case where the preference lists of one sex are of length at most 2. We also extend these results to the cases where (i) preference lists may include ties, and (ii) we seek to minimize the number of agents involved in a blocking pair.

Details DOI

TCS Journal 2010 Journal Article

The College Admissions problem with lower and common quotas

Péter Biró
Tamás Fleiner
Robert W. Irving
David F. Manlove

We study two generalised stable matching problems motivated by the current matching scheme used in the higher education sector in Hungary. The first problem is an extension of the College Admissions problem in which the colleges have lower quotas as well as the normal upper quotas. Here, we show that a stable matching may not exist and we prove that the problem of determining whether one does is NP-complete in general. The second problem is a different extension in which, as usual, individual colleges have upper quotas, but, in addition, certain bounded subsets of colleges have common quotas smaller than the sum of their individual quotas. Again, we show that a stable matching may not exist and the related decision problem is NP-complete. On the other hand, we prove that, when the bounded sets form a nested set system, a stable matching can be found by generalising, in non-trivial ways, both the applicant-oriented and college-oriented versions of the classical Gale–Shapley algorithm. Finally, we present an alternative view of this nested case using the concept of choice functions, and with the aid of a matroid model we establish some interesting structural results for this case.

Details DOI