Skip to main content
SpringerLink
Log in

Solutions of Partition Function-Based TU Games for Cooperative Communication Networking

  • Conference paper
  • First Online:
Advances in Information and Communication (FICC 2019)

Part of the book series: Lecture Notes in Networks and Systems ((LNNS,volume 70))

Included in the following conference series:

Abstract

In networked communications nodes choose among available actions and benefit from exchanging information through edges, while continuous technological progress fosters system functionings that increasingly often rely on cooperation. Growing attention is being placed on coalition formation, where each node chooses what coalition to join, while the surplus generated by cooperation is an amount of TU (transferable utility) quantified by a real-valued function defined on partitions -or even embedded coalitions- of nodes. A TU-sharing rule is thus essential, as how players are rewarded determines their behavior. This work offers a new option for distributing partition function-based surpluses, dealing with cooperative game theory in terms of both global games and games in partition function form, namely lattice functions, while the sharing rule is a point-valued solution or value. The novelty is grounded on the combinatorial definition of such solutions as lattice functions whose Möbius inversion lives only on atoms, i.e. on the first level of the lattice. While rephrasing the traditional solution concept for standard coalitional games, this leads to distribute the surplus generated by partitions across the edges of the network, as the atoms among partitions are unordered pairs of players. These shares of edges are further divided between nodes, but the corresponding Shapley value is very different from the traditional one and leads to two alternative forms, obtained by focusing either on marginal contributions along maximal chains, or else on the uniform division of Harsanyi dividends. The core is also addressed, and supermodularity is no longer sufficient for its non-emptiness.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 169.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 219.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Notes

  1. 1.

    See [5] on the Banzhaf value of C games.

  2. 2.

    See [27] on how to deal with a bottom partition whose worth is \(\ne 0\).

  3. 3.

    \(v(\emptyset )=\mu ^v(\emptyset )\) being chosen arbitrarily, any \(\mathbf {AS}(f)\ne \emptyset \) is not bounded.

