hu / en

Megjelent Cseh Ágnes és szerzőtársa publikációja a Games and Economic Behavior folyóiratban

games_beh_head

Popular matchings with weighted voters

Klaus Heeger, Ágnes Cseh

Abstract

We consider a natural generalization of the well-known POPULAR MATCHING problem where every vertex has a weight. We call a matching 𝑀 more popular than matching 𝑀′ if the weight of vertices preferring 𝑀 to 𝑀′ is larger than the weight of vertices preferring 𝑀′ to 𝑀. For this case, we show that it is NP-hard to find a popular matching. Our main result is a polynomial-time algorithm that delivers a popular matching or a proof for its non-existence in instances where all vertices on one side have weight 𝑐 for some 𝑐 > 3 and all vertices on the other side have weight 1.

Keywords: Popular matching, Stable matching, Complexity, Algorithm

2024

Júl

17

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

17

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 >