Van-Minh Pho

Anne-Laure Ligozat

Brigitte Grau

Distractor quality evaluation in Multiple Choice Questions

Keywords: Multiple choice questions, natural language processing, automatic quality evaluation, production of educational material

Multiple choice questions represent a widely used evaluation mode; yet writing items that properly evaluate student learning is a complex task. Guidelines were developed for manual item creation, but automatic item quality evaluation would constitute a helpful tool for teachers.

In this paper, we present a method for evaluating distractor (i.e. incorrect option) quality that combines syntactic and semantic homogeneity criteria, based on Natural Language Processing methods. We perform an evaluation of this method on a large MCQ corpus and show that the combination of several measures enables us to validate distractors.

Introduction

Multiple Choice Questions (MCQs) are widely used in many educational and evaluation contexts since their assessment can be automated and they have proven to be relevant and objective indicators of the learner skills [START_REF] Haladyna | A review of multiple-choice item-writing guidelines for classroom assessment[END_REF]. Yet, writing multiple choice items is costly, and the quality of MCQ is crucial in order to ensure that learners will perform according to their skills. Guidelines have been developed [START_REF] Burton | How to prepare better multiple-choice test items: Guidelines for university faculty[END_REF] to help create quality MCQs. However, actual MCQs can present flaws because educators may not have formal instruction for writing MCQs [START_REF] Tarrant | Impact of item-writing flaws in multiple-choice questions on student achievement in high-stakes nursing assessments[END_REF]. An automatic evaluation of MCQs quality could thus help educators.

A MCQ is composed of two parts (cf. example below): the stem and the options (or choices), which include both the answer (correct option), and one or several distractors (incorrect options).

Stem: What country is Kimchi from? Answer: Korea Distractors: Japan, China, Mongolia Selecting distractors is a difficult task when creating a MCQ: the quality of a MCQ relies heavily on the quality of these options [START_REF] Rodriguez | Three options are optimal for multiple-choice items: A metaanalysis of 80 years of research[END_REF]. The objective of this paper is the automatic evaluation of the quality of options according to writing rules. In particular, the rule "Keep choices homogeneous in content and grammatical structure" leads us to propose a definition of syntactic and semantic homogeneity. Homogeneous in content means that options must share semantic features, but are, nonetheless, sufficiently different to be plausible answers but not possible answers.

We propose to evaluate homogeneity by comparing each distractor to the answer and by computing criteria based on syntactic parsing and the use of different semantic resources to cover numerous semantic relationships that are combined in a machine learning model. We focused our work on short options, expressed by chunks (lowest-level phrases) and named entities. Previous research on automatic distractor selection had more restrictions on the type of options [START_REF] Karamanis | Generating multiple-choice test items from medical text: A pilot study[END_REF][START_REF] Mitkov | Semantic similarity of distractors in multiple-choice tests: extrinsic evaluation[END_REF], or was dedicated to a specific domain [START_REF] Karamanis | Generating multiple-choice test items from medical text: A pilot study[END_REF]. To our knowledge, it is the first attempt to evaluate automatically the semantic quality of MCQ distractors. We will show that our method outperforms state-of-the-art methods.

Evaluating the homogeneity of options

In order to help teachers create well-formed MCQs, guidelines were developed. One of the most popular set of guidelines was written by [START_REF] Haladyna | A review of multiple-choice item-writing guidelines for classroom assessment[END_REF]. It is composed of 43 rules grouped in categories related to MCQ content, MCQ formatting, MCQ style, stem writing and option writing.

Concerning option writing, the most important ones for quality evaluation are the following: "Keep choices homogeneous in content and grammatical structure" and "Keep choices independent; choices should not be overlapping".

Grammatical homogeneity can be verified on the syntactic representation of the options provided by a natural language (NL) parser. In the example of Section 1, all options are noun chunks. Semantic characterization of options can be based on different NL tools, each able to provide different semantic properties according to the resources they are based on.

To evaluate the quality of distractors, we compare them to the answer, both on syntactic and semantic features. We do not want to learn a decision that would state on distractor homogeneity or not because homogeneity is more a question of degree than a binary decision. Thus, we formulate homogeneity evaluation as a ranking problem: the most homogeneous distractors should be classified in the first ranks. The candidates to rank, except for distractors, are selected according to syntactic homogeneity criteria, which proved to be a valid selection criteria in the corpus study of [START_REF] Pho | Multiple Choice Question Corpus Analysis for Distractor Characterization[END_REF].

Semantic homogeneity

Semantic homogeneity states that options share common semantic characteristics. In the example of Section 1, all options are Asian countries. We will define several notions close to semantic homogeneity by considering a knowledge organization in the form of a hierarchical graph (Figure 1) carrying typed concepts referred by the terms of the options and semantic relations.

The definition of semantic relatedness by [START_REF] Ponzetto | Knowledge derived from wikipedia for computing semantic relatedness[END_REF] is the following: "Semantic relatedness indicates how much two concepts are semantically distant in a network or taxonomy by using all relations between them (i.e. hyponymic/hypernymic4 , antonymic 5 , meronymic6 and any kind of functional relations including ismade-of, is-an-attribute-of, etc.)". Thus, semantic relatedness holds between two concepts when there exists a path between them, and the degree of relatedness is dependent on the path length and the types of relations. In Figure 1, all concepts are semantically related.

We define semantic similarity as a particular case of semantic relatedness: two terms are similar if they share the same meaning (i.e. synonyms) or a partial meaning, i.e. the concepts to which they refer are linked by a purely ascending or descending chain of is-a or meronymy relations, as "Belarus" and "Europe" in Figure 1.

We define semantic specificity as a particular case of semantic relatedness between two concepts that share a common ancestor, as "France" and "Belarus" in Figure 1.

We define semantic homogeneity as a particular case of semantic relatedness: it considers all relations between compared concepts. Moreover, semantic homogeneity excludes the notion of semantic similarity: two options cannot be similar. Finally, a better homogeneity is reached if semantic specificity is respected.

To estimate semantic homogeneity between a distractor and the answer, we compute several semantic relatedness scores. These measures are based on different criteria: measures based on hierarchical semantic representations of concepts, and data driven measures based on contextual relatedness, i.e. the principle stating that terms with similar contexts in a corpus are likely to be semantically related. Hierarchical representations allow us to take into account explicit semantic relations to compare two concepts. However, the resources (DBpedia, WordNet) corresponding to these representations are often limited in their cov-erage (proportion of options present in the resources). Measures based on contextual relatedness have a broader coverage, but the nature of semantic relations is unknown.

In the following sections, we present each of these measures.

Identity of named entity types

A named entity (NE) is an particular expression referred by a semantic class called NE type. Two options annotated with the same NE type are semantically specific, if they do not refer to a same concept. In order to measure their specificity, we consider 3 large categories: location, organization and person. For such types, NE recognizer are based on surface criteria and gazetteers and do not require a semantic knowledge base.

To compare the NE type of two terms, we use the following measure:

same N E type(t 1 , t 2 ) = 1 if N E(t 1 ) = N E(t 2 ) ∧ t 1 is a NE ∧ t 2 is a NE 0 else (1)
where t 1 and t 2 are two terms and N E(t) is the NE type of the term t.

Similarity of semantic types provided by DBpedia

In addition to comparing general NE types, we compare semantic types at a more fine-grained and hierarchical level, which allow us to verify more precisely semantic specificity. However, while NE types can be recognized independently of a resource, specific types have to be recognized for concepts belonging to a hierarchical taxonomy. We chose DBpedia7 , a hierarchical resource built from Wikipedia articles. DBpedia entities are associated with semantic types which represent classes of the DBpedia ontology, organized in a taxonomy 8 .

To compute semantic homogeneity between two terms t 1 and t 2 based on their DBpedia type and position in the taxonomy, we use Wu and Palmer's measure [START_REF] Wu | Verbs semantics and lexical selection[END_REF], wup(t 1 , t 2 ), which is based on is based on the shortest path between two concepts weighted by their depth in the taxonomy.

wup(t 1 , t 2 ) = 2 × depth(lcs) depth(type(t 1 )) + depth(type(t 2 )) (2)
where type(t) is the DBpedia type of the term t, depth(u) is the depth of a type u in the taxonomy and lcs(type(t 1 ), type(t 2 )) is the least common subsumer (in terms of path length in the taxonomy) between type(t 1 ) and type(t 2 ). Thus, two deep concepts with a common parent get a higher score than two less deep concepts with a common parent.

Relatedness measures based on WordNet

