# Efficient Strategies Algorithms for Resource Allocation Problems
## 2 Background
### Game Theory
They are also called strictly competitive games because the interest of one player is strictly opposed to the interest of the other; therefore, the conflict is total and there is no possible cooperation (what wins one is lost by the other). Similarly, a non-zero sum game is a game in which the sum of the winnings is different from zero (0). It is either positive or negative. 5. Repeated games: the repeated games are simultaneous games which are played several times in a row. The game conditions do not change (the number of players and their strategies and also the utility functions of the strategies). 6. Games with full information and games with incomplete information: the information available to players every time they have to choose an action is a very important dimension of games. It has a decisive influence on the evaluation of strategies by players and even on their perception of strategies. A game is full information if all players know the structure of the game perfectly. It is incomplete information if at least one of the players does not know its structure perfectly. 7. Perfect memory games and imperfect memory games: the game is perfect memory if each player is perfectly informed of the past actions of other players. When a player ignores some of the choices that were made before his choice, the game is an imperfect memory game. The same game can belong to several types at the same time and according to different contexts of interactions we can classify the games into three big families based on: the type of cooperation between the players (cooperative or non-cooperative), development over time (simultaneous or sequential),information available to players (perfect or imperfect information and complete or incomplete) [1]. There are two basic forms to represent a game [1]:  
* Normal Form: a game in normal form is described by the following elements:
* A set of \(n\) players: \(I=\{1,\cdots,n\}\)
* For each player \(i\), \(i\in I\), a set of strategies \(\mathrm{Si}\), which contains all the possible strategies for this player. if \(S_{i}\) is a particular strategy for player \(i\). Therefore, \(S_{i}=S_{i}^{1},S_{i}^{2},\cdots,S_{i}^{n}\) if \(k_{i}\) strategies are available for player \(i\). If each player \(i\) chooses a strategy \(S_{i}\), we can represent the result (or strategy profile) of the game by a vector which contains all these strategies: \(s\equiv(s_{1},s_{2},\cdots,s_{n})\)
* For each player \(i\), a gain function, \(u_{i}\), which represents the preferences of player \(i\) by giving the value for player \(i\) of each result of the game: \(u_{i}(s)\). It's a real number: \(u_{i}:S=\prod_{i\in I}S_{i}\rightarrow\mathbb{R}\) \(s\equiv(s_{1},s_{2},\cdots,s_{n})\mapsto u_{i}(s)\) This form is suitable for the representation of simultaneous games which can be represented in the form of a table. * Extensive form: a game in extensive form is given by a game tree containing an initial node, decision nodes, terminal nodes and branches connecting each node to those which succeed it. * A set of \(n\geq 1\) players, indexed by \(i=1,2,\cdots,n\). * For each decision node, the name of the player who has the right to choose a strategy at this node. * For each player \(i\), the specification of all the actions allowed at each node where (s)he is likely to make a decision. * The specification of the winnings of each player at each terminal node. Sequential games where decisions are made at different times and each player can be made to play multiple times are shown in extensive form. There are several resolution methods:
* Elimination of equivalent strategies: Redundant strategies are called equivalent strategies, and after their elimination, we get the reduced normal form of the game. * Elimination of dominant strategies: Some of the players' strategies may be worse overall than others. One would expect that these strategies would never be chosen by rational players. We can then choose to eliminate them immediately from the game.