# Efficient Strategies Algorithms for Resource Allocation Problems
## 2 Background
### Game Theory  
Game theory studies interactive decision-making problems. Basically, a game in strategic form is given by the description of the interest of the players and the constraints which weigh on the strategies that players can choose [1]. A game essentially includes the following four elements [2]:  
* A set of players: this set specifies which decision-makers or players are involved in the game. A player can be a single individual or a group of individuals making a decision. Each player optimizes his/her quantity-of-interest, that is to say that each player is aware of the alternatives, anticipates the unknown elements, has clear preferences and deliberately chooses his/her action after an optimization process. * A set of rules: it is the course of the game, the procedure to follow and the possibilities of action or strategies (set of moves or choices of the players) offered to the players. * A set of issues: each outcome is the consequence of the actions taken by the players. * A set of gains: the outcomes determine the winnings distributed to players, the value (winnings or utility function) for each player of the different possible outcomes of the game. The notion of utility or utility function is modeling the interest that a player finds in an outcome. It is generally represented with a real number or real numbers so that a comparison can be made. Game theory is a set of tools allowing one to analyze interactions in which players (physical person, company, animal, state, machine, a group etc.) make decisions depending on the anticipations that it forms on what one or more other players will do. We refer the reader to [3; 4; 5; 6; 7; 8; 9; 10; 11] for more details and recent applications of game theory in deep learning. One of the objectives of game theory is to design and model situations requiring decision-making, to determine an optimal strategy for each of the players, to predict the outcomes of the game and to find out how to achieve an optimal situation. Game theory analyzes and predicts future actions using scientific means to create models of behavioral analysis and neglected at the base of external events, in particular natural ones, which have as much influence as other players in the game [12]. However, with the rapid evolution of this discipline, several of these forms of external events have already been taken into account in game theory over the past thirty years. The most common types of games can be found in [2]:  
1. Cooperative and non-cooperative games: a cooperative game is a situation where communication and agreements between players are allowed before the game. Thus, all the agreements between the players are respected and also all the messages formulated by one of the players are transmitted without modification to the others. On the other hand, the assessment of the situations by a player is not disturbed by the preliminary negotiations. Otherwise, we consider that the game is non-cooperative. 2. Simultaneous and sequential games: a simultaneous or strategic game is a situation where each player chooses his/her complete action plan once and for all at the start of the game. Consequently, the choices of all the players are simultaneous. So, when making a choice, the player is no longer informed of the choices of other players. On the other hand, a sequential game specifies the exact course of the game; each player considers his/her action plan, not only at the start of the game, but also whenever (s)he must actually make a decision during the course of the game. In general, the simultaneous games are represented in the form of a table and the sequential games are represented by a game tree which allows the complete representation of the structure and the progress of the game. 3. Finite games: a game is finite if the set of strategies for each player is finite. That is to say, the sets of strategies are finite sets. 4. Zero-sum games and non-zero-sum games: zero-sum games are two-player games in which the sum of the gains and losses of the two players is zero.