Expected Price of Anarchy for the Dynamic Network Formation Game Model (Preprint)

概要

論文の詳細を見る
Recent studies revealed that some social and technological network formations can be represented by the network formation games played by selfish multiple agents. In general, the topologies formed by selfish multiple agents are worse than or equal to those formed by the centralized designer in the sense of social total welfare. Several works such as the price of anarchy are known as a measure for evaluating the inefficiency of solutions obtained by selfish multiple agents compared to the social optimal solution. In this paper, we introduce the expected price of anarchy which is proposed as a valid measure for evaluating the inefficiency of the dynamic network formation game whose solution space is divided into basins with multimodal sizes. Moreover, through some computer simulations we show that it can represent the average case behavior of inefficiency of dynamic network formation games which is missed by two previous measures.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.21(2013) No.1 (online)------------------------------
2012-11-15