To measure semantic homogeneity for all kinds of options and in particular non NE ones, we use measures defined on WordNet9 , a lexical network that clusters synonym words in synsets linked by semantic relations. To each synset is associated a gloss, i.e. a definition in NL. WordNet also contains named entities for a few kinds of entities (large cities, countries, continents...). We use the four measures selected by [START_REF] Mitkov | Semantic similarity of distractors in multiple-choice tests: extrinsic evaluation[END_REF]: the extended gloss overlap measure based on textual similarity between the glosses of two concepts; Leacock and Chodorow's measure based on the shortest path between concepts; and Jiang and Conrath's and Lin's measures, both based on information content [START_REF] Resnik | Using information content to evaluate semantic similarity in a taxonomy[END_REF]. Terms can have multiple senses, so they can be associated with multiple synsets. To compute semantic relatedness between two terms, we compute the measures on all pairs of synsets associated with the terms and we keep the maximal score.

Comparison of links of Wikipedia articles

We also considered measures based on contextual relatedness. A possible contextual representation of a term is the sets of incoming and outgoing links associated with a page in Wikipedia. We consider pages whose title corresponds to an option. The incoming and outgoing "manually created" links represent associated concepts. The tool Wikipedia Miner [START_REF] Milne | An open-source toolkit for mining Wikipedia[END_REF] computes a score learned on these links from Wikipedia dumps.

Explicit Semantic Analysis

Another contextual representation of terms is their distribution through documents in a corpus. Two terms having close distributions in the same documents are likely to be semantically related. In order to compare the distributions of a candidate and the answer, we computed a measure based on Explicit Semantic Analysis (ESA) [START_REF] Gabrilovich | Computing Semantic Relatedness Using Wikipedia-based Explicit Semantic Analysis[END_REF]. ESA is based on a vector representation of texts in which the dimensions are the weights of the text in each document belonging to a corpus. A word is represented by a vector containing weights on its frequency in each document and a text is represented by the centroid of the weighted vectors representing each word of the text. The relatedness score of two texts is the cosine of the vectors representing these texts. In our case, the document corpus is Wikipedia. To compute the measure based on ESA, we use the tool ESAlib10 .

Evaluation of distractor quality

In order to evaluate the quality of distractors, we merge existing distractors with non-distractors (terms which have not been manually selected to be distractors for the MCQ). Our purpose is to learn an assessment model able to rank distractors above non-distractors, as they should be more homogeneous to the answer than the non-distractors. None of the proposed measures directly estimates semantic similarity but we made the hypothesis that a high score of semantic relatedness can represent semantic similarity, which should be learned by our model. MCQs that we process are associated with a document from which stems have been conceived. Non-distractors are selected in this document according to syntactic homogeneity. A first step involves annotation of the options and the non-distractors.

Document and options annotation

To extract non-distractors and compute the different measures, candidates and answers have to be annotated by syntactic and semantic information, which is better realized if these text excerpts are analyzed in the reference document. Thus, we perform four annotations of the document, in the following order:

1. syntactic parsing with the Stanford Parser [START_REF] Klein | Accurate unlexicalized parsing[END_REF]; 2. NE annotation with the Stanford Named Entity Recognition tool [START_REF] Finkel | Incorporating non-local information into information extraction systems by gibbs sampling[END_REF]; 3. specific type annotation, to find entities which are related to a DBpedia entity (and, by extension, a Wikipedia article), with DBpedia Spotlight [START_REF] Daiber | Improving efficiency and accuracy in multilingual entity extraction[END_REF]. This tool associates DBpedia entities with corresponding entities of the document and disambiguates these entities if required. However, some terms (chunks and/or NEs) are not annotated by DBpedia Spotlight. We associate these terms with all DBpedia entities whose title corresponds to them, so without disambiguation; 4. WordNet concept annotation, aiming at associating terms with a WordNet concept. This annotation is performed on chunks and/or NEs, i.e. single or multiword expressions, as following:

if the expression appears in WordNet, the expression is associated with its corresponding concept; if the expression does not appear in WordNet and is not a NE, the expression is associated with the concept corresponding to its syntactic head (for instance, the expression "the little cat" is associated with the WordNet concept "cat").

Annotations of the options are extracted from their occurrences in the document. If an option does not appear in the document, its annotations are performed similarly to the document.

Non-distractor extraction and annotation

Since MCQs are related to a reference document, non-distractors are extracted from this document. All non-distractors are syntactically homogeneous to the answer. If the answer is a NE, the non-distractors are the NEs of the reference document, as [START_REF] Pho | Multiple Choice Question Corpus Analysis for Distractor Characterization[END_REF] showed that distractors generally have the same NE type as 1. Characteristics of the corpora the answer. Nevertheless, in order to take metonymy into account, we keep all non-distractors with a NE type, regardless of the type. If the answer is a chunk and not a NE, the non-distractors are the chunks of the reference document with the same syntactic type as the answer. The chunks are selected from the parse tree of the document sentences, with Tregex [START_REF] Levy | Tregex and Tsurgeon: tools for querying and manipulating tree data structures[END_REF], a tool that selects nodes in parse trees from patterns. We associate non-distractors with their NE type, DBpedia entity and WordNet concept annotated in the document. A last filtering consists of removing non-distractors similar to an option, in order to avoid overlaps: two elements are considered similar if they are associated with the same DBpedia entity or if they refer to the same synset in WordNet.

Semantic ranking

Ranking of the candidates (distractors and non-distractors) according to the different criteria of semantic homogeneity is performed by the tool SVMRank11 , an automatic ranker based on a SVM model, that compares couples of distractorsnon-distractors of a same MCQ and learns the weights of the criteria such as for each couple of distractor-non-distractor (d, nd), svm(d) > svm(nd).

Experiments

Data sets

In order to evaluate our method, we use an English corpus of MCQs (corpus allMCQ, 735 MCQs) extracted from different sources: machine reading system tests provided by QA4MRE 12 (set qa4mre) and several websites of English language learning (set englishEval). We assume that these MCQs tend to be wellwritten. From this corpus, we established two sub-corpora: the first is composed of MCQs which answers are NEs (corpus mcqNE, 14 % of allMCQ), and the second is composed of MCQs which answers are chunks and not NE (corpus mcqNonNE, 20 % of allMCQ).

The questions that we process (chunks and NEs) compose more than one third of the original corpus which shows that these types of questions are frequently asked in tests. Learning was performed separately on each sub-corpus.

Evaluation methodology

We consider that distractors are semantically closer to the answer than nondistractors and should thus have a higher rank. In order to evaluate candidate ranking, we compute the average precision (Equation ( 3)) and recall (Equation ( 4)), as well as the f-measure (Equation ( 5)).

AP = nbQ i P i,nbD nbQ (3) AR = nbQ i R i,nbD nbQ (4)
F = 2 × AP × AR AP + AR (5)
where nbQ is the number of MCQs in the corpus, nbD the number of distractors of the evaluated MCQ, and P i,nbD and R i,nbD are the precision (Equation [START_REF] Karamanis | Generating multiple-choice test items from medical text: A pilot study[END_REF]) and recall (Equation ( 7)) of MCQ i.

P i,nbD = #D of rank ≤ nbD #C of rank ≤ nbD (6) R i,nbD = #D of rank ≤ nbD nbD (7)
where D means distractors and C means candidates. Precision and recall are computed for each semantic relatedness measure, as well as for the ranking model. We evaluate the ranking by 7-fold cross-validation.

Results

Table 2 shows that the ranking model gives higher balance between recall and precision than individual measures, regardless of the corpus. In particular it gives a higher precision than other measures and better results than WordNet-based measures, used by [START_REF] Mitkov | Semantic similarity of distractors in multiple-choice tests: extrinsic evaluation[END_REF].

Some measures give a higher recall than the ranking model. We distinguish two cases: the first concerns (NE and specific) type-based measures which are more efficient for filtering candidates than selecting distractors. The second case concerns measures whose resource coverage is low (WordNet in mcqNE and Wikipedia in mcqNonNE).

The results are overall lower in the mcqNonNE corpus. The main reason is that non NE candidates and answers are associated with less semantic information than NE, particularly on semantic types.

In the corpus mcqNE, most cases where non-distractors are better ranked than distractors are due to the fact that distractors and answers are not typed by a very specific (DBpedia) type. The remaining non-distractors are relevant enough to be distractors or are similar to the answer, so cannot be distractors.

The majority of non-distractors of the corpus mcqNonNE which are better ranked than distractors are clearly non-distractors but some measures (particularly WordNet-based) consider that these non-distractors are more semantically related than distractors. Among the remaining non-distractors, some of them are not semantically related to the answers in the current context (reference document) or they are relevant enough to replace distractors.

Related work

Automatic distractor selection is usually based on similarity measures between the candidates and the answer and is evaluated by learners or teachers.

