부산대학교 도서관

Whether a population of decision-making individuals will reach a state of satisfactory decisions has been a fundamental problem in studying collective behaviors. By means of potential functions, researchers have established equilibrium convergence under different update rules, including best-response and imitation, by imposing certain conditions on the agents’ utility functions. Then, using the proposed potential functions, they were able to tackle the challenging problem of controlling these populations towards a desired equilibrium. Despite the successful attempts, finding a potential function is often daunting and in many cases, near impossible. We introduce a class of decision-making populations, called coordinating populations, where individuals tend to choose an option if some others have switched to that option. We prove that every coordinating population is guaranteed to almost surely equilibrate. Apparently, some general binary network games governed by best-response and imitation, that were proven to equilibrate using Lyapunov functions, are coordinating. Moreover, for the first time, we show that any mixed population of best-responders and imitators with coordination payoff matrices are coordinating and hence equilibrate. As a second contribution, we provide a control algorithm that leads coordinating populations to a desired equilibrium. The algorithm performs near optimal and as well as specialized algorithms proposed for best-response; however, it does not require a potential function. So for general population dynamics where no potential function is yet found, this control algorithm may be readily applied to obtain promising results.