hu / en

Megjelent Biró Péter és Csáji Gergely cikke a Games and Economic Behavior folyóiratban

1-s2.0-S0899825624000411-gr002_lrg

Strong core and Pareto-optimality in the multiple partners matching problem under lexicographic preference domains

Biró Péter & Csáji Gergely

Abstract

We study strong core and Pareto-optimal solutions for multiple partners matching problem under lexicographic preference domains from a computational point of view. The restriction to the two-sided case is called stable many-to-many matching problem and the general one-sided case is called stable fixtures problem. We provide an example to show that the strong core can be empty even for many-to-many problems, and that deciding the non-emptiness of the strong core is NP-hard. On the positive side, we give efficient algorithms for finding a near feasible strong core solution and for finding a fractional matching in the strong core of fractional matchings. In contrast with the NP-hardness result for the stable fixtures problem, we show that finding a maximum size matching that is Pareto-optimal can be done efficiently for many-to-many problems. Finally, we show that for reverse-lexicographic preferences the strong core is always non-empty in the many-to-many case.

2024

Júl

16

H

K

Sz

Cs

P

Sz

V

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

3

4

Következő hónap >
a

2024

Júl

16

H

K

Sz

Cs

P

Sz

V

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

3

4

Következő hónap >