Incentive-based search for equilibria in boolean games

Search for equilibria in games is a hard problem and many games do not have a pure Nash equilibrium (PNE). Incentive mechanisms have been shown to secure a PNE in certain families of games. The present study utilizes the similarity between Asymmetric Distributed Constraints Optimization Problems (ADCOPs) and games, to construct search algorithms for finding outcomes and incentives that secure a pure Nash equilibrium in Boolean games. The set of values returned by the search algorithm for a chosen incentive mechanism is termed an incentive plan. The two incentive mechanisms that are used by the present study are taxation and side-payments. Both are described and their performance on PNE search in Boolean games is evaluated. An incentive plan for the taxation mechanism consists of the values of imposed tax, while an incentive plan for the side payments mechanism consists of values for a set of transfer functions. The distributed search algorithms address two different requirements. One is to find an incentive plan that enables to secure a PNE. The other requirement is that the algorithms return a PNE that satisfies some global objective, such as a PNE that maximizes social welfare. The Boolean game is first transformed into an ADCOP. Then, a designated distributed search algorithm is applied to find the desired outcome. Two distributed search algorithms are described, incorporating k-ary constraints as well as soft constraints that relate to global objectives. The new and innovative algorithm - Concurrent Asymmetric Branch and Bound - is found experimentally to be much faster than the former algorithm. An extensive experimental evaluation on several types of social-network-based Boolean games is presented. The degree of intervention in the game is found to be small for both incentive mechanisms. In other words, the overall tax or the total amount of side-payments is a small fraction of the general utility. The density of the networks has a substantial effect on the solution quality as well as on the computational effort to find them.