# Notes & Questions of Pro-Rata games
Note: In general I will assume that functions are twice differentiable.

## Coarse and correlated equilbrium
**Question**: Arre all the coarse correlated equilibrium Nash equilibrium when $f$ strictly concave?
## Aggregative games

First, concave pro-rata games consist of a special case of aggregative games in which the payoff of each player is a function of their strategy and the sum of the strategies of all players. More formally, an aggregative game is a standard non-cooperative game with $n$ players, where $S_i\subseteq \mathbb R$ is the strategy set of player $i$, $S=\prod S_i$ is the joint strategy set, and $f_i: S\rightarrow\mathbb R$ is the payoff function of player $i$. The game is the called an $\textit{aggregative game}$ if for each player $i$ there exist a function $\tilde{f}: S_i\times \mathbb R\rightarrow \mathbb R$ such that for all $s\in S$:
\begin{equation*}
f_i(s) = \tilde{f_i}(s_i,\sum_{j=1}^ns_j)
\end{equation*}
In words, payoff functions in aggregative games depend on players' own strategies and the aggregate $\sum s_{j}$. In the following section, we will see why in Permissionless and Decentralized scenarios, the pro-rata games are the natural aggregative games to be studied.

If we take the definitions of Sybil and Collusion proof in [An Axiomatic Approach to Block Rewards](https://arxiv.org/abs/1909.10645) we have the following:

- $\textit{Symmetry}$: For all $i,j$, it holds $f_i(s) = f_j(\tau(s))$ where $\tau=(i\quad j)$ is the permutation that changes $i$ for $j$. So, if the game is aggregative, we can write $U_i(x_i,x_{-i}) = f(x_i,\textbf{1}\cdot x)$.
- $\textit{Collusion-proof}$: (We assume that the game is Symmetric and aggregative to simplify the definition) $\sum_{i\in\mathcal I}f(x_i,x)\leq f(\sum_{i\in\mathcal I} x_i,x)$ for all finite set $\mathcal I\subseteq \mathbb N$
- $\textit{Sybil-proof}$: Definition provided in [The Cost of Sybils, Credible Commitments, and False-Name Proof Mechanisms](https://arxiv.org/abs/2301.12813) with cost per Sybil zero. That is, $\sum_{i\in\mathcal I}f(x_i,x)\geq f(\sum_{i\in\mathcal I} x_i,x)$ for all finite set $\mathcal I\subseteq \mathbb N$.

**Proposition**: Every symmetric aggregative continuous game (with action space $\mathbb R_{\geq0}$) that is Sybil-proof and Collusion-proof is a pro-rata game.

*Proof sketch*: We will prove that $U_i(x_i,x_{-i}) = x_i g(x_i+x_{-i})$, and so we will deduce that is a pro-rata game. By Sybil-proofness and Collusion-proofness, we have that $f(k,k+y)=kf(1,k+y)$ for all $k\in\mathbb N$. Similarly, we have that $U_i(1,1+y) = (1/k)f(1,1+y)$ for all $k\in\mathbb N$. Therefore, we deduce that for all $q\in\mathbb Q_{\geq0}$, it holds $f(x,y) = xf(1,y)$. By continuity, we deduce that $f(x,y)=xf(1,x+y)$ holds for all positive real numbers. If we define $g(x) = f(1,x)$ we have finished the proof.

What happens if the game is not Sybil-proof and Collusion-proof. Can we definie a natural Collusion extension game (as we dide in [The Cost of Sybils, Credible Commitments, and False-Name Proof Mechanisms](https://arxiv.org/abs/2301.12813)). Is this extension some type of pro-rata (posible discrete) game?

## Discrete pro-rata games
In [Concave pro-rata games](), the authors assume that the action space of players in pro-rata games are $\mathbb R_{\geq0}$. We will study the pro-rata games with action space $\mathbb N$ (or any discrete space). So, let $f:\mathbb R_{\geq0}\rightarrow\mathbb R$ be a twice differential function, strictly concave, and that there exist $w_0>0$ such that $f(w_0)=0$. In this section, we will prove that discrete pro-rata games have pure semi-symmetric Nash equilibrium, that is: There exists a tuple of actions $s$ such that $s\in V_z:=\{x\in\mathbb N^n:x\in\{z,z+1\}\}$ and is an equilibrium. Also, we will prove that $|z - q/n| \leq 1$, where $q$ is the solution of the optimization problem. And so, we will deduce that the price of anarchy of these games is $\Theta(n)$.

$\textbf{Existence of pseudo-symmetric pure Nash equilibrium}$: Since the space of action is $\mathbb N$, the game is not finite. However, since exist $w_0$ such that $f(w_0)=0$, and strictily concave, we have that all actions $x\in \mathbb N$ with $x>w_0$ are strictly dominated since $f(x)<0$ (due to the concavity of $f$) and therefore, for all $y$ holds that $U_i(x,y)<0$. So, we can reduce the set of actions in $[0,w_0]\cap \mathbb N$. Now, by theorem 1 [imura2016](), we have that to prove that there exists a tuple of actions $s$ such that $s\in V_z:=\{x\in\mathbb N^n:x\in\{z,z+1\}\}$ and is an equilibrium is enough to prove that
\begin{align}
U_i(s-e^i)>U_i(s)&\Rightarrow U_i(s-e^j) > U_i(s-e^j+e^i)\quad \forall s,i,j\\
U_i(s)<U_i(s+e^i)&\Rightarrow U_i(s+e^j-e^i)<U_i(s+e^j) \quad \forall s,i,j\\
\end{align}
We will prove the first one (the second one is analogous). The first implication is equivalent to proving that
\begin{equation*}
\frac{x-1}{x+y-1}f(x+y-1)>\frac{x}{x+y}f(x+y)\Rightarrow \frac{x}{x+y-1}f(x+y-1)> \frac{x+1}{x+y}f(x+y) \quad \forall x,y,i
\end{equation*}
Assume that the first inequality holds for $x,y,i$. Then:
\begin{align*}
\frac{x}{x+y-1}f(x+y-1) &= \frac{x-1}{x+y-1}f(x+y-1)+ \frac{1}{x+y-1}f(x+y-1)\\
&>\frac{x}{x+y-1}f(x+y) + \frac{1}{x+y-1}f(x+y-1)\\
&> \frac{1}{x+y-1}f(x+y-1)+ \frac{1}{x+y}f(x+y)\\
&=\frac{x+1}{x+y}f(x+y)
\end{align*}
where the first inequality holds by assumption and the second one holds by the strict concavity of $f$, since $f(t)>\frac{t}{t'}f(t')$ for all $0<t<t'$, see more details in [Concave pro-rata games](). Therefore, by theorem 1 [imura2016]() we have that there exists a pure pseudo-symmetric Nash equilibrium.

## Repeated game

If the pro-rata game is a potential game, the game converges to a Nash equilibrium with the best replicator dynamics. However, a pro-rata game (twice differential) is a Potantial game if and only if is the linear Cournout oligopoly game.

If a game is a potential game, it holds
\begin{equation}
\frac{\partial^2 U_i}{\partial x_i\partial x_j} =\frac{\partial^2 U_j}{\partial x_i\partial x_j}\text{ for all }i,j\quad (1)
\end{equation}

We can rewrite the pro-rata game as $U_i(x,y) = xg(x+y)$ with $g(t)= f(t)/t$.
If the game is a pro-rata game, this translates to
$$
\frac{\partial^2 U_i}{\partial x_i\partial x_j} = f'(x_i+x_{-i})+x_if''(x_i+x_{-i})
$$
And so, the condition (1) is equivalent to $f''=0$. Therefore, $f(t) = A+Bt$. Therefore, the pro-rata game is the linear cornout game.

In [even2009convergence](), the authors define *Socially concave games* $\Gamma=(N,(A_i),(u_i))$, where $N=[n]$ is the set of players $A_i$ set of actions (convex) and $u_i:\prod A_i\rightarrow \mathbb R$ is playe's $i$ utility function. Assume that $u_i$ is bounded and twice differentiable. Moreover, holds

1) There exists a strict convex combination of the payoff functions whichs is a concave function.
2) The utility function of each player $i$, is convex in actions of the other players i.e. for every $x_i$ the function $u_i(x_i,x_{-i})$ is convex in $x_{-i}$.

Assume that $f$ is twice differential function. Then all pro-rata games hold $1)$. On the other hand the condition $2)$ is equivalent to