Existing work on automatic distractor selection is based either on hierarchical domain-specific resources (WordNet, UMLS) [START_REF] Karamanis | Generating multiple-choice test items from medical text: A pilot study[END_REF][START_REF] Mitkov | Semantic similarity of distractors in multiple-choice tests: extrinsic evaluation[END_REF] and/or document corpora [START_REF] Lee | Automatic generation of cloze items for prepositions[END_REF][START_REF] Mitkov | Semantic similarity of distractors in multiple-choice tests: extrinsic evaluation[END_REF]. From these resources, candidates are selected according to common syntactic and semantic characteristics with the answer: common syntactic type [START_REF] Karamanis | Generating multiple-choice test items from medical text: A pilot study[END_REF][START_REF] Lee | Automatic generation of cloze items for prepositions[END_REF][START_REF] Mitkov | Semantic similarity of distractors in multiple-choice tests: extrinsic evaluation[END_REF], common semantic classes [START_REF] Karamanis | Generating multiple-choice test items from medical text: A pilot study[END_REF][START_REF] Mitkov | Semantic similarity of distractors in multiple-choice tests: extrinsic evaluation[END_REF] or terms sharing the same head as the answer [START_REF] Mitkov | Semantic similarity of distractors in multiple-choice tests: extrinsic evaluation[END_REF]. Then, distractors are selected from candidates according to different measures: context-based [START_REF] Karamanis | Generating multiple-choice test items from medical text: A pilot study[END_REF][START_REF] Lee | Automatic generation of cloze items for prepositions[END_REF] or a strategy based on these first measures, WordNet-based and phonetic-based measures [START_REF] Mitkov | Semantic similarity of distractors in multiple-choice tests: extrinsic evaluation[END_REF]. Evaluation of distractors is performed by learners (through psychometric tests) [START_REF] Lee | Automatic generation of cloze items for prepositions[END_REF][START_REF] Mitkov | Semantic similarity of distractors in multiple-choice tests: extrinsic evaluation[END_REF] or judgment of domain experts [START_REF] Karamanis | Generating multiple-choice test items from medical text: A pilot study[END_REF], but none of this work evaluated distractors on a reference corpus. Moreover, related work is dedicated to a specific domain (linguistics, medicine, preposition learning), whereas our work is not specific to a domain. Related work is also limited by the syntactic types of answers (words, noun chunks) whereas our work covers all kinds of chunks (noun and verb phrases) and NEs.

Conclusion

In this paper, we proposed a method to automatically evaluate the quality of distractors according to criteria relative to syntactic and semantic homogeneity. Results outperform the state-of-the-art methods for automatic distractor selection, and are better on NE than other kinds of chunks. Measures based on hierarchical semantic resources allow us to filter candidates according to properties like types and semantic relations. Measures based on contextual relatedness allow us to refine distractor recognition.

These criteria are relevant but are not sufficient to automatically recognize distractors: considering other information like stems and the context of the options, we would recognize distractors more precisely. Moreover, in future work, we will adapt our approach to all kinds of answers (phrases, clauses and sentences). We will also evaluate distractor quality a posteriori, from scores obtained by learners answering to MCQs.

Fig. 1 .

 1 Fig. 1. Semantic characterization of pairs of nodes

Table 2 .

 2 Results of semantic relatedness methods

		mcqNE		mcqNonNE
		R P	F	R P	F
	NE similarity	0.83 0.26 0.40
	DBpedia type similarity 0.70 0.34 0.46 0.94 0.14 0.24
	Extended gloss overlap 0.67 0.25 0.36 0.37 0.23 0.28
	Leacock & Chodorow	0.73 0.27 0.39 0.42 0.22 0.29
	Jiang & Conrath	0.83 0.23 0.36 0.40 0.18 0.25
	Lin	0.84 0.23 0.36 0.40 0.18 0.25
	Wikipedia link similarity 0.41 0.32 0.36 0.76 0.22 0.34
	ESA	0.40 0.34 0.37 0.35 0.24 0.28
	Combination	0.48 0.46 0.47 0.39 0.36 0.37

Two concepts of which the first has a more specific/general sense than the second

Two concepts of which their senses are opposite

Two concepts of which the first is a part or a member of the second

http://dbpedia.org/About

http://mappings.dbpedia.org/server/ontology/classes/

http://wordnet.princeton.edu/

http://ticcky.github.io/esalib/

http://www.cs.cornell.edu/people/tj/svm light/svm rank.html


M Le Treust

S Lasaulce

A Repeated Game Formulation of Energy-Efficient Decentralized Power Control

Keywords: Cognitive radio, energy-efficiency, Folk theorem, Nash equilibrium, power control games, repeated games. I

Decentralized multiple access channels where each transmitter wants to selfishly maximize his transmission energy-efficiency are considered. Transmitters are assumed to choose freely their power control policy and interact (through multiuser interference) several times. It is shown that the corresponding conflict of interest can have a predictable outcome, namely a finitely or discounted repeated game equilibrium. Remarkably, it is shown that this equilibrium is Pareto-efficient under reasonable sufficient conditions and the corresponding decentralized power control policies can be implemented under realistic information assumptions: only individual channel state information and a public signal are required to implement the equilibrium strategies. Explicit equilibrium conditions are derived in terms of minimum number of game stages or maximum discount factor. Both analytical and simulation results are provided to compare the performance of the proposed power control policies with those already existing and exploiting the same information assumptions namely, those derived for the one-shot and Stackelberg games.

authors analyze the problem of distributed power control (PC) in flat fading multiple access channels (MACs).

The problem is formulated as a non-cooperative game where the players are the transmitters, the action of a given player is her/his/its transmit power ("his" is chosen in this paper), and his payoff/reward/utility function is the energy-efficiency of his communication with the receiver. The results reported in [START_REF] Shah | Power Control for Wireless Data based on Utility and Pricing[END_REF] [START_REF] Goodman | Power control for wireless data[END_REF] have been extended to the case of multi-carrier systems in [START_REF] Meshkati | A game-theoretic approach to energy-efficient power control in multi-carrier CDMA systems[END_REF]. Unfortunately, as shown in [START_REF] Goodman | Power control for wireless data[END_REF], Nash equilibria (NE) resulting from the one-shot game formulation of the energy-efficient power control problem are generally inefficient. This is one of the reasons why some authors proposed to apply other game-theoretic concepts to improve efficiency of the network equilibrium: [START_REF] Saraydar | Efficient power control via pricing in wireless data networks[END_REF] proposed a pricing mechanism and [START_REF] Lasaulce | Introducing hierarchy in energy games[END_REF] proposed to introduce some hierarchy in the network by considering a Stackelberg game [START_REF] Stackelberg | Marketform und Gleichgewicht[END_REF] or using successive interference cancellation at the receiver. The solution of [START_REF] Saraydar | Efficient power control via pricing in wireless data networks[END_REF] has the advantage to be Pareto-optimal (PO) but requires global channel state information (CSI) at the transmitters and equilibrium uniqueness is not proven analytically. On the other hand, the solution of [START_REF] Lasaulce | Introducing hierarchy in energy games[END_REF] is not PO but only requires individual CSI and uniqueness is guaranteed.

All the cited and related works on energy-efficient PC ([3][4] [START_REF] Lasaulce | Introducing hierarchy in energy games[END_REF], etc) have at least one common point: time is divided into windows or blocks over which the channel is assumed to be constant and transmit power levels can be updated only once within a given block. The corresponding framework is the one of static or one-shot games which is to say, transmitters play independently from block to block and maximize their instantaneous utility for each block. In this paper, we consider a more general situation: transmitters are allowed to update their power levels several times within a block; the corresponding PC type could be called decentralized fast PC (DFPC), generalizing the more conventional decentralized slow PC (DSPC) for which the power can be updated only once per block. Both in the DFPC and DSPC cases, we want to take into account the fact that players (namely the transmitters) interact several times within a block or/and from block to block, which introduces new types of behaviors (cooperation, punishment, etc) with respect to the one-shot game. The framework considered here is the one of dynamic games. More specifically, we analyze a special case of dynamic games, which is the case of repeated games (RG). In standard repeated games [START_REF] Aumann | Essays in game theory and mathematical economics in honor of Oskar Morgenstern[END_REF][8] [START_REF] Mertens | Repeated Games, Parts A,B,C[END_REF] the same game is played a finite or infinite number of times and players are interested in optimizing a certain performance metric, resulting from averaging their utility over the whole duration of the game. In contrast with iterative or learning techniques that are based on mild information assumptions and different behavior assumptions (transmitters can be modeled by automata), RG generally require more demanding information and behavior assumptions. Also, RG aim at optimizing an averaged utility and reaching points July 29, 2010 DRAFT more efficient than the one-shot game NE. Two important models of RG are considered: the finitely repeated game (FRG) [START_REF] Benoit | Finitely Repeated Games[END_REF] and discounted repeated game (DRG) [START_REF] Fudenberg | The folk theorem in repeated games with discounting or with incomplete information[END_REF]. A priori, the FRG seems to be more suited to DFPC since the number of times players interact is finite and can be known (e.g., the number of training symbols in a block) whereas the DRG seems to be more suited to DSPC with a uncertain number of blocks over which players interact. To the authors' knowledge, there is only a small fraction of papers dedicated to repeated games in the wireless literature. As far as the present paper is concerned, the most relevant contributions available are [START_REF] Etkin | Spectrum Sharing for Unlicensed Bands[END_REF][13] [START_REF] Wu | Repeated Open Spectrum Sharing Game with Cheat-Proof Strategies[END_REF]. With respect to these works, our contributions are as follows. The work reported in this paper is the first to apply the concept of RG to energy-efficient PC (the existing works consider Shannon transmission rates or similar utility functions). A second important feature of the present analysis is that only individual CSI and signal-to-interference plus noise ratio (SINR) are needed to implement the proposed PC scheme, which is not the case in [START_REF] Etkin | Spectrum Sharing for Unlicensed Bands[END_REF][13] [START_REF] Wu | Repeated Open Spectrum Sharing Game with Cheat-Proof Strategies[END_REF]. Third, two models of RG are considered and explicit equilibrium conditions on the number of game stages (for the FRG) and discounted factor (for the DRG) are provided and discussed, which is not made in the existing literature. At last but not least, the PC policy we propose is compared in a fair manner with existing game-theoretic PC policies both analytically and by simulations and shown to be the most efficient one (in the sense of Pareto). For this purpose, several works from the game theory literature, and not used yet by the wireless community, are exploited.

