2016/02/05 by Ceyhun Eksin, Alejandro Ribeiro, Eksin, Ceyhun +1
Decision Sciences · Economics, Econometrics and Finance · Social Sciences · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Economic theories and models #Experimental Behavioral Economics Studies #FOS: Computer and information sciences #FOS: Electrical engineering #Game Theory and Applications #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.1602.02066
openalex publication_date 2016/02/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.