Mathew Goonewardena
email: pradeep.goonewardena.1@ens.etsmtl.ca

Samir M Perlaza
email: samir.perlaza@inria.fr

Animesh Yadav
email: ya-dav.animesh@uqam.ca

Wessam Ajib
email: ajib.wessam@uqam.ca

Generalized Satisfaction Equilibrium: A Model for Service-Level Provisioning in Networks

Keywords: game theory, satisfaction form games, self-optimizing networks, wireless small-cell networks Théorie de réseaux auto-configurables

This technical report presents a generalization of the existing notion of satisfaction equilibrium (SE) for games in satisfaction form. The new equilibrium, which is referred to as the generalized SE (GSE), is particularly adapted for modeling problems such as service-level provisioning in decentralized selfconfiguring networks. Existence theorems for GSEs are provided for particular classes of games in satisfaction form and the problem of finding a pure strategy GSEs with a given number of satisfied players is shown to be NP-hard. Interestingly, for certain games there exist a dynamic, analogous to the best response of games in normal form, that is shown to efficiently converge to a pure strategy GSE under the given sufficient conditions. Finally, Bayesian games in satisfaction form and the corresponding Bayesian GSE are introduced. These games describe the interactions between players that possess incomplete information in a game in satisfaction form. These contributions form a more flexible framework for studying self-configuring networks than the existing SE framework. This paper is concluded by a set of examples in wireless communications in which classical equilibrium concepts are shown to be not sufficiently adapted to model service-level provisioning. This reveals the relevance of the new solution concept of GSE.

Introduction

Game theory has played a fundamental role in the analysis of decentralized self-configuring networks (DSCNs), e.g., sensor networks, body area networks, small cells, law-enforcement networks. See for instance [START_REF] Lasaulce | Game Theory and Learning for Wireless Networks: Fundamentals and Applications[END_REF][START_REF] Han | Game Theory in Wireless and Communication Networks: Theory, Models, and Applications[END_REF][START_REF] Alpcan | Mechanisms and Games for Dynamic Spectrum Allocation[END_REF] and references therein. A DSCN is an infrastructure-less network in which transmitters communicate with their respective receivers without the control of a central authority, for instance, a base station. Therefore, radio devices must autonomously tune their own transmit-receive configuration to meet a required quality-of-service (QoS) or qualityof-experience (QoE), as well as efficiently exploit the available radio resources. The underlying difficulty of this individual task is that meeting a given QoS/QoE depends also on the transmitreceive configuration adopted by all other counterparts. This suggests that communications networks can be modeled by games as first suggested in [START_REF] Blachman | Communication as game[END_REF], which justifies the central role of game theory. An object of central attention within this context is the equilibrium. The notion of Nash equilibrium (NE) [START_REF] Nash | Equilibrium points in n-person games[END_REF][START_REF] Nisan | Algorithmic game theory[END_REF] is probably the most popular solution to games arising from DSCNs. An NE is reminiscent to notions used in mechanics, for instance, a small perturbation to a system at a stable (mechanical) equilibrium induces the system to spontaneously go back to the equilibrium point. Similarly, within a communication network operating at an NE, any transmitter unilaterally deviating from the equilibrium point degrades its own individual performance and thus, backs down to the initial equilibrium configuration. The relevance of the notion of equilibrium is that it sets up the rules under which a DSCN can be considered stable, and thus exploitable. In any other state, the network cannot be fruitfully exploited as there always exist radio devices aiming to change their individual transmit-receive configurations. Aside from NE, there are other notions of equilibria particularly adapted to DSCN. Each solution concept has advantages and disadvantages, as described in [START_REF] Perlaza | Game-Theoretic Solution Concepts and Learning Algorithms[END_REF].

A major disadvantage that is common to most of equilibrium concepts is that stability depends on whether or not each radio device achieves the highest performance possible. This does not necessarily meet the original problem in which radio devices must only ensure a QoS or QoE condition. To overcome this constraint, a new solution concept known as satisfaction equilibrium (SE) was suggested in [START_REF] Ross | Satisfaction equilibrium: Achieving cooperation in incomplete information games[END_REF] and formally introduced in the realm of wireless communications in [START_REF] Perlaza | Quality-of-service provisioning in decentralized networks: A satisfaction equilibrium approach[END_REF][START_REF]Satisfaction equilibrium: A general framework for QoS provisioning in self-configuring networks[END_REF]. The SE notion relaxes the condition of individual optimality and defines an equilibrium in which all radio devices satisfy the QoS or QoE constraints. From this perspective, radio devices are not anymore modeled by players that maximize their individual benefit but by players that aim at satisfying some individual constraints. This new approach was adopted to model the problem of dynamic spectrum access in [START_REF] Ren | User demand-centric distributed wirless resource sharing in dynamic environment: A QoE game perspective[END_REF][START_REF] Rose | Distributed power allocation with sinr constraints using trial and error learning[END_REF][START_REF] Ellingsaeter | Frequency allocation game in satisfaction form[END_REF] and small cells in [START_REF] Perlaza | On the decentralized management of scrambling codes in small cell networks[END_REF]. Other applications of SE are reported for instance in the case of collaborative filtering in [START_REF] Xu | User participation game in collaborative filtering[END_REF]. In [START_REF] Goonewardena | Existence of equilibria in joint admission and power control for inelastic traffic[END_REF] it is discussed that the normal form games discussed in [START_REF] Andrews | Maximizing capacity in arbitrary wireless networks in the sinr model: Complexity and game theory[END_REF][START_REF] Southwell | Quality of service games for spectrum sharing[END_REF], where the player has a dormant action, have satisfaction form representations, such that their pure strategy NEs coincides with the SEs. However, this equilibrium notion of SE as introduced in [START_REF] Perlaza | Quality-of-service provisioning in decentralized networks: A satisfaction equilibrium approach[END_REF] presents several limitations. As pointed out in [START_REF] Southwell | Quality of service games for spectrum sharing[END_REF] and [START_REF] Mérriaux | On the achievability of efficient satisfaction equilibrium in self-configuring networks[END_REF], the notion of SE is too restrictive. Simultaneously satisfying the QoS/QoE constraints of all radio devices might not always be feasible, and thus an SE cannot be achieved, even if some of the radio devices can be satisfied. Hence, existence of an SE is highly constrained, which limits its application to wireless communications. These limitations are more evident in the case of mixed-strategies. In mixed-strategies, an SE corresponds to a probability distribution that assigns positive probability to actions that satisfy the individual constraints for any action profile that might be adopted by all the other players.

Contributions

In this paper, the notion of SE presented in [START_REF] Perlaza | Quality-of-service provisioning in decentralized networks: A satisfaction equilibrium approach[END_REF] is generalized to embrace the case in which only a subset of the radio devices can satisfy their QoS/QoE individual constraints. This new notion of equilibrium is referred to as generalized satisfaction equilibrium (GSE). At a GSE, there are two groups of players: satisfied and unsatisfied. The former is the set of players that meet their own QoS/QoE conditions. The latter is the set that are unable to meet their own QoS/QoE, given the actions adopted by all the other players. The key point is that at a GSE, none of the actions of a given unsatisfied player allows meeting the individual QoS/QoE constraints and thus, none of the players unilaterally deviates from equilibrium point. Note that if all players can be satisfied then the notion of SE and GSE are identical.