This paper is structured as follows. In Sec. II-A the assumed signal model is described. This is followed (Sec. II-B) by a short review of the static/one-shot non-cooperative and Stackelberg PC games. In Sec.

III a rigorous RG formulation of the PC problem is provided and information assumptions necessary to implement the equilibrium strategies of Sec. IV-B are given. The proposed equilibria (finitely and discounted repeated games equilibria) and their properties are analyzed in Sec. IV. The results derived are illustrated by simulations in Sec. V, which is followed by the conclusion (Sec. VI).

II. SYSTEM MODEL

A. Signal model

We consider a decentralized MAC with a finite number of transmitters, which is denoted by K. The network is said to be decentralized in the sense that the receiver (e.g., a base station) does not dictate to the transmitters (e.g., mobile stations) their PC policy. Rather, all the transmitters choose their policy by themselves and want to selfishly maximize their energy-efficiency; in particular, they can ignore some July 29, 2010 DRAFT specified centralized policies. We assume that the users transmit their data over quasi-static channels and at the same time and frequency band. Note that a block is defined as a sequence of M consecutive symbols which comprises a training sequence that is, a certain number of consecutive symbols used to estimate the channel (or other related quantities) associated with a given block. A block has therefore a duration less than the channel coherence time. The signal model used corresponds to the information-theoretic channel model used for studying MAC [START_REF] Wyner | Recent results in Shannon theory[END_REF] [START_REF] Cover | Some advances in broadcast channels[END_REF]; see e.g., [START_REF] Belmega | Power allocation games for MIMO multiple access channels with coordination[END_REF] for more comments on the multiple access technique involved. What matters is that this model is both simple to be presented and captures the different aspects of the problem (the SINR structure in particular) and can be readily applied to speficic systems such as CDMA systems [START_REF] Goodman | Power control for wireless data[END_REF][5] or multi-carrier CDMA systems [START_REF] Meshkati | A game-theoretic approach to energy-efficient power control in multi-carrier CDMA systems[END_REF]. The equivalent baseband signal received by the base station can be written as

y(n) = K i=1 g i (n)x i (n) + z(n) (1)
where i ∈ K, K = {1, ..., K}, x i (n) represents the symbol transmitted by transmitter i at time n,

E|x i | 2 = p i ,
the noise z is assumed to be distributed according to a zero-mean Gaussian random variable with variance σ 2 and each channel gain g i varies over time but is assumed to be constant over each block. For each transmitter i, the channel gain modulus is assumed to lie in a compact set

|g i | 2 ∈ η min i , η max i .
This assumption is both practical (for example, such limitations can model the finite receiver sensitivity and the existence of a minimum distance between the transmitter and receiver) and important to guarantee the existence of the proposed equilibria (Sec. IV). At last, the receiver is assumed to implement single-user decoding.

B. Review of the one-shot power control game

Here, we review a few key results from [START_REF] Goodman | Power control for wireless data[END_REF] concerning the static non-cooperative PC game. In order to define the static PC game some notations need to be introduced. We denote by R i the transmission information rate (in bps) for user i and f an efficiency function representing the block success rate, which is assumed to be sigmoidal and identical for all the users; the sigmoidness assumption is a reasonable assumption, which is well justified in [18][19]. Recently, [START_REF] Belmega | An information-theoretic look at MIMO energy-efficient communications[END_REF] has shown that this assumption is also justified from an information-theoretic standpoint. At a given instant, the SINR at receiver i ∈ K writes as:

SINR i = p i |g i | 2 j =i p j |g j | 2 + σ 2 (2)
where p i is the power level for transmitter i. With these notations, the static PC game, called G, is defined in its normal form as follows.

u i (p 1 , ..., p K ) = R i f (SINR i ) p i [bit/J]. (3)
In this game with complete information (G is known to every player) and rational players (every player does the best for himself and knows the others do so and so on), an important game solution concept is the NE (i.e., a point from which no player has interest in unilaterally deviating). When it exists, the non-saturated NE of this game can by obtained by setting ∂u i ∂p i to zero, which gives an equivalent condition on the SINR: the best SINR in terms of energy-efficiency for transmitter i has to be a solution of xf (x) -f (x) = 0 (this solution is independent of the player index since a common efficiency function is assumed, see [START_REF] Meshkati | An Energy-Efficient Approach to Power Control and Receiver Design in Wireless Data Networks[END_REF] for more details). This leads to:

∀i ∈ {1, ..., K}, p * i = σ 2 |g i | 2 β * 1 -(K -1)β * (4)
where β * is the unique solution of the equation xf (x) -f (x) = 0. By using the term "non-saturated NE"

we mean that the maximum transmit power for each user, denoted by P max i , is assumed to be sufficiently high not to be reached at the equilibrium i.e., each user maximizes his energy-efficiency for a value less than P max i (see [START_REF] Lasaulce | Introducing hierarchy in energy games[END_REF] for more details). An important property of the NE given by ( 4) is that transmitters only need to know their individual channel gain |g i | to play their equilibrium strategy. One of the interesting results of this paper is that it is possible to obtain a more efficient equilibrium point by repeating the game G while keeping this key property.

C. Review of the Stackelberg power control game

Here we review a few key results from [START_REF] Lasaulce | Introducing hierarchy in energy games[END_REF]. The corresponding results will be used in Sec. IV and V where the performance of the proposed RG equilibrium is compared with the one of the Stackelberg equilibrium (SE). The main difference between the one-shot game [START_REF] Goodman | Power control for wireless data[END_REF] and the Stackelberg game is that in the latter, one of the transmitters is the leader of the game. The other transmitters are assumed to be able to observe the actions of the leader and react to them accordingly; these transmitters are called the followers. Note that the leader knows that his actions are observed and therefore anticipates the reaction of the followers. In [START_REF] Lasaulce | Introducing hierarchy in energy games[END_REF], it is shown that the SE power profile Pareto-dominates the one-shot NE power profile. The power played by transmitter i ∈ K at the SE when he is the game leader (L) is given by: July 29, 2010 DRAFT

p L i = σ 2 |g i | 2 γ * (1+β * ) 1-(K-1)γ * β * -(K-2)β * where γ * is the unique solution of x 1 -(K-1)β * 1-(K-2)β * x f (x) -f (x) = 0, and the corresponding utility is u L i = |g i | 2 σ 2 1-(K-1)γ * β * -(K-2)β * γ * (1+β * )
f (γ * ). On the other hand, the power played by transmitter i ∈ K at the SE when he is one of the game followers (F) and corresponding utility are given by p

F i = σ 2 |g i | 2 β * (1+γ * ) 1-(K-1)γ * β * -(K-2)β * and u F i = |g i | 2 σ 2 1-(K-1)γ * β * -(K-2)β * β * (1+γ * ) f (β * ).

III. MOVING FROM STATIC TO REPEATED PC GAMES

A. Strategic information assumptions

First, we want to show that, in the non-saturated regime (as defined in the preceding section), the energyefficient one-shot PC game has a very interesting structure in terms of CSI. This structure, which is analyzed just below, has two consequences. The first consequence is that only individual CSI is required at the transmitters that is, only |g i | needs to be known by transmitter i. In the existing literature

