# Efficient Strategies Algorithms for Resource Allocation Problems
## 2 Background
### Different Games of [PERSON]
#### 2.3.1 Symmetrical Games  
* The zero-sum game: [PERSON]'s zero-sum game comes from [15]. It is a constant sum game involving two players, \(A\) and \(B\), and \(n\) independent battlegrounds. Player \(A\) has \(X_{a}\) units of force to be dispatched between the battlefields, and Player \(B\) has \(X_{b}\) units. Each player must distribute his/her forces without knowing the distribution of the opponent. If \(A\) sends \(X_{ak}\) units and \(B\) sends \(X_{bk}\) units to battlefield \(k\), the player with the higher strength level wins on battlefield \(k\). An equilibrium of this game is a pair of \(n\)-varied distributions (a varied distribution with \(n\) dimensions) and the first solutions appear in [15] in 1938, which solve the problem in the case of \(n=3\) and \(X_{a}=X_{b}\) (the number of battlefields is 3 and the number of resources of both players is equal). In the model of this game, two players \(A\) and \(B\) simultaneously assign their forces \(X_{a}\) and \(X_{b}\) respectively on a finite number \(n\geq 3\) of homogeneous battlefields. Each battlefield has a gain of \(1/n\). Each player's gain is the sum of the winnings across all battlefields or, equivalently, the proportion of battlefields to which the player sends a higher level of strength. In the case where both players allocate the same level of force to a battlefield, it is assumed that player \(B\) ((s)he is assumed to be the opponent of the one who establishes the game, so for him/her it is victory or defeat but no draw because the latter is considered a defeat) wins this battlefield and all resources are to be used.
* The non-zero sum game: After the constant sum game, [PERSON] and [PERSON] presented a non constant sum version of the classic Colonel Blotto game [16]. In [PERSON]'s original formulation of the Colonel Blotto game, player resources are \"use them or lose them\", in the sense that all resources that are not assigned to one of the contests are lost. The [PERSON] non-constant version of the Colonel Blotto game makes it more flexible to use or lose this feature. As a model, two players, \(A\) and \(B\), simultaneously enter offers in a finite number \(n\geq 3\), of independent battlefields. Each field has a common value for each player. Each player has a fixed level of available resources which may or may not be equal, but here, we will focus on the case where they are unequal. In the case where the players allocate the same level of force in a given field, it is assumed that player \(B\) wins on this field, otherwise the player who has used a greater number of resources wins this battlefield. As long as the players' budgets are not too asymmetrical, there is a equilibrium in the game. However, if the players' budgets are sufficiently asymmetrical, new joint distributions of equilibria must be built entirely.
* The game with heterogeneous battlefields: Colonel Blotto's game with heterogeneity in battlefield values is a variant of the games of Colonel Blotto previously seen, which presents a new geometric method for constructing equilibrium distributions with heterogeneous battlefields [17]. We have the two-player model \(A\) and \(B\) with identical budgets \(X_{a}=X_{b}\). The players have to allocate their resources on \(N\geq 3\) battlefields indexed by \(n\in\{1\cdots N\}\). For both players, the value of the battlefield \(i\) is \(v_{i}\in(0,\infty)\) and each player has his/her own value which (s)he assigns according to the importance of this field from his/her point of view (the fields do not have the same values for the two players). Each player seeks to maximize the overall value of the battlefields captured, by trying to win the most fields and prefers those with high values. The rules are like for the other games of colonel Blotto--the one who allocates a high number of forces (resources) wins this field, and when a tie occurs, it is assumed that player \(B\) wins this field.