Learning efficient satisfaction equilibria via trial and error

In this paper, the problem of quality-of-service (QoS) provisioning is formulated as a game in satisfaction form. The corresponding solution is shown to be either a satisfaction equilibrium (SE), an efficient satisfaction equilibrium (ESE) or a non-equilibrium solution in which the largest population of players are satisfied (N-person satisfaction point, N-PSP). The main two contributions are: (i) A family of functions whose global maximizers are either an ESE, an SE or an N-PSP depending on their existence; and (ii) a fully distributed algorithm that allows the achievability of the above equilibria or non-equilibrium configurations via the decentralized maximization of these functions. In particular, the construction of such functions ensures the convergence of the proposed algorithm to stochastically stable solutions. This property is shown to be independent of the topology of the network or the specific individual QoS constraints.