Dynamic Cost-Sharing Game with Spanning Arborescence

Authors

  • Peichen Ye Saint Petersburg State University
  • Yin Li Saint Petersburg State University; Harbin Institute of Technology
  • Ovanes Petrosian Saint Petersburg State University

DOI:

https://doi.org/10.21638/11701/spbu31.2022.21

Abstract

This paper presents the dynamic Shapley value for cost-sharing game with spanning arborescence. The cooperative behaviour of players is determined, and a two-stage directed network game is considered. At each stage, a cost matrix associated with the directed network is defined by players adopting strategies, and a minimum cost spanning arborescence on the directed network is determined. After the first stage, a particular player will leave the game with a certain probability, which depends on all players' behaviours in the first stage. The characteristic function is defined. Using the Imputation Distribution Procedure(IDP), the dynamic Shapley value in the game is constructed.

Keywords:

directed network, cost sharing game, minimum cost spanning arborescences, dynamic Shapley value

Downloads

Download data is not yet available.
 

References

Bergantinos, G. and Vidal-Puga, J. J. (2007). A fair rule in minimum cost spanning tree problems. Journal of Economic Theory, 137(1), 326–352

Bird, C. G. (1976). On cost allocation for a spanning tree: A game theoretic approach. Networks, 6, 335–350

Claus, A. and Kleitman, D. J. (1973). Cost allocation for a spanning tree. Networks, 3, 289–304

Dutta, B. and Kar, A. (2004). Cost monotonicity, consistency and minimum cost spanning tree games. Games Econom Behav, 48, 223–248

Dutta, B. and Mishra, D.(2012). Minimum cost arborescences. Games Econom Behav, 74, 120–143

Min, Ch. Peichen, Y. and Yin, L (2022). Dynamic "optimistic" characteristic function in the game with spanningtree. 2022 International Conference Stability and Oscillations of Nonlinear Control Systems (Pyatnitskiy's Conference). IEEE, 2022: 5427–5432

Petrosyan, L. A. and Danilov, N. N. (1979). Stability of solutions in non-zero sum differential games with transferable payoffs. Viestnik of Leningrad Universtiy, 1, 52–59

Petrosyan, L. A., Sedakov, A. A. and Bochkarev, A. O. (2013). Two-stage network games. Matematicheskaya teoriya igr i ee prilozheniya, 5(4), 84–104

Yin, Li. (2016). The dynamic Shapley Value in the game with spanning tree. 2016 International Conference Stability and Oscillations of Nonlinear Control Systems (Pyatnitskiy's Conference). IEEE, 2016, 1–4

Downloads

Published

2023-01-27

How to Cite

Ye, P., Li, Y., & Petrosian, O. (2023). Dynamic Cost-Sharing Game with Spanning Arborescence. Contributions to Game Theory and Management, 15, 287–302. https://doi.org/10.21638/11701/spbu31.2022.21

Issue

Vol. 15 (2022)

Section

Articles

License

Articles of "Contributions to Game Theory and Management" are open access distributed under the terms of the License Agreement with Saint Petersburg State University, which permits to the authors unrestricted distribution and self-archiving free of charge.