Distributed optimization can be formulated as an n-player coordination game. One of the most common learning techniques in game theory is ﬁctitious play and its variations. However, ﬁctitious play is founded on an implicit assumption that opponents’ strategies are stationary. In this paper we present a new variation of ﬁctitious play in which players predict opponents’ strategy using a particle ﬁlter algorithm. This allows us to use a more realistic model of opponent strategy. We used pre-speciﬁed opponents’ strategies to examine if our algorithm can efﬁciently track the strategies. Furthermore, we have used these experiments to examine the impact of different values of our algorithm parameters on the results of strategy tracking. We then compared the results of the proposed algorithm with those of stochastic and geometric ﬁctitious play in three different strategic form games: a potential game and two climbing hill games, one with two players and the other with three players. We also tested our algorithm in two different distributed optimization scenarios, a vehicle-target assignment game and a disaster management problem. Our algorithm converges to the optimum faster than both the competitor algorithms in the strategic form games and the vehicle-target assignment game. Hence by placing a greater computational demand on the individual agents, less communication is required between the agents. In the disaster management scenario we compared the results of particle ﬁlter ﬁctitious play with the ones of Matlab’s centralized algorithm bintprog and the centralized pre-planning algorithm of (Gelenbe, E. andTimotheou, S. (2008) Random neural networks with synchronized interactions. Neural Comput., 20(9), 2308–2324). In this scenario our algorithm performed better than the pre-planning algorithm in two of the three performance measures we used.
|Number of pages||16|
|Journal||The Computer Journal|
|Publication status||Published - 2010|