\begin{equation}
2f(t)-2tf'(t)+t^2f''(t)>0
\end{equation}

This is equivalent to $f(t)/t$ being convex.

The set of convex functions that hold this is non-empty. The linear cournout oliyopoly game holds the condition $2)$ since is linear in the second term and in particular convex. On the other hand, not all concave function hold this condition.

Now if we consider the concave pro-rata games that are socially concave games, we have by theorem $3.1$ of [even2009convergence]() no-external regret behavior leads to a Nash equilibrium.

Also, if the game is monotone, then the gradient ascent policy converges to Nash equilibrium.

This strategies are in general not Nash policies. This can be deduced with a similar argument used in [The Cost of Sybils, Credible Commitments, and False-Name Proof Mechanisms](https://arxiv.org/abs/2301.12813). Assume that the gradient descent policy $\pi$ is a Nash policy. Observe that the gradient policy is independent of the number of players. We can write the $r(n) = V_i(\pi,...,\pi)$ with $\pi$ played by $n$ players (were $V_i$ is the expected discounted reward). If its a Nash policy, implies in particular that a player creating two independent instances of the policy $\pi\otimes\pi$ (two Sybils) is dominated, i.e $r(n)\geq r(n+1)$. We would deduce that $r(n)\leq r(1)n/2^n$. Since the Nash policies converge to the Nash equilibrium, we have that $r(n)=\Theta(n)$. Contradiciton.

Definition of $\pi\otimes\pi$: Strategy that creates two instances that follow the strategy $\pi$ independently.

## Sybil-commitment of concave pro-rata games

We assume that costs of creating sybil commitments is zero or $c(k)=ck$
**Observation**: The Sybil-commitment of a concave pro-rata game is a discrete pro-rata game. In equilibimum $x= (q(n)/n)\cdot\textbf{1}^T$, ($q(n)$ is the elemnt that maximizes $q^{n-1}f(q)$) the payoff of each Sybil is $f(q(n))/n$ and so, the profit of reporting $x$ players if $y$ are report it is $\frac{x}{x+y}f(q(x+y))$. This game is clearly discrete. What can we say about the Nash equilibirum, and the PoA?

## Best response to players using gradient ascent strategies in concave pro-rata games

What is the best response to players using gradient ascent strategies in concave pro-rata games?

Assume all players except one (adversarial) follow a gradient descent policy in a monotone game. Then, what is the strategy that maximize the adverserial discounted average payoff with discount factor $\delta$? If the number of players is known by the adversary the answer is simple if $\delta\rightarrow 1$. If $\delta$ is small depends on players priors.

For each $z$, we can define the game $U_i(x_{i},x_{-i}) = \frac{x_i}{x_{i}+x_{-i}+z}f(x_i+x_{-i}+z)$. This game has a unique Nash equilibrium $x=q(z,n)/n$. Then the best response is

$$z_{max} =\text{argmax}_z \frac{z}{q(z,n)+z}f(q(z,n)+z)$$

Since the game is monotone, the payoff will converge to $\text{max}_z \frac{z}{q(z,n)+z}f(q(z,n)+z)$. Can we approximate this value?

Is $q(z,n)$ concave wrt $z$?

**Claim:** $q(z,n)$ is the unique solution of $\text{max }_{q\geq0} \frac{q^{n}}{(z+q)}f(z+q)$ i.e.
$$q(z,n)=\text{argmax }_{q\geq0} \frac{q^{n}}{(z+q)}f(z+q)$$

So, if $f(x)/x$ is concave for $x\geq0$ then the logarithm of $\frac{q^{n}}{(z+q)}f(z+q)$ is log-concave. So for each $z$ we can compute $q(z)$ efficiently

The leader have to solve

\begin{equation}
\text{max}_{z\geq0} \frac{z}{z+q(z)}f(z+q(z))
\end{equation}

## Questions

- What can we say about the Stackelberg equilibirum of pro-rata games? We assume that there are $n$-players. The act by lexicographic order, player $k$ can see the actions of players $i=1,...,k-1$. This game seems a natural game for Proof-stake games. Some players commit (lock) first, others follow.
- Can we say something more precise about discrete concave pro-rata games?
- With extra conditions, the pro-rata games converge (with different alogirthms) to the one-shoot Nash equilibrium in the repeated game. What can we say about concave pro-rata games?
- However, we know that this strategies are not Nash policies. Can we create a markov strategy $\pi$ such that $(\pi,...,\pi)$ is a nash policy independent of the number of players and players priors? Prbly can not be markovian.
- Existence of Symmetric prior and player independenty Nash policies in Symmetric games.

## References

- [Imura2016](https://link.springer.com/chapter/10.1007/978-3-319-29254-0_7)
- [Concave pro-rata games](https://angeris.github.io/papers/pro-rata-games.pdf)
- [even2009convergence](https://dl.acm.org/doi/abs/10.1145/1536414.1536486?casa_token=9wrjezDLvqEAAAAA:Odi5GZp2Wgwr9s5vyuMVyKqjJeYrrcLkjQBiRlZBFBGB1LblbOXDhUOSVwOlGUtId9nvt5VKAWTn)