The existence of GSEs in games in satisfaction form is studied and general existence results are presented for some classes of games. Interestingly, these existence conditions are less restrictive than those observed for the case of SE in [START_REF] Perlaza | Quality-of-service provisioning in decentralized networks: A satisfaction equilibrium approach[END_REF]. Nonetheless, the existence of a GSE is shown to be not ensured even in the case of mixed-strategies. This contrasts with other game formulations, such as the normal-form, for which there always exists an NE in mixed-strategies.

The connections between pure strategy GSE and a class of problems known as constrained satisfaction problems (CSPs) are exploited to show that the problem of searching for a pure strategy GSE with a given number of satisfied players, in a game in satisfaction form is NP-hard. A particular subclass of games in satisfaction form is identified for which a simple dynamic, analogous to the asynchronous best-response in normal-form, is shown to converge to a pure strategy GSE.

Finally, for the incomplete information case a new class of games in satisfaction form is introduced: Bayesian games. This class of games builds upon the definition of Bayesian games [START_REF] Harsanyi | Games with incomplete information played by Bayesian players. Parts I-III[END_REF][START_REF] Nisan | Algorithmic game theory[END_REF] to model the case of incomplete information in games in satisfaction form. The corresponding solution concept Bayesian-GSE is also introduced. The relevance of these games in the realm of wireless communications is highlighted by several examples.

The rest of the paper is organized as follows. Sec. 2 introduces games in satisfaction form and presents the definition of GSE. Sec. 3 studies the complexity of the problem of finding a pure strategy GSEs of a finite game in satisfaction form. In particular, it is shown that this problem is NP-hard. Sec. 3.2 introduces the satisfaction-response dynamics and identifies sufficient conditions under which this dynamic converges to a pure strategy GSE. Sec. 4 introduces Bayesian games in satisfaction form, the Bayesian-GSE and Bayesian satisfaction-response dynamics. Sec. 5 discusses applications in wireless networks, GSEs for stable admission control, and numerical results. Finally, Sec. 6 concludes the paper with a discussion of future directions.

Notation

Matrices and vectors are denoted by boldface uppercase and boldface lower case symbols respectively. For square matrice R, the notation R ≺ R (resp. R R ) implies that R -R is positive definite (resp. positive semi-definite). Finite sets are denoted by uppercase calligraphic letters and ∅ denotes the empty set. Given a set N , the corresponding power set (set of all possible subsets) is denoted by P (Y). The cardinality of N is |N | = N (uppercase letter). The indicator function is denoted by N (•) and N (n) = 1 if n ∈ N and N (n) = 0 otherwise. The operator E (•) denotes expectation. Let A i be a finite set, with i ∈ N. Let π i ∈ (A i ) be a probability distribution over the elements of the set A i . The probability that π i assigns to a ∈ A i is denoted by π i (a) . Let the sets A 1 , . . . , A m , with m ∈ N, be finite. The set formed by the Cartesian product of all sets is A A

1 × . . . × A N . The Cartesian product of all sets except A i is A -i A i × • • • × A i-1 × A i+1 × . . . A N .
The elements of A and A -i are denoted respectively by a and a -i .

Satisfaction Form and Generalized Satisfaction Equilibrium

This section introduces games in satisfaction form and generalizes the notion of equilibrium presented in [START_REF] Perlaza | Quality-of-service provisioning in decentralized networks: A satisfaction equilibrium approach[END_REF].

Games in Satisfaction Form

A game G SF in satisfaction form is defined by the triplet

G SF N , {A i } i∈N , {g i } i∈N , (1)
where N is the finite index set of the players and A i is the finite set of pure strategies (actions) of player i ∈ N . Let Π i denote the set of all probability distributions over A i . The correspondence g i : Π -i → P (Π i ) determines the set of strategies that satisfy the individual constraints of player i. More specifically, given a profile

(π i , π -i ) ∈ Π, player i is said to be satisfied if π i ∈ g i (π -i ) .
The correspondence g i should not be confused to a constraint on feasible strategies, as in the case of games with coupled actions [START_REF] Scutari | Monotone games for cognitive radio systems[END_REF]. Player i can choose any π i ∈ Π i as a response to π -i ∈ Π -i , however, only the strategies in g i (π -i ) ⊆ Π i satisfy its individual constraints. When only pure strategies are considered, with a slight abuse of notation, the correspondence in pure strategies is denoted by g i : A -i → P (A i ) . Then, given a -i ∈ A -i , g i (a -i ) ⊆ A i denotes the set of pure strategies that satisfies the individual constraints of player i.

Generalized Satisfaction Equilibrium

Each strategy profile π ∈ Π of the game (1) induces a partition {N s , N u } over the set N of players. Players in the set N s are said to be satisfied, that is, ∀i ∈ N s , π i ∈ g i (π -i ). Alternatively, players in the set N u are said to be unsatisfied, that is, ∀i ∈ N u , π i ∈ Π i g i (π -i ) . The players in N s are satisfied and thus, they do not possess any interest in changing their own strategy. Conversely, players in N u are unsatisfied and thus, to guarantee an equilibrium, it must hold that none of their strategies can be used to satisfy their individual constraints. This notion of equilibrium, namely generalized satisfaction equilibrium, is introduced by the following definition.

Definition 1 Generalized Satisfaction Equilibrium (GSE): π ∈ Π is a GSE of the game in (1) if there exists a partition {N s , N u } of N such that ∀i ∈ N s , π i ∈ g i (π -i ) and ∀j ∈ N u , g j (π -j ) = ∅.
At a GSE strategy profile π ∈ Π, either a player i satisfies its individual constraints or it is unable to satisfy its individual constraints since g i (π -i ) = ∅. From Def. 1 it follows that a pure strategy GSE of (1) is a profile a ∈ A, where ∀i ∈ N s , a i ∈ g i (a -i ) and ∀j ∈ N u , g j (a -j ) = ∅. This equilibrium notion generalizes previously proposed solution concepts to games in satisfaction form. An SE, as introduced in [START_REF] Perlaza | Quality-of-service provisioning in decentralized networks: A satisfaction equilibrium approach[END_REF], is a special case of a pure strategy GSE of Def. 1. Specifically, every GSE in which all players are satisfied in pure strategies is an SE of [START_REF] Perlaza | Quality-of-service provisioning in decentralized networks: A satisfaction equilibrium approach[END_REF]. An -SE, of [START_REF] Perlaza | Quality-of-service provisioning in decentralized networks: A satisfaction equilibrium approach[END_REF], is a GSE in which

N u = ∅ and ∀i ∈ N , g i (π -i ) = {π i ∈ Π i : E gi(a-i) (a i ) = 1 -},
where the expectation is taken over the mixed strategy profile. Finally when = 0, the SE in mixed strategies as introduced in [START_REF] Perlaza | Quality-of-service provisioning in decentralized networks: A satisfaction equilibrium approach[END_REF], also follows as a special case of a GSE of Def. 1.

The set of all GSEs of a game can be categorized by the number of players that are satisfied. An N s -GSE denotes a GSE in which N s ≤ N players are satisfied. An N -GSE satisfies all players and thus, it is referred to as an SE in this paper. The qualifiers mixed-and pure-may be omitted when the meaning is clear from the context.