([2][3][5], etc)
this game feature is observed once the equilibrium solution has been determined. It turns out that it is due to the structure of the utility functions of the one-shot game and not only to the specific solutions analyzed in the existing literature. This can therefore be checked before deriving the equilibrium solution.

A simple way of proving this statement is to consider a game where utilities are normalized: u i (p 1 ,...,p K )

|g i | 2 = R i f p i |g i | 2 j =i p j |g j | 2 +σ 2 p i |g i | 2
. By making the change of variables a i = p i |g i | 2 the normalized utility function becomes:

ûi (a 1 , ..., a K ) = R i f a i j =i a j +σ 2 a i
. It is seen from the normalized utilities that channel gains play only a role when players de-normalize their actions by computing p i = a i |g i | 2 , which shows that only individual CSI is needed to play the game. The second consequence of the structure of ûi is that the repeated versions of the one-shot game are easier to be analyzed. Indeed, the normalized utilities ûi depend on time only through the action profile a = (a 1 , ..., a K ) and not through |g i |. This means that the PC stochastic repeated game can be analyzed as the repeated version of a (normalized) static game; this is why, in the sequel, we will not use a time index for u i . In addition to the individual CSI assumption, we also assume that every player can observe a public signal. More specifically, we assume that every player knows at each stage of the game the signal

ω = σ 2 + K i=1 |g i | 2 p i . (5)
By noticing that ∀i ∈ K, p i |g i | 2 × SINR i +1 SINR i = ω we see that each transmitter can construct the public signal from the sole knowledge of his action, individual channel gain, and individual SINR. One of the main July 29, 2010 DRAFT results of this paper is that assuming the two mentioned information assumptions allows one to implement a cooperation plan between the transmitters corresponding to an efficient equilibrium. This is possible with the repeated game formulation of the problem, which is given below.

B. Repeated game formulation of the power control problem

In the static PC game, each transmitter observes the channel gain associated with the current block i.e., |g i | and updates his power level according to (4) in order to maximize his instantaneous utility. In repeated games, players want to maximize their averaged utility. To define the latter quantity we first need to define several notions namely a game stage, the game history, and the strategy of a player. Game stages correspond to instants at which players can choose their actions. To be concrete, in the case of DSPC, game stages coincide with blocks whereas in the case of DFPC, game stages coincide with sub-blocks (comprising one or several symbols). The proposed framework is the one of repeated games with a public signal (see e.g., [22][23]) in which the public signal (namely ( 5)) is a deterministic function of the played actions.

We denote by

Ω = σ 2 , σ 2 + K i=1 η max i P max i
the interval the public signal lies in. The pair of vectors (ω t , p i,t ) = (ω(1), ..., ω(t -1), p i (1), ..., p i (t -1)) is called the history of the game for transmitter i at time t and lies in the set

H t = Ω t-1 × P t-1 i
. This is precisely the history h t = ω t , p i,t which is assumed to be known by the transmitters before playing at stage t. With these notations, a pure strategy of a transmitter in the repeated game can be defined properly.

