### Working paper

## Formation of Coalition Structures As a Non-Cooperative Game

The collecton contains paper accepted for the Seventh International Conference Game theory and Management (June 26-28, 2013, St. Petersburg State University, St. Petersburg, Russia). The presented papers belong to the field of game theory and its application to mamagement.

The volume may be recommended for researchers and post-graduate students of management, economic and applied mathematics departments.

Sited and reviewed in: Math-Net.Ru and RSCI. Abstracted and indexed in: Mathematical Reviews, Zentralblatt MATH and VINITI.

The paper proposes a list of requirements for a game able to describe individually motivated social interactions: be non-cooperative, able to construct multiple coalitions in an equilibrium and incorporate intra and inter coalition externalities. For this purpose the paper presents a family of non-cooperative games for coalition structure construction with an equilibrium existence theorem for a game in the family. Few examples illustrate the approach. One of the results is that efficiency is not equivalent to cooperation as an allocation in one coalition. Further papers will demonstrate other applications of the approach.

We study existence of Nash equilibria (NE) in pure stationary strategies in n-person positional games with no moves of chance, with perfect information, and with the mean or total effective cost function.

We construct a NE-free three-person game with positive local costs, thus disproving the conjecture suggested in Boros and Gurvich (2003). Still, the following four problems remain open: Whether NE exist in all *two*-person games with total effective costs such that

(I) all local costs are strictly positive *or* (II) there are no dicycles of the total cost zero?

Whether NE exist in all n-person games with the terminal (transition-free) cost functions, provided all dicycles form a unique outcome c and

(III) assuming that c is worse than any terminal outcome *or* (IV) without this assumption?

For n=3 the case (I) (and hence (II)) is answered in the negative. This is the main result of the present paper. For n=2 the case (IV) (and hence (III)) was answered in the positive earlier.

We briefly survey the above and some other negative and positive results on Nash-solvability in pure stationary strategies for the games under consideration.

We suggest a new algorithm for two-person zero-sum undiscounted stochastic games focusing on stationary strategies. Given a positive real ϵϵ, let us call a stochastic game ϵϵ-ergodic, if its values from any two initial positions differ by at most ϵϵ. The proposed new algorithm outputs for every ϵ>0ϵ>0 in finite time either a pair of stationary strategies for the two players guaranteeing that the values from any initial positions are within an ϵϵ-range, or identifies two initial positions uu and vv and corresponding stationary strategies for the players proving that the game values starting from uu andvv are at least ϵ/24ϵ/24 apart. In particular, the above result shows that if a stochastic game is ϵϵ-ergodic, then there are stationary strategies for the players proving 24ϵ24ϵ-ergodicity. This result strengthens and provides a constructive version of an existential result by Vrieze (1980) claiming that if a stochastic game is 00-ergodic, then there are ϵϵ-optimal stationary strategies for every ϵ>0ϵ>0. The suggested algorithm extends the approach recently introduced for stochastic games with perfect information, and is based on the classical potential transformation technique that changes the range of local values at all positions without changing the normal form of the game.

This book is devoted to game theory and its applications to environmental problems, economics, and management. It collects contributions originating from the 12th International Conference on “Game Theory and Management” 2018 (GTM2018) held at Saint Petersburg State University, Russia, from 27 to 29 June 2018.