References

  1. Han, Z., Niyato, D., Saad, W., Başar, T., Hjørungnes, A.: Game Theory for Wireless and Communication Networks. Cambridge University Press, Cambridge (2012)

    MATH  Google Scholar 

  2. Saad, W., Han, Z., Debbah, M., Hjørungnes, A., Başar, T.: Coalitional game theory for communication networks: a tutorial, pp. 1–26. arXiv:0905.4057v1 (2009)

    Article  Google Scholar 

  3. Slikker, M.: Coalition formation and potential games. Games Econ. Behav. 37, 436–448 (2001)

    Article  MathSciNet  Google Scholar 

  4. Aigner, M.: Combinatorial Theory. Springer, Berlin (1997)

    Book  Google Scholar 

  5. Roth, A. (ed.): The Shapley Value-Essays in Honor of Lloyd S. Shapley. Cambridge University Press, Cambridge (1988)

    MATH  Google Scholar 

  6. Akyildiz, I., Lo, B., Balakrishnan, R.: Cooperative spectrum sensing in cognitive radio networks: a survey. Phys. Commun. 4, 40–62 (2011)

    Article  Google Scholar 

  7. Laneman, J., Wornell, G.: Distributed space-time-coded protocols for exploiting cooperative diversity in wireless network. IEEE Trans. Inf. Theory 49, 2415–2425 (2003)

    Article  MathSciNet  Google Scholar 

  8. Letaief, K., Zhang, W.: Cooperative spectrum sensing. In: Hossain, E., Bhargava, V. (eds.) Cognitive Wireless Communication Networks, pp. 115–138. Springer, Berlin (2007)

    Chapter  Google Scholar 

  9. Zhou, Z., Zhou, S., Cui, S., Cui, J.H.: Energy-effiecient cooperative communication in clustered wireless sensor networks. IEEE Trans. Veh. Technol. 57, 3618–3628 (2008)

    Article  Google Scholar 

  10. Al-Karaki, J.L., Kamal, A.E.: Routing techniques in wireless sensor networks: a survey. IEEE Wirel. Commun. 11, 6–28 (2004)

    Article  Google Scholar 

  11. Cai, J., Pooch, U.: Allocate fair payoff for cooperation in wireless ad hoc networks using Shapley value. In: Proceedings of IPDPS 04, pp. 219–226 (2004)

    Google Scholar 

  12. Cavalcanti, D., Agrawal, D., Cordero, C., Xie, B., Kumar, A.: Issues in integrating cellular networks, WLANs and MANETs: a futuristic heterogeneous wireless network. IEEE Wirel. Commun. 12, 30–41 (2005)

    Article  Google Scholar 

  13. Cho, J.H., Swami, A., Chen, I.R.: A survey on trust management for mobile ad hoc networks. IEEE Commun. Surv. Tutorials 13(4), 562–583 (2011)

    Article  Google Scholar 

  14. Chow, C.Y., Leong, H.V., Chan, A.T.S.: GroCoca: group-based peer-to-peer cooperative caching in mobile environment. IEEE J. SAC 25(1), 179–191 (2007)

    Google Scholar 

  15. Huang, X., Zhai, H., Fang, Y.: Robust cooperative routing protocol in mobile wireless sensor networks. IEEE Trans. Wirel. Commun. 7(12), 5278–5285 (2008)

    Article  Google Scholar 

  16. Ye, M., Li, C., Chen, G., Wu, J.: An energy efficient clustering scheme in wireless sensor networks. Ad Hoc Sens. Wirel. Netw. 3, 99–119 (2007)

    Google Scholar 

  17. Nandan, A., Das, S., Pau, G., Gerla, M., Sanadidi, M.: Co-operative downloading in vehicular ad-hoc wireless networks. In Proceedings of WONS 05, pp. 32–41 (2005)

    Google Scholar 

  18. Vardhe, K., Reynolds, D., Woerner, B.: Joint power allocation and relay selection for multiuser cooperative communication. IEEE Trans. Wirel. Commun. 9(4), 1255–1260 (2010)

    Article  Google Scholar 

  19. Wang, B., Han, Z., Liu, K.: Distributed relay selection and power control for multiuser cooperative communication networks using buyer/seller game. In: IEEE INFOCOM 2007 Proceedings, pp. 544–552 (2007)

    Google Scholar 

  20. Wang, T., Giannakis, G.B.: Complex field network coding for multiuser cooperative communications. IEEE J. SAC 26(3), 561–571 (2008)

    Google Scholar 

  21. Younis, O., Fahmy, S.: HEED a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks. IEEE Trans. Mob. Comput. 3(4), 366–379 (2004)

    Article  Google Scholar 

  22. Younis, O., Krunz, M., Ramasubramanian, S.: Node clustering in wireless sensor networks: recent developments and deployment challenges. IEEE Netw. 20, 20–25 (2006)

    Article  Google Scholar 

  23. Fitzek, F.H.P., Katz, M.D. (eds.): Cooperation in Wireless Networks: Principles and Applications-Real Egoistic Behavior is to Cooperate!. Springer, Berlin (2006)

    Google Scholar 

  24. Saad, W., Han, Z., Başar, T., Debbah, M., Hjørungnes, A.: Coalition formation games for collaborative spectrum sensing. IEEE Trans. Veh. Technol. 60, 276–297 (2011)

    Article  Google Scholar 

  25. Saad, W., Han, Z., Zheng, R., Hjørungnes, A., Başar, T., Poor, H.V.: Coalitional games in partition form for joint spectrum sensing and access in cognitive radio networks. IEEE J. Sel. Top. Sig. Proc. 6, 195–209 (2012)

    Article  Google Scholar 

  26. Borm, P., Owen, G., Tijs, S.: On the position value for communication situations. SIAM J. Discrete Math. 5, 305–320 (1992)

    Article  MathSciNet  Google Scholar 

  27. Gilboa, I., Lehrer, E.: Global games. Int. J. Game Theory 20, 120–147 (1990)

    MathSciNet  MATH  Google Scholar 

  28. Rossi, G.: Worth-sharing through Möbius inversion. Homo Economicus 24, 411–433 (2007)

    Google Scholar 

  29. Thrall, R.M., Lucas, W.F.: \(n\)-person games in partition function form. Naval Res. Logistic Q. 10, 281–298 (1963)

    Article  MathSciNet  Google Scholar 

  30. Grabisch, M., Funaki, Y.: A coalition formation value for games in partition function form. Eur. J. Oper. Res. 221(1), 175–185 (2012)

    Article  MathSciNet  Google Scholar 

  31. Myerson, R.: Values of games in partition function form. Int. J. Game Theory 6, 23–31 (1977)

    Article  MathSciNet  Google Scholar 

  32. Rossi, G.: The geometric lattice of embedded subsets, pp. 1–17. arXiv: 1612.05814 (2017)

  33. Whitney, H.: On the abstract properties of linear dependence. Am. J. Math. 57, 509–533 (1935)

    Article  MathSciNet  Google Scholar 

  34. Rosas, M.H., Sagan, B.E.: Symmetric functions in noncommuting variables. Trans. AMS 358, 215–232 (2006)

    Article  MathSciNet  Google Scholar 

  35. Conitzer, V., Sandholm, T.: Complexity of constructing solutions in the core based on synergies among coalitions. Artif. Intell. 170, 607–619 (2006)

    Article  MathSciNet  Google Scholar 

  36. Shapley, L.S.: Cores of convex games. Int. J. Game Theory 1(1), 11–26 (1971)

    Article  MathSciNet  Google Scholar 

  37. Fortunato, S.: Community detection in graphs. Phys. Rep. 486(3–5), 75–174 (2010)

    Article  MathSciNet  Google Scholar 

  38. Gilboa, I., Lehrer, E.: The value of information—an axiomatic approach. J. Math. Econ. 20(5), 443–459 (1991)

    Article  MathSciNet  Google Scholar 

  39. Rota, G.C.: On the foundations of combinatorial theory I: theory of Möbius functions. Z. Wahrscheinlichkeitsrechnung Verw. Geb. 2, 340–368 (1964)

    Google Scholar 

  40. Weber, R.J.: Probabilistic values for games. In: A.E. Roth (ed.) The Shapley Value—Essays in Honor of Lloyd S. Shapley, pp. 101–119. Cambridge University Press, Cambridge (1988)

    Google Scholar 

  41. Grabisch, M.: The lattice of embedded subsets. Discrete Appl. Math. 158, 479–488 (2010)

    Article  MathSciNet  Google Scholar 

  42. Shapley, L.S.: A value for \(n\)-person games. In: Kuhn, H., Tucker, A.W. (eds.) Contributions to the Theory of Games, pp. 307–317. Princeton University Press, Princeton (1953)

    Google Scholar 

  43. Stanley, R.: Enumerative Combinatorics, 2nd edn. Cambridge University Press, Cambridge (2012)

    MATH  Google Scholar 

  44. Knuth, D.E.: Generating all combinations and partitions. The Art of Computer Programming, vol. 4, no. 3, pp. 1–150. Addison-Wesley (2005)

    Google Scholar 

  45. Kung, J.P.S., Rota, G.C., Yan, C.H. (eds.): Combinatorics: The Rota Way. Cambridge University Press, Cambridge (2009)

    MATH  Google Scholar 

  46. Rahwan, T., Jenning, N.: An algorithm for distributing coalitional value calculations among cooperating agents. Artif. Intell. 171, 535–567 (2007)

    Article  MathSciNet  Google Scholar 

  47. Korte, B., Vygen, J.: Combinatorial Optimization-Theory and Algorithms. Springer, Berlin (2002)

    MATH  Google Scholar 

  48. Myerson, R.: Graphs and cooperation in games. Math. Oper. Res. 2, 225–229 (1977)

    Article  MathSciNet  Google Scholar 

  49. Owen, G.: Values of graph-restricted games. SIAM J. ADM 7(2), 210–220 (1986)

    MathSciNet  MATH  Google Scholar 

  50. Diestel, R.: Graph Theory. Springer, Berlin (2010)

    Book  Google Scholar 

  51. Azrieli, Y., Lehrer, E.: Concavification and convex games. Working Paper, Tel Aviv University, pp. 0–18 (2005)

    Google Scholar 

  52. Holzman, R., Lehrer, E., Linial, N.: Some bounds for the Banzhaf index and other semivalues. Math. Oper. Res. 13, 358–363 (1988)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering DISI, University of Bologna, 40126, Bologna, Italy

    Giovanni Rossi

Authors
  1. Giovanni Rossi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Giovanni Rossi .

Editor information

Editors and Affiliations

  1. Faculty of Science and Engineering, Saga University, Saga, Japan

    Kohei Arai

  2. The Science and Information (SAI) Organization, Bradford, UK

    Rahul Bhatia

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Rossi, G. (2020). Solutions of Partition Function-Based TU Games for Cooperative Communication Networking. In: Arai, K., Bhatia, R. (eds) Advances in Information and Communication. FICC 2019. Lecture Notes in Networks and Systems, vol 70. Springer, Cham. https://doi.org/10.1007/978-3-030-12385-7_47

Download citation

Publish with us

Policies and ethics

Search

Navigation