Definition 2 (Players' strategies in the RG): A pure strategy τ i for player i ∈ K is a sequence of causal functions (τ i,t ) t≥1 with τ i,t :

H t → [0, P max i ] h t → p i (t). (6)
The strategy of player i, which is a sequence of functions, will be denoted by τ i (removing the game stage index in ( 6) is a common way to refer to a player's strategy). The vector of strategies τ = (τ 1 , ..., τ K ) will be referred to a joint strategy and lie in the set T . A joint strategy τ induces in a natural way a unique action plan (p(t)) t≥1 . To each profile of powers p(t) = (p 1 (t), . . . , p K (t)) corresponds a certain instantaneous utility u i (p(t)) for player i. In our setup, each player does not only care about what he gets at a given stage but what he gets over the whole duration of the game. This is why we consider utility functions resulting from averaging over the instantaneous utility. More precisely, we consider two utility functions which correspond to the two important models of repeated games under investigation namely the FRG and DRG.

July 29, 2010 DRAFT Definition 3 (Players' utilities in the RG): Let τ = (τ 1 , ..., τ K ) be a joint strategy. The utility for player i ∈ K is defined by:

v T i (τ ) = 1 T T t=1 u i (p(t)) in the FRG v λ i (τ ) = ∞ t=1 λ(1 -λ) t-1 u i (p(t)) in the DRG (7)
where p(t) is the power profile of the action plan induced by the joint strategy τ , T ≥ 1 is the number of game stages in the FRG, and 0 < λ < 1 is a parameter of the DRG called the discount factor and is known to every player (since the game is with complete information).

In this paper, we consider two models of RG because these are complementary in a certain sense. In scenarios where the duration over which the transmitters interact is known (this is typically the case when transmit power levels can only be updated during the training phase of the block) or/and transmitters value the different instantaneous utilities uniformly, the FRG seems to be more suited. In the current available wireless literature on the problem under investigation the DRG is used as follows: the discount factor is used in [START_REF] Etkin | Spectrum Sharing for Unlicensed Bands[END_REF] as a way of accounting for the delay sensitivity of the network; the discount factor is used in [START_REF] Wu | Repeated Open Spectrum Sharing Game with Cheat-Proof Strategies[END_REF] to let the transmitters the possibility to value short-term and long-term gains differently. Interestingly, [START_REF] Sorin | Repeated Games with Complete Information[END_REF][21] offer another interpretation of this model. Indeed, the author sees the DRG as an FRG where T would be unknown to the players and considered as an integer-valued random variable, finite almost surely, whose law is known by the players. Otherwise said, λ can be seen as the stopping probability at each game stage: the probability that the game stops at stage t is thus λ(1 -λ) t-1 . The function v λ i would correspond to an expected utility given the law of T . This shows that the discount factor is also useful to study wireless games where a player enters/leaves the game. We would also like to mention that it can also model a heterogeneous DRG where players have different discount factors, in which case λ represents min i λ i (as pointed out in [START_REF] Shapley | Stochastic Games[END_REF]). In practice, such a parameter can be acquired through a public signal from the receiver. Definition 4 (Equilibrium strategies in the RG): A joint strategy τ supports an equilibrium of the RG defined by (K,

{T i } i∈K , {v i } i∈K ) if ∀i ∈ K, ∀τ i ∈ T i , v i (τ ) ≥ v i (τ i , τ -i ) where v i equals v T i or v λ i
, -i is the standard notation to refer to the set K\{i}; here τ -i = (τ 1 , ..., τ i-1 , τ i+1 , ..., τ K ).

An important issue is precisely to characterize the set of possible equilibrium utilities in the RG. When the game is with complete information and perfect monitoring, there is a theorem which provides the corresponding characterization from the sole knowledge of the possible utilities in the static game. This theorem is called the "Folk theorem" (see e.g., [START_REF] Aumann | Essays in game theory and mathematical economics in honor of Oskar Morgenstern[END_REF] [START_REF] Sorin | Repeated Games with Complete Information[END_REF]). Recall that the game is said to be with perfect July 29, 2010 DRAFT monitoring when every player is able to observe at each stage the actions chosen by all the other players.

Whereas this knowledge can be acquired in certain scenarios where appropriate estimation and sensing mechanisms are implemented, one of our objectives is to show that some of these information assumptions can be relaxed by exploiting the specific structure of energy-efficient PC games. In the next section, we clearly make explicit the information assumptions needed to implement the proposed cooperation plan. This cooperation plan is built from a point of the feasible utility region of G and has been studied in [START_REF] Goodman | Network assisted power control for wireless data[END_REF] in the framework of centralized networks.

IV. EQUILIBRIUM ANALYSIS OF THE REPEATED PC GAME

Folk theorems aim at characterizing the set of equilibrium utilities of RG for different types of RG (finite/infinite/discounted RG), equilibria (NE, correlated equilibria, communication equilibria, etc), and information assumptions (complete/incomplete information, perfect/imperfect monitoring). In this paper, the objective is much more modest since we focus on a given equilibrium point and a specific game. One of the goals of this section is to show that the proposed equilibrium has several attractive properties for wireless II-B and the operating point for which a detailed study is required.

A. An interesting operating point of the game G By considering all the points (p 1 , ..., p K ) such that p i ∈ [0, P max i ], i ∈ K, one obtains the feasible utility region. We consider a subset of points of this region for which the power profiles (p 1 , ..., p K ) verify

p i |g i | 2 = p j |g j | 2 for all (i, j) ∈ K 2 .
The considered subset therefore consists of the solutions of the following system of equations:

∀(i, j) ∈ K 2 , ∂u i ∂p i (p) = 0 with p i |g i | 2 = p j |g j | 2 . ( 8
)
It turns out that, following the lines of the proof of SE uniqueness in [START_REF] Lasaulce | Introducing hierarchy in energy games[END_REF], it is easy to show that a sufficient condition for ensuring both existence and uniqueness of the solution to this system of equations is that July 29, 2010 DRAFT there exists

x 0 ∈]0, 1 K-1 [ such that f (x) f (x) -2(K-1) 1-(K-1)
x is strictly positive on ]0, x 0 [ and strictly negative on ]x 0 , 1 K-1 [. This condition is satisfied for the two following efficiency functions:

f (x) = (1 -e -x ) M [1] and f (x) = e -c
x [START_REF] Belmega | An information-theoretic look at MIMO energy-efficient communications[END_REF] with c = 2 R -1 (R is the transmission rate). If this condition should be found to be too restrictive it is always possible to directly derive a purely numerical condition, which can be translated into a condition on K, M (in the case of [START_REF] Shah | Power Control for Wireless Data based on Utility and Pricing[END_REF]), or R [START_REF] Belmega | An information-theoretic look at MIMO energy-efficient communications[END_REF]. Under the aforementioned condition, the unique solution of ( 8) can be checked to be:

∀i ∈ K, pi = σ 2 |g i | 2 γ 1 -(K -1)γ ( 9
)
where γ is the unique solution of

x[1-(K -1)•x]f (x)-f (x) = 0.
It is important here to distinguish between the equal-SINR condition imposed in ( 8) and the equal-SINR solution of the one-shot game (4). In the first case, the SINR has a special structure imposed by the condition (8) which is

SINR i = |g i | 2 p i σ 2 +(K-1)|g i | 2 p i .
Therefore, each transmitter is assumed to maximize a single-variable utility function u i (q i ) with

q i = p i × g i g 1 2 , g i g 2 2 , ..., g i g K 2 .
In the second case (one-shot NE), the solution is the solution of a K-unknown K-equation system and it happens that the solution has the equal-SINR property. The proposed operating point (OP), given by ( 9), is thus fair in the sense of the SINR since ∀i ∈ K, SINR i = γ. Another question to be answered is whether it is efficient. To answer this question we proceed in three steps. First, we provide sufficient conditions under which it is PO. Second, we provide some conditions under which it Paretodominates the SE point derived in [START_REF] Lasaulce | Introducing hierarchy in energy games[END_REF]. Third, we show that the proposed (OP) always Pareto-dominates the one-shot game NE point (4). Denote PO for Pareto-optimality.

Proposition 5 (Sufficient conditions for PO): Let U G be the achievable utility region for the game G. Let u max be an upper bound for the utilities of all transmitters. Let U C G be the complementary set of

U G in [0, u max ] K . If U G or U C
G is a convex region then the vector of utilities u(p) is Pareto-optimal. The proof is provided in App. A. Whereas it appears a difficult task to fully characterize the frontier of the achievable utility region for an arbitrary choice of sigmoidal functions f and therefore obtain the mildest condition for Pareto-optimality, many simulations have shown us that with usual efficiency functions [START_REF] Shah | Power Control for Wireless Data based on Utility and Pricing[END_REF][20],

the assumption "G or G C is convex" is reasonable but unfortunately not always valid. Of course, the fact that we do not provide a general proof does not mean that the proposed OP is not efficient under milder conditions. In all the simulations we have performed (not only those reported in Sec. V), the proposed OP was PO. The addressed technical problem is in fact a quite general problem encountered in game theory, especially in economics and some non-trivial refinements could be brought to our analysis.

July 29, 2010 DRAFT Proposition 6 (SE vs OP): Let p L i (resp. p F i ) the power of transmitter i at the equilibrium of the Stackelberg game of [START_REF] Lasaulce | Introducing hierarchy in energy games[END_REF] when i is the game leader (resp. one of the game followers). Denote by u L i , u F i the corresponding utilities. Then, we have:

(i) ∀i ∈ K, u i (p) ≥ u L i ; (ii) ∃K 0 , ∀K ≥ K 0 , ∀i ∈ K, u i (p) ≥ u F i .
The first statement of this proposition indicates that a transmitter always prefers to play the OP than being a leader of the hierarchical game of [START_REF] Lasaulce | Introducing hierarchy in energy games[END_REF]. The second statement shows that this is also true for the followers when the network reaches a certain size in terms of users. All the simulations we have performed have shown that K 0 equals 3.

Proposition 7 (NE vs OP): It is always true that ∀i ∈ K, u i (p) ≥ u i (p * ) where p * = (p * 1 , ..., p * K ). An important message conveyed by this proposition is that every transmitter always prefers the optimal strategy of the RG than the optimal strategy of the one-shot game. In the next section, we will see that the proposed OP corresponds to a possible agreement between the players, which allows one to obtain an equilibrium point in the FRG and DRG. Note that other points of G which are both feasible and individually rational could be used to build a cooperation plan. Designing other cooperation plans based on the repeated game formulation is a relevant extension of this paper.

B. Equilibrium strategies of the repeated PC games

First, we state two theorems providing equilibrium strategies that have the properties mentioned in Sec.

IV-A. These theorems correspond to the FRG and DRG respectively. Theorem 8 (Equilibrium strategies in the FRG): Let T 0 be some integer. Assume that the following condition is met: T ≥ T 0 with:

T 0 =     η max i f (β * ) β * -η min i f (γ)[1-(K-1)γ] γ η min i f (β * )[1-(K-1)β * ] β * - η max i f (β * ) β * ( j =i P max j η min j +σ 2 )     . ( 10
)
Then, for all i ∈ K, the following action plan is an NE of the T -stage FRG for any distribution for the channel gains and any (T, T 0 ) verifying (10) ∀t ≥ 1,:

τ i,t = p i if t ∈ {1, 2, . . . , T -T 0 } p * i if t ∈ {T -T 0 + 1, . . . , T } P max i if someone deviates from the above cooperative plan. (11)
July 29, 2010 DRAFT Theorem 9 (Equilibrium strategies in the DRG): Assume that the following condition is met:

λ ≤ η min i δ(β * , γ) η min i δ(β * , γ) + η max i [(K -1)f (β * ) -δ(β * , γ)] ( 12
)
where δ(β

* , γ) = 1-(K-1)γ γ f (γ) -1-(K-1)β * β * f (β * ).
Then, for all i ∈ K, the following action plan is a subgame perfect NE of the DRG for any distribution for the channel gains:

∀t ≥ 1, τ i,t = p i if all the other players play p-i p * i otherwise . ( 13
)
For the proofs see App. D. Here, we restrict our attention to interpreting these theorems.

Comment 1 (Equilibrium conditions). Before starting the game, the players agree on a certain cooperation/punishment plan. Each transmitter i ∈ K always transmits at p i if no deviation is detected and plays a punishment level otherwise (P max i or p * i depending on the RG under consideration). The proposed strategies support an equilibrium if the gain brought by deviating is less than the expected loss induced by the punishment procedure applied by the other transmitters. To make sure that this effectively occurs, the game must be sufficiently long in the FRG and the game stopping probability sufficiently low in the DRG. This explains the presence of the lower bound on T and upper bound on λ.

Comment 2 (Cooperation plan). In the DRG, the cooperation plan consists in always transmitting at the powers corresponding to the OP analyzed in Sec. IV-A. In the FRG, the cooperation plan includes a phase where the transmitters play the one-shot game NE, which can seem surprising. The game having a finite number of stages, it appears that the players who deviate at the last stage of the game cannot be punished. If a player deviates earlier it can happen that the punishment undergone by the deviator is not sufficiently severe. Therefore, the agreement consisting in playing the one-shot NE during the second phase of the cooperation plan corresponds to a selfish trade-off between the gain brought by deviating without being punished severely enough and the one brought by playing at an efficient point (namely the OP, which Pareto-dominates the one-shot NE).

Comment 3 (Deviation detection mechanism). The cooperation plan is implementable only if the transmitters can detect a deviation from the cooperation plan. It turns out that the knowledge of the public signal is sufficient for this purpose. Indeed, when the transmitters play at the OP, the public signal equals out to be crucial it would be necessary to consider other solution concepts such as strong equilibria which are stable to deviations of coalitions [START_REF] Aumann | The Core of a Cooperative Game Without Side Payments[END_REF][26] [START_REF] Sorin | Repeated Games with Complete Information[END_REF] but this is out of scope of this paper.

Comment 4 (Punishment procedure). There is one difference between Theorems 8 and 9 in terms of punishment. In the FRG, the other transmitters punish the deviator by playing at their maximum transmit power, which is the most severe punishment possible. In the DRG, the punishment is that the other transmitters play at the one-shot game NE. The drawback for punishing at the one-shot game NE point is that the punishment mechanism is less efficient which is to say, more game stages are needed to punish the deviator. The advantage is that the proposed equilibrium strategy is subgame perfect [START_REF] Selten | Spieltheoretische behandlung eines oligopolmodells mit nachfragetragheit[END_REF]. The subgame perfection property ensures that if a joint strategy τ of the RG supports an equilibrium then, after all possible histories h, the joint strategy τ (h) is still an equilibrium strategy, which makes the decentralized network performance predictable. Back to the FRG, it can be proven [START_REF] Benoit | Finitely Repeated Games[END_REF] that the subgame perfect equilibrium property cannot be verified in this RG because the associated one-shot game has only one pure NE (whereas at least two pure NE are needed).

Comment 5 (Equilibrium conditions and wireless channels). The equilibrium conditions provided can be seen to be independent of the channel statistics. If the latter are known, it is possible to refine the bounds (see App. D for more details). To the best of the authors' knowledge, this type of conditions are not considered in the available wireless literature whereas it is important to know whether the models of RG are applicable. The problem of how much these conditions are restrictive can be seen from two complementary perspectives. If the channel gain dynamics is given, the question is to know the maximum (resp. minimum) value of the discount factor (resp. game stages) guaranteeing the existence of an equilibrium condition. The values for η min i and η max i depend on the propagation scenario and considered technology. In systems like

WiFi networks these quantities typically correspond to the path loss dynamics, the receiver sensitivity, the minimum distance between the transmitter and receiver. On the other hand, if the discount factor (resp. the number of game stages) is given (e.g., by the traffic statistics or training sequence length), this imposes lower and upper bounds on the channel gains. It can happen that the admissible range for the discount factor (or the number of game stages) can be not compatible with the channel gain dynamics, in which case our model need to be refined.

V. NUMERICAL RESULTS

In this section we consider the same type of scenarios as [START_REF] Meshkati | A game-theoretic approach to energy-efficient power control in multi-carrier CDMA systems[END_REF][5] namely random CDMA systems with a spreading factor equal to N , the efficiency function f (x) = (1 -e -x ) M and Rayleigh fading channels.

The first scenario considered is simple but has the advantage that it can be represented clearly. Consider the scenario (K, M, N ) = (2, 2, 2). Fig. 1 represents the normalized achievable utility region of the oneshot PC game (normalizing the utilities allows one to conduct fair comparisons). Four important points are highlighted: the NE of the one-shot game (circle), the SE (star), the proposed operating/cooperation point studied in Sec. IV-A (square marker), and the point where the social welfare (sum of utilities) is maximized (cross). From this figure it can be seen that: the utility region is convex; a significant gain can be obtained by using a model of repeated games instead of the one-shot model; and the cooperation and optimum social points coincide.

Considering the same scenario, the link between the number of stages of the FRG (resp. the stopping probability of the DRG) and channel gain dynamics has been considered. Fig. 2 (resp. 3) represents the quantity 10 log 10 η max η min as a function of T (resp. of λ) for M = 2 and different numbers of transmitters and spreading factors : (K, N ) ∈ {(2, 2), (4, 5), [START_REF] Benoit | Finitely Repeated Games[END_REF][START_REF] Etkin | Spectrum Sharing for Unlicensed Bands[END_REF]}. Considering the corresponding figures, the models of RG seem to be suitable not only in scenarios where |g i | models the path loss effects but also the fading effects. Of course if the number of stages is too small or the probability too high, more appropriate models have to be designed.

As a third type of numerical results, the performance gain brought by the DRG formulation of the distributed PC problem is assessed. Denote by w N E (resp. w SE and w DRG ) the efficiency of the NE (resp. SE and RG equilibrium) in terms of social welfare i.e., the sum of utilities of the players. Fig. 4 represents the quantity w DRG -w N E

w N E and w SE -w N E w N E in percentage as a function of the spectral efficiency α = K N with N = 128 and 2 ≤ K < N β * + 1. The asymptotes α max = 1 β * + 1 N are indicated in dotted lines for different values M ∈ {10, 100}. The improvement become very significant when the system load is close to 1 N + 1 β * , this is because the power at the one-shot game NE becomes large when the system becomes more and more loaded. As explained in [START_REF] Lasaulce | Introducing hierarchy in energy games[END_REF] for the Stackelberg approach, these gains are in fact limited by the maximum transmit power.

At last, Fig. 5 represents the ratio w F RG w N E as a function of the number of stages played (averaged over channel gains). Considering the following constants (K, M, N ) = (35, 10, 128), P max = 10 -2 Watt, σ 2 = 10 -5 Watt, 10 log 10 ( ηmax η min ) = 20 and the equation ( 10), a cooperation plan can be settled as soon as T 0 = 2852 stages. This curve gives an idea of what a transmitter can gain by cooperating, the normalized gain in terms of utility goes from 1 to 6 depending on the number of stages of the game (between 2852 and 15000 stages). For example, in a cellular system where power levels are updated with a typical frequency of 1500 Hz, this would mean that cooperating is a good option if several transmitters are using the same resources for more than 1 s. The ratio w F RG w N E has a limit when T → +∞. The latter is easy to obtain since

wF RG wNE = φ(γ) K i=1 Ri T -T 0 t=1 |gi(t)| 2 + φ(β * ) K i=1 Ri T t=T -T 0 +1 |gi(t)| 2 φ(β * ) K i=1 Ri T t=1 |gi(t)| 2 (14)
July 29, 2010 DRAFT where φ(x) = f (x)

x [1 -(K -1)x]. It follows that, for a given T 0 , lim

T →+∞ w F RG w N E = φ(γ) φ(β * ) .

VI. CONCLUSION

One of the messages of this paper is that taking into account the fact that transmitters interact several times, it is possible to incite selfish transmitters to operate at lower powers, which leads to an equilibrium point that Pareto-dominates the one-shot NE point of [START_REF] Goodman | Power control for wireless data[END_REF] and the SE point of [START_REF] Lasaulce | Introducing hierarchy in energy games[END_REF]. It has been proven that the proposed equilibrium strategies only require individual CSI and a public signal, which is available in many wireless systems. Additionally, this equilibrium is also fair in terms of SINR similarly to the oneshot game NE. In terms of modeling, two models of RG have been analyzed: the finitely RG which is suited to situations where the number of game stages is known, whereas the discounted RG is more suited to situations where it is uncertain or when typical features of wireless networks (delay sensitivity of the network, the fact that users can enter/leave the system, or the fact that transmitters can value the current and future utilities differently) have to be accounted for. An apparent drawback of these two models is the existence of an admissible range for the channel gain dynamics. When only path loss is considered, the corresponding effect is generally negligible. If fading is also considered, simulations have shown that the corresponding impact seems to be limited if the game stopping probability (resp. number of game stages) is reasonably low (resp. high). Otherwise, the proposed model probably needs some refinements such as those proposed in [START_REF] Sorin | On Repeated Games with Complete Information[END_REF] where the author studies the influence of the value of the discount factor on the set of possible equilibrium utilities for the prisoners' dilemma. As a more general extension of this paper it would be important to apply the proposed approach to other network types such as the interference channel and studying other equilibrium points (depending on the fairness criterion under consideration). At last but not least, the proposed communication and game models, even through there are commonly used, should be refined to propose cooperation plans more robust to imperfect modeling and inherent uncertainty on the quantities used.

APPENDIX A PROOF OF PROPOSITION 5 Assume that U G is convex. Let u be a point of U G . Define the hyperplane H(u), orthogonal to the vector

1 |g 1 | 2 , ..., 1 |g K | 2
and containing u by:

H(u) = (u 1 , ..., u K ) ∈ R K + : K i=1 u i -u i |g i | 2 = 0 .
The key observation to be made is that the point ũ = (u 1 (p), ..., u K (p)) given by ( 9) maximizes the weighted sum K i=1 w i u i

July 29, 2010 DRAFT

if w i = 1 |g i | 2 . Note that ũ is unique since the solution of x [1 -(K -1)x] f (x) -f (x) = 0 is unique p = arg max p K i=1 u i (p) |g i | 2 .
By definition, ũ maximizes the Euclidian distance d(u, 0) for all points on the line originating from 0 and directed by the vector

1 |g 1 | 2 , ..., 1 |g K | 2
, orthogonal to the hyperplane H(ũ). In conclusion, ũ maximizes the sum N i=1 u i |g i | 2 , and because of the convexity of the utility region, no other achievable point can dominate the hyperplane H(ũ), which shows that ũ is PO.

Now assume that U C

G is convex. Denote by u max i the maximal utility for player i. Define a set of K points (û i ) i∈K , such that: ûi = (0, . . . , u max i + 1, . . . , 0). Let P be a polyhedron defined as the subset of R K + that dominates every hyperplane passing through the OP ũ and a combination of K -1 points ûi . As U C G is convex, this polyhedron intersects the achievable utility region in a unique point which is the OP ũ. Since the positive orthan at the OP is strictly included in the polyhedron, the OP is therefore PO.

APPENDIX B PROOF OF PROPOSITION 6

Statement (i). From Sec. II-C we have that

ũi u L i = f (γ) γ [1-(K-1)γ](1+β * ) f (γ * ) γ * [1-(K-1)γ * β * -(K-2)β * ] (15) ≥ f (γ) γ [β * -(K-1)γ * β * +1-(K-1)γ * ] f (γ * ) γ * (β * -(K-1)γ * β * +1-(K-1)β * ) . (16)
Since by definition β * ≥ γ * we readily see that ũi

u L i ≥ 1.
Statement (ii). From Sec. II-C we have that

ũi u F i = f (γ) γ [1 -(K -1)γ](1 + γ * ) f (β * ) β * [1 -(K -1)γ * β * -(K -2)β * ] (17)
≥ f (γ) γ {1 -γ[(K -1)γ * + K -2]} f (β * ) β * {1 -β * [(K -1)γ * + K -2]} . ( 18
)
We want to prove that this ratio is greater than or equal to 1. We consider the quantity :

ϕ [γ K ,β * ] (K) = f (γ K ) γK {1 -γK [(K -1)γ * K + K -2]} (19)
-f (β * ) β * {1 -β * [(K -1)γ * K + K -2]} = K(f (β * ) -f (γK ))(γ * K + 1) + f (γ K ) γK ( 20
) -f (β * ) β * -(f (β * ) -f (γK ))(γ * K + 2) ≥ K(f (β * ) -f (γK ))(γK + 1) + f (γ K ) γK (21) -f (β * ) β * -(f (β * ) -f (γK ))(β * + 2) (22)
As γK goes to zero as K goes to infinity, (γ K ≤ 1 K-1 ) and by hypothesis f (0) = 0, lim x→0 f (x)

x = 0 :

limK→+∞ ϕ [γ K ,β * ] (K) (23)
≥ limK→+∞ K[(f (β * ) -f (γK ))(γK + 1)] (24)
+ f (γ K ) γK -f (β * ) β * -(f (β * ) -f (γK ))(β * + 2) ≥ limK→+∞ K(f (β * )) -f (β * ) β * -(f (β * ))(β * + 2) = +∞ (25)
In conclusion, the sequence (ϕ [γ K ,β * ] (K)) K≥2 is strictly increasing and its limit is +∞. There exists an integer K 0 such that for all

K ≥ K 0 , ϕ [γ K ,β * ] (K) > 0. This implies that u i (p) > u F i . APPENDIX C PROOF OF PROPOSITION 7
The goal is to show that ∀i ∈ K,

u i (p) u i (p * ) = f (γ) γ [1-(K-1)γ] f (γ * ) γ * [1-(K-1)γ * ]
is greater than or equal to one. For this, consider the function φ

(x) = f (x) x [1 -(K -1)x]. The derivative of φ is φ (x) = x(1-(K-1)x)f (x)-f (x) x 2
which vanishes in unique point namely, in γ. Therefore the function φ is strictly increasing on ]0, γ[ and strictly decreasing on ]γ, +∞[ and thus reaches its maximum in γ, which concludes the proof.

APPENDIX D PROOF OF THEOREMS 8 AND 9

The proofs are provided in the general case where the PC game is repeated for different channel realizations (DSPC). At a game stage t a transmitter has therefore to consider future realizations of the channels, which are unknown at stage t. To tackle this issue we use a dynamic programming principle [START_REF] Shapley | Stochastic Games[END_REF], which is standard in repeated game. Let us define ūi = max p u

i (p) = R i |g i | 2 f (β * ) σ 2 β *
, the maximal utility player i can get for a fixed channel gain |g i | 2 . First consider the FRG. It is clear that during the last T 0 stage, the players play the one-shot NE. Thus no deviation over this period can be profitable to any player. We now consider that a player deviates during the first T -T 0 stages. His deviation utility is bounded by ūi and he will be punished at his minmax level in the next stage. Suppose the deviator deviates at stage t ≤ T -T 0 . Denote by u i = min p -i max p i u i (p) with p -i = (p 1 , ..., p i-1 , p i+1 , ..., p K ). The deviation utility of the FRG is upper-bounded as: The worst case scenario for stochastic channel gains implies the average case scenario. The condition of theorem 8 is sufficient for the desired equilibrium condition hold at each stage t of the FRG. This concludes the proof for the FRG. Consider now the equilibrium condition for the DRG at stage t :

λ ūi(p t ) + s≥t+1 λ(1 -λ) s-t Eg[u * i (p s )] ≤ λ ũi(p t ) + s≥t+1 λ(1 -λ) s-t Eg[ ũi(p s )] ⇐⇒ λ|gi| 2 f (β * ) β * + s≥t+1 λ(1 -λ) s-t Eg[|gi| 2 ] f (β * )(1 -(K -1)β * ) β * ≤ λ|gi| 2 f (γ)(1 -(K -1)γ) γ + s≥t+1 λ(1 -λ) s-t Eg[|gi| 2 ] f (γ)(1 -(K -1)γ) γ ⇐⇒ λ|gi| 2 f (β * ) β * - f (γ)(1 -(K -1)γ) γ ≤ s≥t+1 λ(1 -λ) s-t Eg |gi| 2 × f (γ)(1 -(K -1)γ) γ - f (β * )(1 -(K -1)β * ) β *

  networks: (a) as shown in the previous section, only individual CSI is required at the transmitters; (b) it is fair in terms of SINR like the NE in the one-shot game G; (c) it is PO under sufficient but reasonable conditions; (d) it is more efficient than the equilibrium point of the SE point of[START_REF] Lasaulce | Introducing hierarchy in energy games[END_REF] under sufficient but reasonable conditions; (e) it is always more efficient than the NE in the one-shot game G; (f) it is subgame perfect (this notion will be explained in Sec. IV-B) in the case of the DRG. The corresponding equilibrium relies on a cooperation plan exploiting two points of the one-shot game: the NE point presented in Sec.

2σ 2 1

 2 -(K-1)γ . Therefore, if one transmitter deviates from the OP, the public signal ω(t) is no longer constant. Of course, if more transmitters deviate from the equilibrium in a coordinated manner this detection mechanism can fail; this is not inherent to the proposed cooperation plan but to the NE definition. If this issue should turn July 29, 2010 DRAFT

t- 1 s=1

 1 ũi(p(s)) + ūi(p(t)) + T s=t+1 Eg[ u i (p(s))] ≤ T -T 0 -1 s=1 ũi(p(s)) + ūi(p(T -T0)) + T s=T -T 0 +1 Eg[ ui (p(s))]The equilibrium condition for the FRG at stage t writes as:T -T 0 -1 s=1 ũi(p(s)) + ūi(p(T -T0)) + T s=T -T 0 +1 Eg[ ui (p(s))] ≤ T -T 0 -1 s=1 ũi(p(s)) + ũi(p(T -T0)) + T s=T -T 0 +1 Eg[u * i (p(s))]

.

  ⇐⇒ūi(p(t)) + T s=T -T 0 +1 Eg[ ui (p(s))]≤ ũi(p(t)) + T s=T -T 0 +1 Eg[u * i (p(s))] ⇐⇒ |gi| 2 f (β * ) β * + T s=T -T 0 +1 Eg[ |g i | 2 f (β * ) β * ( j∈K\i p max j |g j | 2 +σ 2 ) ] ≤ |gi| 2 f (γ)(1-(K-1)γ) γ + T s=T -T 0 +1 Eg[|gi| 2 ] f (β * )(1-(K-1)β * )β *Now we want to show that the last inequality is verified under the sufficient condition of Theorem 8. The sufficient condition of Theorem 8 implies that:η max i f (β * ) β * -η min i f (γ)(1-(K-1)γ) γ ≤ T0 η min i f (β * )(1-(K-1)β * ) β * -η max i f (β * ) β * ( j∈K\i p max j 0 +1 η min i f (β * )(1-(K-1)β * ) β * ,

Fig. 1 .Fig. 2 .Fig. 3 .Fig. 4 .Fig. 5 .

 12345 Fig. 1. Normalized achievable utility region for (K, M, N ) = (2, 2, 2) plus four important points.

  The static PC game is a triplet G = (K, {A i } i∈K , {u i } i∈K ) where K is the set of players, A 1 , ..., A K are the corresponding sets of actions, A i = [0, P max

	Definition 1 (Static PC game): i	], P max i	is the maximum
	transmit power for player i, and u 1 , ..., u k are the utilities of the different players which are defined by:
	July 29, 2010		DRAFT

July 29, 2010 DRAFT

The equilibrium condition for the DRG can be obtained by following the same reasoning as for the FRG.