Existence of Generalized Satisfaction Equilibria

The existence of a GSE in (1) depends on the properties of the correspondences g 1 , . . . , g N . Let g : Π → P (Π) be as follows:

g(π) g 1 (π -1 ) × . . . × g N (π -N ).
(

) 2
Then an SE is a fixed point of g, i.e.,

π ∈ g (π) , (3)
and thus, the tools of fixed-point equations [START_REF] Border | Fixed Point Theorems with Applications to Economics and Game Theory[END_REF] can be used to state existence theorems of SEs. This is not the case for GSEs. Note that at a GSE profile π ∈ Π, where N s < N there exists an i ∈ N for which g i (π -i ) = ∅ and thus, a fixed point is not properly defined. This observation highlights the difficulty of providing a general existence result for a GSE. It also emphasizes the key difference between GSE and NE. By definition an NE is a fixed point of the special case when the correspondences of ( 1) are best response mappings with respect to individual utility functions and therefore, for finite games there always exists at least one NE [START_REF] Nash | Equilibrium points in n-person games[END_REF][START_REF] Nisan | Algorithmic game theory[END_REF]. Thus the satisfaction form in ( 1) is a more general formation that the normal form [START_REF] Perlaza | Quality-of-service provisioning in decentralized networks: A satisfaction equilibrium approach[END_REF]. Existence results can be given for very particular classes of correspondences g 1 , . . . , g N . Consider for instance a game in which player i obtains an expected reward given by the function u i : Π → R and it is satisfied only if the expected reward is higher than a given threshold τ i (the expectation is over the mixed strategies). That is, the set of mixed strategies that satisfies the individual constraints of player i is given by:

g i (π -i ) = {π i ∈ Π i : u i (π) ≥ τ i } . (4)
Examples of games in satisfaction form following this construction are used in [START_REF] Perlaza | Quality-of-service provisioning in decentralized networks: A satisfaction equilibrium approach[END_REF] to describe several dynamic spectrum access problems. In this case, the game in satisfaction form possesses at least one GSE. This observation is formalized by the following proposition.

Proposition 1 The finite game in satisfaction form in [START_REF] Lasaulce | Game Theory and Learning for Wireless Networks: Fundamentals and Applications[END_REF] for which ∀i ∈ N , g i (π

-i ) = {π i ∈ Π i : u i (π) ≥ τ i } , possesses at least one GSE.
The statement of Prop. 1 is only for games with the specified correspondences. Prop. 1 does not hold if the correspondence is modified for instance to

g i (π -i ) = {π i ∈ Π i : τ i ≤ u i (π) ≤ τ i },
with τ i and τ i , any two reals.

Proof: The proof of Prop. 1 uses the argument that at least one GSE of the game in (1), for which g i follows the definition in (4), coincides with at least one NE of the normal-form game:

G NE N , {A i } i∈N , {u i } i∈N . (5)
From the assumption of finite sets of actions and finite set of players, it follows from [START_REF] Nash | Equilibrium points in n-person games[END_REF] that the game in ( 5) possess at least one NE. At an NE, none of player can unilaterally choose another action and improve its individual reward. Thus, at any NE, there always exists a partition N s and N u of the set of players such that ∀i ∈ N s , u i (π) ≥ τ i and ∀j ∈ N u , u j (π) < τ j , and g j (π -j ) = ∅, which is a GSE (Def. 1) of the game in satisfaction form in (1) with correspondence (4). The proof of Prop. 1 states that every NE of ( 5) is a GSE of a game in satisfaction form in which the correspondences are of the form (4). However, the converse is not always true, i.e. the set of GSEs of the game in (1) might be larger than the set of NEs of (5). This is because at a GSE, a player i might still unilaterally deviate and achieve a higher expected utility (but not above the required threshold if it is in N u ), which contradicts the definition of an NE.

In the following example, a game in satisfaction form that does not possess a GSE in mixed strategies is presented. Define a two player game in which each player i has two actions a 1 i , a 2 i , i ∈ {1, 2} . The probability that the strategy of player i assigns to action a j i is π i (a j i ), j ∈ {1, 2} . The correspondence of player 1 is

g1 (π2) = π1 ∈ Π1 : π1 a 1 1 < π1 a 2 1 if π2 a 1 2 ≥ π2 a 2 2 π1 ∈ Π1 : π1 a 1 1 ≥ π1 a 2 1 othewise . ( 6
)
and the correspondence of player 2 is

g2 (π1) = π2 ∈ Π2 : π2 a 1 2 < π2 a 2 2 if π1 a 1 1 < π1 a 2 1 π2 ∈ Π2 : π2 a 1 2 ≥ π2 a 2 2 othewise . ( 7
)
Let π ∈ Π be an arbitrary strategy profile. Then, one of the following cases holds

π 2 a 1 2 ≥ π 2 a 2 2 or π 2 a 1 2 < π 2 a 2 2 . Consider the case π 2 a 1 2 ≥ π 2 a 2 2 . Then, player 1 is either in the case in which π 1 a 1 1 < π 1 a 2 1 or else it is in the case π 1 a 1 1 ≥ π 1 a 2 1 .
In the former, i.e., π 1 a 1 1 < π 1 a 2 1 , player 1 is satisfied. In the latter, i.e., π

1 a 1 1 ≥ π 1 a 2 1 , player 1 deviates to π 1 , with π 1 a 1 1 < π 1 a 2 1 .
Either way when player 2 has π 2 a 1 2 ≥ π 2 a 2 2 , player 1 converges to a strategy in which π 1 a 1 1 < π 1 a 2 1 . However, when player 1 is in this case, player 2 is unsatisfied and it deviates to a strategy π 2 a 1 2 < π 2 a 2 2 . This causes player 1 to be unsatisfied in its current strategy π 1 a 1 1 < π 1 a 2 1 and it deviates to a strategy π 1 a 1 1 ≥ π 1 a 2 1 . Since the above cases cover the entire mixed-strategy space, this game does not possess a GSE.

Complexity of Generalized Satisfaction Equilibria in Pure Strategies

This section establishes the complexity of the GSE search problem in pure strategies. First step is to establish the complexity of the SE search problem. The problem is stated as follows: given the game in satisfaction form in [START_REF] Lasaulce | Game Theory and Learning for Wireless Networks: Fundamentals and Applications[END_REF], if there is a pure strategy SE find it, otherwise indicate that it does not exist. The following proposition asserts its complexity.

Proposition 2 Pure strategy SE search problem is NP-hard.

The method to establish the time complexity of a problem is the polynomial-time Karp reduction [START_REF] Arora | Computational Complexity: A Modern Approach[END_REF]. In the following development the CSP is reduced to the problem of finding an SE in pure strategies. The CSP is NP-complete [START_REF] Bulatov | Complexity of conservative constraint satisfaction problems[END_REF] and it is introduced at the beginning of Appendix A.

Proof: The proof is given in Appendix A The pure strategy N s -GSE search problem is: given the game in satisfaction form in (1) and a natural number N s , with 1 ≤ N s ≤ N , if there is an N s -GSE or higher in pure strategies find it, otherwise, indicate that it does not exist.

Corollary 1 Pure strategy N s -GSE problem is NP-hard.
Proof: Given a routine to solve N s -GSE search problem, the SE search problem can be solved by setting N s = N. Therefore N s -GSE search problem is at least as hard as the SE search problem. Finding the complexity of the mixed strategy GSE search problem is left as an open problem.

