  A multi-agent system operates in an uncertain environment about which agents
have different and time varying beliefs that, as time progresses, converge to a
common belief. A global utility function that depends on the realized state of
the environment and actions of all the agents determines the system's optimal
behavior. We define the asymptotically optimal action profile as an equilibrium
of the potential game defined by considering the expected utility with respect
to the asymptotic belief. At finite time, however, agents have not entirely
congruous beliefs about the state of the environment and may select conflicting
actions. This paper proposes a variation of the fictitious play algorithm which
is proven to converge to equilibrium actions if the state beliefs converge to a
common distribution at a rate that is at least linear. In conventional
fictitious play, agents build beliefs on others' future behavior by computing
histograms of past actions and best respond to their expected payoffs
integrated with respect to these histograms. In the variations developed here
histograms are built using knowledge of actions taken by nearby nodes and best
responses are further integrated with respect to the local beliefs on the state
of the environment. We exemplify the use of the algorithm in coordination and
target covering games.
