hu / en

Complexity of stability in trading networks – by Tamás Fleiner, Zsuzsanna Jankó, Ildikó Schlotter & Alexander Teytelboym

in International Journal of Game Theory

 

 

Complexity of stability in trading networks

Tamás Fleiner, Zsuzsanna Jankó,
Ildikó Schlotter & Alexander Teytelboym 

 

    • Original Paper
    • Open Access
    • Published:
    • International Journal of Game Theory – volume 52, pages 629–648 (202
 
Abstract

Efficient computability is an important property of solution concepts. We consider the computational complexity of finding and verifying various solution concepts in trading networks—multi-sided matching markets with bilateral contracts and without transferable utility—under the assumption of full substitutability of agents’ preferences. It is known that outcomes that satisfy trail stability always exist and can be found in linear time. However, we show that the existence of stable outcomes—immune to deviations by arbitrary sets of agents—is an NP-hard problem in trading networks. We also show that even verifying whether a given outcome is stable is NP-hard in trading networks.

Download PDF

 

 

2024

Jul

25

M

T

W

T

F

S

S

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

Next month >