Mapping GSE to CSP

The following formulates the problem of finding a GSE in pure strategies as a CSP. The CSP is introduced at the beginning of Appendix A. The variables of the CSP are the pure strategies {a i , . . . , a N } . If for a -i ∈ A -i , g i (a -i ) = ∅, then include a tuple (a i , a -i ), for each a i ∈ g i (a -i ) , in the N -ary relation R i of constraint c i . Else if g i (a -i ) = ∅, then player i may choose any action therefore, there is some flexibility in deciding which tuples to place in the relation R i . One possibility is to include a tuple (a i , a -i ) for each a i ∈ A i . Another possibility is to include a single tuple (a i , a -i ) where a i ∈ A i is the only action the player wants to take when it cannot achieve satisfaction. For example, in wireless access power control a i could be the zero power action. Repeat these steps ∀a -i ∈ A -i and ∀i ∈ N . The resulting CSP is

({a i } i∈N , {A i } i∈N , {c i } i∈N ).
By the above construction of the relations R 1 , . . . , R N , at a solution a ∈ A of this CSP player i has either a i ∈ g i (a -i ) or g i (a -i ) = ∅. Therefore any solution of the above constructed CSP is a pure strategy GSE. Thus algorithms for CSPs can be employed to solve for pure strategy GSEs. Generally distributed CSP algorithms require extensive information sharing between agents [START_REF] Yokoo | Distributed Constraint Satisfaction: Foundations of Cooperation in Multi-agent Systems[END_REF]. Since a GSE with a maximum number of satisfied players is more desirable, one can also consider solving the corresponding optimization problem of the CSP where the objective is to maximize N s . CSP algorithms has been considered in [START_REF] Vickrey | Multi-agent algorithms for solving graphical games[END_REF][START_REF] Soni | Constraint satisfaction algorithms for graphical games[END_REF] to find -Nash equilibria by discretizing the mixed strategy space and formulating a CSP problem.

Satisfaction Response Algorithm

Prop. 2 and Corollary 1 demonstrate that solving for a pure strategy GSE of the game in ( 1) is a hard problem in general. However, it is possible to identify games in satisfaction form that have a special structure and thus, a pure strategy equilibrium can be efficiently found. Suppose Y is a totally ordered set so that ∀y, y ∈ Y either y ≤ y or y ≤ y. Define finite action spaces A i ⊂ Y, ∀i ∈ N , so that A i is totally ordered as well. For all pairs (a, a ) ∈ A 2 , the relation a ≤ a holds if ∀i ∈ N , a i ≤ a i . Alternatively, the relation a < a holds if ∀i ∈ N a i ≤ a i and for at least one j ∈ N a j < a j . The smallest and largest elements of A i are denoted by a i and a i respectively and define the following vectors, a (a 1 , . . . , a N ) and ( 8)

a (ā 1 , . . . , āN ) . (9)
Consider the following mappings:

φ i :A -i → Y and (10)
φ i :A -i → Y. (11)
Given the condition a -i ≤ a -i , the mapping φ i is called order-preserving if

φ i (a -i ) ≤ φ i a -i (12)
and is called order-reversing if

φ i (a -i ) ≥ φ i a -i . ( 13
)
Then consider the game in satisfaction form in (1) and let the correspondence g i , ∀i ∈ N , be defined by

