Solutions of partition function-based TU games for cooperative communication networking
share
Fostered by continuous technological progress, the functioning of communication networks increasingly often relies on collaborative node behavior. Recently growing attention has been placed on coalition formation, which combines non-cooperative and cooperative games, as players strategically choose what coalition to join, while receiving a share of coalitional worth. In particular, collaboration may produce an amount of TU (transferable utility) quantified by a function taking real values on partitions -or even embedded coalitions- of nodes. The next step is to choose a criterion for sharing such a TU, as this determines how players are rewarded and thus is essential for analyzing their strategic behavior. This work introduces a new option for distributing partition function-based surpluses. In terms of cooperative game theory, the formal setting corresponds to both global games and games in partition function form, namely lattice functions, while the sharing criterion is a point-valued solution or value. The proposed 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 simply rephrasing the traditional solution concept for standard coalitional games, this definition leads to distribute the surplus generated by partitions across the edges of the network, as the atoms among partitions are unordered pairs of players. The corresponding Shapley value is different from the traditional one, and obtains 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.
READ FULL TEXT