Автор(ы): Губко М. В. (ИПУ РАН, Лаборатория 57)Автор(ов): 1 Параметры публикацииТип публикации: ДокладНазвание: Models of Network Formation Game ControlНаименование конференции: 4th International Conference on Game Theory and Management (GTM-2010, St.Petersburg)Наименование источника: Proceedings of the 4th International Conference on Game Theory and Management (GTM-2010, St.Petersburg)Город: Санкт-ПетербургИздательство: СПбГУГод издания: 2010Страницы: 64-67 АннотацияIn a basic model of the organizational systems control theory a system is considered where a sole principal controls n >= 1 agents. The principal chooses a control u to maximize his or her utility function. Each agent has a utility function that can depend on his or her action, actions of others agents, and the principal’s control. The vector (y1, …, yn) of agents’ actions along with the control u (and, in general, some uncertain external parameters) leads to the result x(y1, …, yn, u, .). Thus, given the control u agents play a game with the outcome x. If the principal uses some game-theoretic solution concept P(u) from X to predict the outcome of the game, then the control problem is to find the optimal control. The set U may allow for loop-back controls u(x) if they make sense in the setting in hand.If agents are involved in some network interaction (choose a path through a transportation network, participate in a process of intercommunication in a social network, or share information with colleagues in models of information security, etc), the output x describes the resulting parameters of this network (equilibrium traffic densities in networking games, sustained opinions in the models of intercommunication …). Specific solution concepts (like Wardrop equilibrium or information equilibrium) allow predicting the rational actions of the agents. In these models the principal influences agents’ behavior by directing traffic in transportation network, injecting the judgments into a social network, or choosing the information security policy. In a wide range of problems the agents form the network structure itself. For example, in the problem of road building investment agents must agree on the structure of a road network and then share the construction costs among parties. Agents choose the circle of acquaintance (and then communicate with the neighbors) in models of social networks, or support communication channels in models of local network security. The role of the principal is to force the formation of certain bonds between the agents by a tax policy or public-private partnership agreements in the problem of road investment, by promoting some types of bonds in a social network, by limiting access in the problem of information security, etc. Often the framework of network formation employs some model of network interaction (game-theoretic or simulation, and sometimes rather complicated) to calculate the agents’ payoffs, but to stress the structure formation aspects it is supposed below that agents’ payoffs fi(y1, …, yn, u) depend solely on their network formation efforts yi and on the control variable u. The state x of the system is a network – a directed or undirected graph built over the set of agents (some extensions involve vector weights attached to the edges of the graph), and the problem of the principal is to find the control which maximizes his or her utility function.The tradition treats a network formation game (NFG) as a generalization of cooperative game in characteristic function form, although NFGs admit purely strategic analysis. The mechanism of network formation (i.e. the relation between the agents’ efforts y1, …, yn and the resulting network) can be very complicated. Typical mechanisms involve mutual agreements on bond formation (for example, both agents must agree to become friends), and unilateral formation of directed arcs (normally no approval is required from the recipients of local corporate e mails). In the former the actions set of every agent includes the binary vector of offers and the vector of acceptances of other agents’ offers, while in the latter a binary vector of intentions is enough.Control theory imposes strong requirements on the solution concepts employed. Existence of solution guarantees the predictability of agents’ behavior, while the uniqueness (or narrowness) of solution concept assures the controllability of the system. Traditional solution concepts, like Nash equilibrium, when applied to NFGs, fail to satisfy these requirements (for example, the empty network is a Nash equilibrium of mutual agreement game irrespective of agents’ payoffs). Thus, several special strategic solution concepts were developed in the literature for NFGs: pairwise stability, strong Nash stability, hybrid stability, and k-stability. All these solution concepts have benefits and implications. In the report I discuss and compare these concepts aligning them into the line from the weakest to the strongest. This arrangement allows the principal to choose the concept that suits best agents capabilities in a specific setting. Rather common control problem is the problem of maximizing the total value of a network – the sum of agents’ payoffs. Although in this case the goals of the principal do not contradict the goals of the controlled system, the problem of stabilizing the effective network is far from trivial, and the principal has to reallocate the payoff among the agents in a very sophisticated way to resolve the conflict of efficiency and stability.In the report a more general setting is considered of incentive problem where the principal can immediately set bonuses to the agents for the formation of specific networks. This problem is solved in complete information framework for several solution concepts including pairwise stability, strong stability, and hybrid stability. The problem is reduced to the set of discrete optimization problems, their complexity is estimated, and in several cases the closed form solutions are obtained. Some applications of the theoretic results are discussed. Библиографическая ссылка: Губко М.В. Models of Network Formation Game Control / Proceedings of the 4th International Conference on Game Theory and Management (GTM-2010, St.Petersburg). СПб.: СПбГУ, 2010. С. 64-67.