g i (a -i ) = {a i : φ i (a -i ) ≤ a i ≤ φi (a -i ) (14)
in which both φ i and φ i be order-preserving.

RR n°8883

For a ∈ A, if a i / ∈ g i (a -i ) and if g i (a -i ) = ∅, then there always exists an a i ∈ g i (a -i ) that player i can use to satisfy its individual constraints. This deviation a i is called a satisfaction response and is denoted by SR i (a -i ) ∈ g i (a -i ). Let N u ⊆ N be the subset of unsatisfied players with nonempty correspondence, i.e., i ∈ N u , if a i / ∈ g i (a -i ) and g i (a -i ) = ∅. Then consider the discrete time asynchronous update sequence in which at each instance a subset N ⊆ N u , performs satisfaction response. This update process is called asynchronous, as opposed to synchronous, in which all players in N u perform the response and as opposed to sequential, in which only one of those players at a time performs the response. Algorithm 1 provides the pseudo code for asynchronous satisfaction response and Prop. 3 states its convergence properties.

Algorithm 1 Asynchronous Satisfaction Response

Initialize a = a While a is not a GSE:

Select N ⊆ N u a := (SR j (a -j )) j∈N , (a i ) i∈N N
Proposition 3 Consider a game in satisfaction form (1) with ∀i ∈ N , g i given by [START_REF] Perlaza | On the decentralized management of scrambling codes in small cell networks[END_REF]. Then, starting at a ∈ A the asynchronous satisfaction response algorithm converges to a pure strategy GSE.

Proof: By definition of the satisfaction response game, when initialized at a ∈ A, if at the current profile a, the player i ∈ N u and g i (a -i ) = ∅, then a i < φ i (a -i ) . Then when i performs satisfaction response, a i < SR i (a -i ) ≤ φ i (a -i ) . Since at each satisfaction response the players in N advance at least one action in their ordered action spaces and since the number of players and the action spaces are finite the algorithm terminates in finite time either when N u = ∅ or ∀i ∈ N u g i (a -i ) = ∅. In the above proof there is the implicit assumption that every player that finds itself in N u with a nonempty correspondence performs satisfaction response within a finite number of future steps. If ∀i ∈ N and ∀a -i ∈ A -i , φ i , φ i are order-reversing, then Algorithm 1 converges initialized at a ∈ A. Worst case iterations for sequential satisfaction response is O (N max {|A i | : i ∈ N }) which occurs when all players are initially in N u and each player advances to N s with SR i (a -i ) = φ i (a -i ) only to be found back in N u at the beginning of its next chance to respond. Simultaneous satisfaction response is bounded by O (max {|A i | : i ∈ N }) . Convergence time of the more general asynchronous case can be bounded between the sequential and simultaneous limits, with the minor condition that every player in N u has to perform a response at least once in a predetermined time interval lower than N .

Algorithm 1 applies to infinite action spaces that are closed intervals in the real line. However in that case convergence time may depend on the minimum step size. Power control in continuous domain to achieve a required rate is an example and is discussed in Section 5.1. Sequential satisfaction response up to a predefined fixed number of iterations is discussed in [START_REF] Ross | Satisfaction equilibrium: Achieving cooperation in incomplete information games[END_REF] as a possible learning algorithm however, conditions for convergence are not identified.

Bayesian Games in Satisfaction Form

In many wireless network problems, global CSI is not common knowledge among transceivers, therefore can be modeled as Bayesian games of incomplete information which were formalized by John Harsanyi [START_REF] Harsanyi | Games with incomplete information played by Bayesian players. Parts I-III[END_REF][START_REF] Nisan | Algorithmic game theory[END_REF]. In a Bayesian game a player possesses private information, called its type. The type set of player i is denoted by X i . All players share common knowledge of the joint distribution F x of the random type vector x (x 1 , . . . x i , . . . , x N ), where x i is a random variable over X i . A pure strategy of i is a mapping s i : X i → A i that assigns an action to every type in X i [START_REF] Shoham | Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations[END_REF]. The set of pure strategies of i is denoted by S i such that s i ∈ S i . Define s (s 1 , . . . , s N ) and s -i (s 1 , . . . , s i-1 , s i+1 , . . . , s N ), where s ∈ S and s -i ∈ S -i . In this section the mixed strategy set Π i is the set of all probability distributions over S i and a mixed strategy of i is denoted by π i ∈ Π i [START_REF] Shoham | Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations[END_REF]. Given type x i , the probability which π i assigns to a i ∈ A i is denoted by π i (a i | x i ) . The correspondence is g i : Π -i × X i → Π i . Then a Bayesian game in satisfaction form is the tuple:

G BSF N , {A i } i∈N , {X i } i∈N , {g i } i∈N , F x . ( 15
)
Having a correspondence for each type in X i comes useful for instance in modeling a minimum rate requirement that depends on a queue length or a minimum signal to interference and noise ratio (SINR) based on the channel gain. For a strategy profile (π i , π -i ) ∈ Π, player i is said to be unsatisfied if π i / ∈ g i (π -i , x i ) for at least one x i ∈ X i and conversely i is satisfied if ∀x i ∈ X i , π i ∈ g i (π -i , x i ) . Then the Bayesian-GSE is defined as follows.

Definition 2 Bayesian Generalized Satisfaction Equilibrium (Bayesian-GSE):The profile π ∈ Π is a Bayesian-GSE of ( 15) if there exists a partition {N s , N u } of N such that ∀i ∈ N s , ∀x i ∈ X i , π i ∈ g i (π -i , x i ) and ∀j ∈ N u , if for some x j ∈ X i π j / ∈ g j (π -j , x j ), then g j (π -j , x j ) = ∅.

Def. 2 essentially sates that at a Bayesian-GSE, players in N u are unable to deviate and achieve satisfaction for the types in which they are unsatisfied. A Bayesian-GSE with N s number of satisfied players is called an N s -Bayesian-GSE and if all players are satisfied it is called a Bayesian-SE. This equilibrium is Bayesian in the sense that g i (π -i , x i ) can be defined as the achievement of a performance level in expectation over the posterior F x|xi . As in complete information case, with a slight abuse of notation, the pure strategy correspondence is denoted by g i : S -i ×X i → S i , such that given s -i ∈ S -i , g i (s -i , x i ) ⊆ S i .

For π ∈ Π, let E x|xi u i (π, x) denotes the ex interim expected utilities of i [28] and τ i (x i ) ∈ R a threshold, which can possibly take different values for x i ∈ X i . The expectation is over the mixed strategies and the posterior F x|xi . A Bayesian game is finite when the sets of players, actions, and types are all finite. Then, Prop. 4 is the Baysian counter part to Prop. 1.

Proposition 4 A Finite Bayesian game in satisfaction form [START_REF] Xu | User participation game in collaborative filtering[END_REF] where ∀i ∈ N and ∀x i ∈ X i , g i (π -i , x i ) = {π i ∈ Π i : E x|xi u i (π, x) ≥ τ i (x i )}, has at least one Bayesian-GSE.

Proof: Given the above Bayesian satisfaction form game, construct the Bayesian normal form game as follows

G BNE N , {A i } i∈N , {X i } i∈N , {u i } i∈N , F x , (16)
where u i is the utility of i ∈ N . The proof follows by noting that at a Bayesian-Nash equilibrium π ∈ Π of ( 16), ∀i ∈ N the ex interim expected utility

E x|xi u i (π, x) is a maximum ∀x i ∈ X i . Thus if player i for type x i has E x|xi u i (π, x) < τ i (x i ) , then i cannot deviate and improve E x|xi u i (π, x)
. Hence for any unsatisfied types

x i of i, g i (π -i , x i ) = ∅, which by Def. 2 is a Bayesian-GSE.
It is possible to identify satisfaction-response-Bayesian games for pure strategies. Recall the totally ordered action spaces from Section 3.2, where ∀i ∈ N , A i ⊂ Y. Let φ i : S -i × X i → Y and

φ i : S -i × X i → Y. Then φ i is called order-preserving if ∀x -i ∈ X -i , s -i (x -i ) ≤ s -i (x -i ) , then ∀x i ∈ X i φ i (s -i , x i ) ≤ φ i (s -i , x i ). Then (15) is a satisfaction-response-Bayesian game if ∀i ∈ N g i (s -i , x i ) = {s i ∈ S i : φ i (s -i , x i ) ≤ s i (x i ) ≤ φi (s -i , x i )}
, where φ i , φi are order-preserving. Let us define ∀x i ∈ X i , s i (x i ) a i , and s (s i ) i∈N .

Proposition 5 For a satisfaction-response-Bayesian game, starting from s the asynchronous satisfaction response algorithm converges to a pure strategy Bayesian-GSE.

Proof: The proof is similar to that of Prop. 3 except each type has to be considered. Initialized at s, if i ∈ N u performs satisfaction response at the current profile s, then ∀x i ∈ X i where g i (s -i , x i ) = ∅, s i (x i ) ≤ SR i (s -i , x i ) ≤ φi (s -i , x i ) and for at least one x i (for which i was unsatisfied) s i (x i ) < SR i (s -i , x i ) ≤ φi (s -i , x i ) . Therefore, for each unsatisfied type the strategies monotonically advances in the ordered action space. Since the number of players, actions, and types are finite the algorithm terminates when either N u = ∅ or ∀i ∈ N u for all unsatisfied types x i ∈ X i , g i (s -i , x i ) = ∅.

Applications of GSEs

This section presents several applications of games in satisfaction form in wireless network problems for complete and incomplete information cases. The objective is to demonstrate the applicability of GSE to standard problems. Power control and channel allocation are the main focus. Also efficient-GSEs are discussed for the admission control problem.

Uplink Power Control Game

Power control under per user rate requirements has been well studied for its feasible region and Pareto optimal solutions [START_REF] Hande | Distributed uplink power control for optimal SIR assignment in cellular data networks[END_REF]. The possibly infeasible case in which a subset of the transmitters may not be satisfied has received less attention. In [START_REF] Monemi | Distributed multiple target-SINRs tracking power control in wireless multirate data networks[END_REF] the over constrained SINR targets are handled by introducing multiple SINR targets such that the infeasible users switch to lower targets.

The single-input-single-output (SISO) power control game in the interference channel is presented in [START_REF] Scutari | Potential games: A framework for vector power control problems with coupled constraints[END_REF] as a generalized Nash equilibrium problem. The following development considers single-input-multiple-output (SIMO) case as a satisfaction-response game. The baseband equivalent signal at the destination of transmitter i is

y i = √ p i h ii s i + j∈N {i} √ p j h ji s j + z i , (17)
where y i ∈ C ni is the received symbol vector at the receiver of i th transmitter, n i is the number of receiver antennas, s i ∈ C is the transmitted symbol of i, h ji ∈ C ni is the channel between transmitter j and destination of i, and z i ∼ CN (0, σI) is the circular symmetric complex additive white Gaussian noise. The payoff of transmitter i is the achievable rate u i p i , p -i = log(1 + p i h H ii R -1 -i h ii ) bits/sec/Hz, where R -i = j∈N {i} p j h ji h H ji + σI is the interference plus noise covariance matrix. The transmit power is p i ∈ P i , where

P i = [p i , p i ], p i , p i ∈ R ≥0 .
The game in satisfaction form played by the transmitters is

G PC N , {P i } i∈N , {g i } i∈N , (18)
in which ∀i ∈ N g i p -i = {p i ∈ P i : τ i ≤ u i (p) ≤ τi } , where 0 ≤ τ i ≤ τi . The upper bound τ i is considered for the sake of generality. For instance the transmitter or receiver may have a maximum operational rate. This model is valid for τi = +∞, which corresponds to rate unbounded from above.

Define ∀i ∈ N φ i p -i = inf pi∈R p i : u i p i , p -i ≥ τ i and φi p -i = sup pi∈R p i : u i p i , p -i ≤ τ i .
Then restate the correspondence g i p -i ≡ {p i ∈ P i :

φ i p -i ≤ p i ≤ φ i p -i .
From the properties of positive (semi-)definite matrices [START_REF] Horn | Matrix Analysis[END_REF],

p -i ≤ p -i implies R -1 -i p -i R -1 -i p -i which
in turn implies u i p i , p -i ≤ u i p i , p -i and therefore concludes that φ i p -i ≤ φ i p -i and φi p -i ≤ φi p -i . The inequalities hold strictly if p -i < p -i . Thus by extension of Prop. 3 to action spaces that are closed intervals in the real line Algorithm 1 converges for game [START_REF] Southwell | Quality of service games for spectrum sharing[END_REF]. If the upper threshold is removed, by setting τi = +∞, the stronger condition p -i < p -i implies g i p -i ⊂ g i p -i holds.

The players must know the noise and interference covariance matrix and can be obtained from the receiver. The standard power control game is to minimize the transmit power with peruser rate constraints and it is a generalized NE problem where a solution may not exist if over constrained, where as [START_REF] Southwell | Quality of service games for spectrum sharing[END_REF] always has a GSE. Even assuming the feasibility of the problem, the update algorithms proposed in [START_REF] Scutari | Potential games: A framework for vector power control problems with coupled constraints[END_REF] require projection into the global feasible set, which requires extensive information exchange between users at each iteration.

Efficient-GSEs and Admission Control

At a pure strategy GSE p ∈ P of (18), an unsatisfied player i ∈ N u obtains u i (p) < τ i , but may have p i > p i . If a player in N u lowers its power, then it is possible that another in N u can deviate to satisfaction and thus disrupt the equilibrium. In some applications it is desirable that at a GSE ∀i ∈ N u p i = p i . Such profiles are called efficient-GSEs as the N u poses the least interference to N s . Efficient-GSEs do not necessarily exist.

In most scenarios ∀i ∈ N p i = 0. Then at an efficient-GSE ∀i ∈ N u p i = 0, and thus serves as an admission control scheme where the unsatisfied players remain switched-off. However, unlike a traditional admission control scheme as in [START_REF] Halldórsson | Wireless capacity and admission control in cognitive radio[END_REF], an efficient-GSE is stable, i.e., the players who do not transmit are aware that they cannot achieve satisfaction even at maximum power. The mapping outlined in Section 3.1 can be used to solve for efficient GSEs in a finite action space game of discrete power levels by way of solving a CSP.

Orthogonal Resource Allocation Game

Consider the problem of allocating a finite set K of orthogonal resources among N interfering SISO wireless channels. The action set of transmitter i is K i ⊆ K, while transmit power remains constant. Transmitter i is said to be satisfied if the SINR at its receiver is above a threshold,

γ i (k i ) := |h k i ii | 2 pi j∈N {i} |h k i ji | 2 pj +σ k i i ≥ τ i , k i ∈ K i , | h ki ji | 2 ≥
0 is the power gain from transmitter j to receiver of i on k i , and noise power σ ki i > 0. The game in satisfaction form is:

G CH N , {K i } i∈N , {g i } i∈N , (19)
where

∀k -i ∈ K -i g i (k -i ) = {k i ∈ K i : γ i (k i ) ≥ τ i , } .
By Prop. 1 game ( 19) has at least one GSE in mixed strategies. Prop. 6 shows that searching for a pure strategy SE of ( 19) is NP-hard.

Proposition 6

The pure strategy SE search problem of ( 19) is NP-hard.

Proof: The proof is given in Appendix B. Corollary 1 observes that if an efficient algorithm exists to solve the N s -GSE search problem then that algorithm can efficiently solve the SE search problem of the same game. Therefore finding an N s -GSE of ( 19) is NP-hard as well.

Bayesian Game for Power Control

Consider the SIMO multiple access interference channel of Section 5.1. In the Bayesian setup, the private information of player i is its direct channel to its destination h ii ∈ X i , which can be obtained through feedback. Define the vector of all channels (direct and interference) h = (h ij ) i,j∈N . A pure strategy of i depends on its channel to its receiver s i (h ii ). The utility of transmitter i is

u i (s, h) = log 2 (1 + s i (h ii )h H ii R -1 -i h ii ).
The resulting Bayesian power control game is

G BPC N , {P i } i∈N , {X i } i∈N , {g i } i∈N , F h , (20)
where

g i (s -i , h ii ) = s i ∈ S i : τ i ≤ E h-i u i (s, h) ≤ τ i
and the thresholds are as in [START_REF] Southwell | Quality of service games for spectrum sharing[END_REF]. Independence of types among players are assumed. The correspondence can be restated as

g i (s -i , h ii ) = {s i ∈ S i : s i (h ii ) ∈ P i , φ i (s -i , h ii ) ≤ s i (h ii ) ≤ φ i (s -i , h ii ) , where φ i (s -i , h ii ) = inf pi∈R p i : E h-i u i (s, h) ≥ τ i ,
and

φ i (s -i , h ii ) = sup pi∈R p i : E h-i u i (s, h) ≤ τ i .
From the properties of positive (semi-)definite

matrices ∀h ∈ X , s -i (h -i ) ≤ s -i (h -i ) implies φ i (s -i , h ii ) ≤ φ i (s -i , h ii ) and φ i (s -i , h ii ) ≤ φ i (s -i , h ii ).
Thus, G BPC is a satisfaction-response game and by Prop. 3, Algorithm 1 converges for game [START_REF] Harsanyi | Games with incomplete information played by Bayesian players. Parts I-III[END_REF].

Numerical Results

Consider G PC in [START_REF] Southwell | Quality of service games for spectrum sharing[END_REF] for continuous power domain. The network consists of three small-cell base stations (SBSs), each serving two SUEs in a closed access manner. The SUEs are equipped with a single antenna whereas the SBSs have 4 antennas each. The SBSs and the SUEs are i.i.d. uniformly distributed over a circular area of unit radius. The elements of the channel vector h ji i, j ∈ N are independent circular symmetric complex Gaussian with zero mean and variance equal to the pathloss with exponent α = 3. The power domain is P i = [0, 10] W.

The scaled noise power spectral density is 10 -6 W/Hz, and the channel bandwidth is 1MHz.

Then simultaneous satisfaction response by Algorithm 1 is initialized at p = 0. The step size of SR i (a -i ) = 0.2×(p i max -p i min )×U +p i min , where p i max , p i min are the maximum and minimum feasible power respectively and U is the standard uniform random variable. It is assumed that the channels remain constant during the convergence. Fig. 1 depicts the rates at convergence to pure strategy GSEs for the six players. In Fig. 1a, all players achieve satisfaction at the GSE and in Fig. 1b, one player fails to achieve satisfaction at the GSE. The number of satisfied players depends on the channel realizations and thresholds. For a given threshold the number of satisfied players depends on the channel realizations. Fig. 2 compares GSE and Nash solutions for the number of satisfied UEs. The corresponding NE problem is G PC-NE (N , {P i } i∈N , {u i } i∈N ), where payoff u i is the achievable rate. From the monotonicity of u i in p i , a player i transmits at its maximum power at a NE. As expected the GSE is able to satisfy more players than the Nash solution.

Next consider the Bayesian power control game G BPC (20) of Section 5.4 with ∀i ∈ N g i (s -i , h ii ) = s i ∈ S i : E h-i u i (s, h) ≥ τ i . The pure strategy s i gives an action for each realization of the type in X i . Therefore for numerical tractability, single antennas UEs and SBSs and a discrete channel model is considered. Let the channel power gains ∀i, j ∈ N | h ij | 2 be equiprobably distributed in two levels {0.25, 0.75} . The power domain is P i = [0, 10] W. The other network parameters are as in G PC . Fig. 3 depicts the convergence of rate and power levels for a single player by the simultaneous satisfaction response using Algorithm 1. Algorithm 1 is initialized at p = 0 and SR i (s -i , x i ) is set to the minimum feasible power.

Number of satisfied players

Probability

GSE τ i = 1 bits/s/Hz, τ i = 3 bits/s/Hz Nash equilibrium τ i = 1 bits/s/Hz, τ i = 3 bits/s/Hz GSE τ i = 6 bits/s/Hz, τ i = 8 bits/s/Hz Nash equilibrium τ i = 6 bits/s/Hz, τ i = 8 bits/s/Hz Finally efficient-GSEs are evaluated. The discrete power control problem with L + 1 power levels, {0, p L , . . . , (L-1)p L , p}, is investigated for efficient-GSEs where the unsatisfied players must assign zero power. Here L is a positive integer. The rest of the parameters are as G PC discussed earlier. The efficient-GSE problem is modeled as a CSP as discussed in Section 5.2 and then solved using a brute force CSP solver. For a given set of transmit power levels and τ i , τ i ∀i ∈ N , the existence of an efficient-GSE is a property of the channel realizations. From the simulation results in Table 1 it is observed that as τ i grows efficient-GSEs exists with very high probability. However, as L grows the complexity of the CSP grows exponentially and hence becomes computationally intractable.

Conclusion

This paper presents the novel generalized satisfaction equilibrium (GSE) for games in satisfaction form. When players attempt to satisfy a required service level, rather than maximize their utility, at a GSE the unsatisfied players are unable to unilaterally deviate to achieve satisfaction. GSE bridges constraint satisfaction problems and games in satisfaction form as the two problems can be transformed to each other. Finding a pure strategy GSE is shown to be NP-hard. The paper presents the relation of GSE to NE and of satisfaction form to normal form. It also presents results of existence of GSEs for special classes of games and offers counter examples to the general case. The class of satisfaction-response games are shown to be efficiently solvable. The incomplete information case is considered under Bayesian-GSEs. To demonstrate the applicability of GSE, standard wireless problems are solved and compared in performance against Nash equilibria. An important GSE is when the unsatisfied players pose the least resistance to the satisfied players. This is called an efficient equilibrium. It is our understanding that efficient-GSEs possess immense potential for self-organization in heterogeneous networks. There is much to be explored in efficient equilibria in terms of existence and distributed algorithms.

p i (W) (τ i , τ i ) bits/s/

Appendices

A The CSP and the Proof of Prop. 2

The CSP is briefly introduced here and a comprehensive description can be found in [START_REF] Bulatov | Complexity of conservative constraint satisfaction problems[END_REF][START_REF] Kumar | Algorithms for constraint satisfaction problems: A survey[END_REF] and references therein. In a finite domain D, a q-ary relation is a set of length q tuples of the form (d 1 , . . . d q ) , where the elements are from D. An instance of CSP is defined by (V, D, C) , where V = {v 1 , . . . , v V } is the set of variables, D is the finite domain of the variables, and

C = {c 1 , . . . , c C } is a collection of constraints. Constraint c i is a pair (v qi , R i ), where the list v qi = (v i1 , . . . , v iqi ), 1 ≤ q i ≤ V, v i1 , . . . , v iqi ∈ V and R i is a q i -ary relation on D. An assignment a = (v j , d j ) j∈V , is a single value d j ∈ D given to each variable v j ∈ V. Assignment a is said to solve the CSP if ∀c i ∈ C, the v qi component of a is a tuple in the relation R i .
In complexity analysis the representation of the problems are important as they are compared with respect to the input size. Here it is considered that ∀i ∈ N , g i is provided in tabular form with two columns a -i and g i (a -i ) . That is for each a -i ∈ A -i for which g i (a -i ) is nonempty there is an entry/row in the table. For a -i with no entry in the table g i (a -i ) is empty.

Proof: The CSP is given by (V, D, C) . If C < V, then introduce V -C number of dummy unary constraints c j , C < j ≤ V of the form (v j , R j ) where R j has a unary tuple for each element of D. These constraints are dummy as they are satisfied by any assignment to v j . If V < C, then introduce C -V dummy variables. Let this derived, either adding constraints or variables, CSP be ( V, D, C). Observe that an assignment is a solution to ( V, D, C) iff it solves (V, D, C) . Define a game in satisfaction form with max {V, C} players and set A i = D. Assign v i ∈ V and c i ∈ C to player i. The strategy of player i is to assign a value a i (v i ) ∈ A i , to v i and it is satisfied if c i is satisfied.

If the list v qi of c i contains the v i , then construct table g i as follows. Each tuple in R i can be considered as values assigned to the variables in v qi by the respective players who own each variable i.e., (a i1 (v i1 ), . . . a i (v i ), . . . , a iqi (v iqi )) ∈ R i , where a i (v i ) is assigned by player i itself. The idea is to add values of variables of other players on the left column of g i and put the corresponding a i (v i ) on the right column but keeping in mind that more than one tuple in R i can have the same value assignment to other variables but with different values to v i . Take a tuple from R i , if the values of variables except v i is not already in the left column of the table add it in a new row and corresponding a i (v i ) on the right column of that row. If on the other hand that exact value combination of other variables is already in the left column then append to the right column (to the existing values) the new a i (v i ) . If list v qi does not contain v i , then construct g i with one row for each tuple in R i on the left column and the entire set D on each row on the right column, i.e., the satisfaction of i does not depend on its action but only on the actions of others. These mappings are polynomial time in size of ( V, D, C). Construction of game ( 1) is now complete. If an assignment a is an SE then that assignment is found in g i ∀i ∈ N , which by construction implies that the assignment is in R i ∀i ∈ N , hence solves ( V, D, C). Conversely if a solves ( V, D, C) then it is in R i ∀i ∈ N , then by construction that assignment is in g i ∀i ∈ N , hence an SE. It was already established that a solution to ( V, D, C) solves (V, D, C) . Therefore the SE search problem is NP-hard.

B Proof of Prop. 6

Proof: The NP-hardness is proven by a polynomial time reduction from the set partition problem to [START_REF] Mérriaux | On the achievability of efficient satisfaction equilibrium in self-configuring networks[END_REF]. Set partition is a known NP-complete problem [START_REF] Garey | Computers and Intractability; A Guide to the Theory of NP-Completeness[END_REF]. It is defined by an input set P = {p 1 , . . . p P } of positive integers and the problem is to decide if there is a partition of P into two subsets P 1 and P 2 such that the sum of elements of the two sets are equal. Let us denote by τ the value of sum of each partition so that the total sum of elements of P is 2τ . Let N = P + 2 be the number of players and K = k 1 , k 2 , 2 resources. Let σ k i = σ, ∀1 ≤ i ≤ P + 2 and ∀k ∈ K. The transmit powers of the first P players are the numbers p i ∈ P, 1 ≤ i ≤ P. For those P players 1 ≤ i ≤ P, ∀k ∈ K let | h k ij | 2 = 1, where 1 ≤ j ≤ P + 2. The last two players i ∈ {P + 1, P + 2} have power p P +1 = p P +2 = 1 and they do not interfere the first P players, i.e., ∀1 ≤ j ≤ P and ∀k ∈ K | h k ij | 2 = 0, but they interfere each other ∀ij ∈ {P + 1,

P + 2} | h k ij | 2 = 1.
In summary, the first P players have identical unit gain channels to all receivers, the last two players have zero gain channels to the receivers of the first P players while having unit gain channels to the receivers of those two. Let ∀i ∈ N τ i = pi τ +σ . Let K i = K ∀1 ≤ i ≤ P and K P +1 = k 1 and K P +2 = k 2 . Then for players P + 1 and P + 2 to be satisfied, the sum of received interference powers on each channel due to the first P players has to be less than or equal to τ, but since 1≤i≤P p i = 2τ, they necessarily have to be equal to τ. Observe that from the construction if P + 1 and P + 2 are satisfied then all 1 ≤ i ≤ P are satisfied as well. Thus a pure strategy channel allocation is an SE of the constructed game iff it is a valid set partition of P.

  Pure strategy SE for τ i = 1bits/s/Hz and τ i = 3bits/s/Hz.

5 -

 5 GSE in pure strategies for τ i = [3]bits/s/Hz and τ i =[START_REF] Nash | Equilibrium points in n-person games[END_REF]bits/s/Hz.

Figure 1 :

 1 Figure 1: Convergence of Algorithm 1 for G PC .

Figure 2 :

 2 Figure 2: Comparison of probability of satisfaction between pure-GSEs and Nash equilibria for G PC and G PC-NE .

Figure 3 :

 3 Figure 3: Convergence of simultaneous satisfaction response algorithm for G BPC for a single player in a symmetric network.

  Equilibrium de Satisfaction Généralisée: Un Modèle pour Fournir de Niveau de Service dans les Réseaux Résumé : Ce rapport technique présente une généralisation de la notion existante d'équilibre de satisfaction (ES) pour les jeux de satisfaction. Le nouvel équilibre, appelé ES généralisé (ESG), est particulièrement adapté à la modélisation de problèmes tels que la fourniture de services dans les réseaux auto-configurables. Des théorèmes d'existence pour les ESG sont présentés pour des classes particulières de jeux de satisfaction et il est démontré que la recherche d'un ESG en stratégie pure avec une contrainte de nombre de joueurs satisfait est un problème NP-complexe. Il est aussi intéressant de remarquer qu'il existe pour certains jeux une dynamique, analogue à la meilleure réponse dans le cas des jeux sous forme normale, qui converge efficacement vers un ESG en stratégie pure avec les conditions suffisantes indiquées. Enfin, les jeux de satisfaction Bayesiens et l'ESG Bayesien correspondant sont présentés. Ces jeux décrivent les interactions entre des joueurs qui ont une information incomplète dans les jeux de satisfaction. Ces contributions forment un cadre plus flexible facilitant l'étude des réseaux auto-configurables, relativement à l'ES existant. Cet article est conclu par un ensemble d'exemples de réseaux sans fils dans lesquels le concept classique d'équilibre se révèle inadapté à la modélisation de la fourniture de services, soulignant ainsi la pertinence de ce nouveau concept d'ESG.

Table 1 :

 1 Probability of existence of efficient-GSE

			Hz Pr{efficient-GSE} Avg. satis. users
	1	(1, 5)	0.9460	2.4353
	1	(1, 20)	0.9951	3.8418
	1	(1, 50)	0.9994	3.9022
	10	(1, 5)	0.9252	2.1291
	10	(1, 20)	0.9747	4.4762
	10	(1, 50)	0.9990	4.5086
		(a) L = 1, for two actions of transmit and do not transmit.
	p i (W) (τ i , τ i ) bits/s/Hz Pr{efficient-GSE} Avg. satis. users
	1	(1, 5)	0.9682	2.7629
	1	(1, 20)	0.9980	3.8861
	1	(1, 50)	0.9997	3.9415
	10	(1, 5)	0.9374	2.7401
	10	(1, 20)	0.9897	4.5544
	10	(1, 50)	0.9999	4.5933

(b) L = 2, for three actions {0, 0.5p i , p i } .

RR n°8883

This work was supported in part by the European Commission under Individual Fellowship Marie Skłodowska-Curie Action (CYBERNETS) through Grant 659316.


Lokman Rahmani

Gabriel Antoniu

Luc Bougé

Luc Bougé Towards Smart

Towards Smart Visualization for HPC Simulations

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Towards Smart Visualization for HPC Simulations

Lokman Rahmani 1,2 , Supervisors: Gabriel Antoniu 3 & Luc Bougé 1,2 1 ENS Rennes, 2 IRISA Rennes, 3 INRIA Rennes, France

Context

• HPC platforms featuring millions of cores • HPC scientific simulation on 100.000+ cores • Petabytes of data to be post-processed and visualized

• Increasing gap between computational power and I/O capacity The Problem : Too much data generated by simulations! Preparing data for visualization take too much time, which may block the simulation. This impacts badly the performances of the whole simulation process.

Our Idea: Smart ISV Framework Architecture

• Define a semantics of the data: variation in data • Automatically detect interesting parts of data • Adapt the resolution of the visualization

Implementation and Integration

Integration into existing ISV (Damaris/Viz [2]):

• Without any code modification in the simulation

• No reconfiguration of the visualization tool (VisIt [START_REF]VisIt[END_REF]).

Automatically detect relevant data

Using different metrics, with respect to the defined semantics:

• Statistics: Coefficient of variation 3 Visualizing only the relevant parts of the generated data provides up to 40% gain in visualization time without quality loss.

Figure 1 :

 1 Figure 1: Blue Waters NCSA supercomputer[1]

Figure 2 :

 2 Figure 2: CM1 Tornado simulation

1

  Defined data semantics: more variation in the data implies interesting data 2 Automatically detect the relevant parts of the data with respect to the defined semantics.

Acknowledgements

This work is done within framework of the Joint Laboratory for Petascale Computing, an international collaboration between INRIA, the University of Illinois at Urbana-Champagn (IL. USA), and Argonne National Laboratory (IL. USA).