Wednesday 6 September 2017

Cooperative games and the FEH voting event

Consider the following situation.

Two competitors A and B, are selling homogeneous products on the market. (Well not under perfect competition anyway.) Obviously they are enemies that they don't communicate. One day, however, due to unknown reasons they decided to maximize the total profit that they create. The profit of each of the seller can be viewed as a function of the seller's price and the opponent's price, assuming that the demand curve is fixed.

The problem is that they don't communicate. They even do not bother to check the opponent's price (it's time wasting -- profit maximization is only the command from the higher order). The only information they have on their hand is their price and their corresponding profit on that day (note: it relies on the opponent's price on the day too). Is it possible to adjust the price daily in order to edge close to the goal?

Call the price at the $i^{th}$ day $P_{A,i}, P_{B,i}$ and the profit function $f(\cdot, \cdot)$ that takes seller's price and opponent's price and output the profit for the seller (assume that the market is symmetric in the sense that swapping the price results in the same total profit). Is it possible to find such iteration so that $f(P_{A,i}, P_{B,i})+f(P_{B,i}, P_{A,i}) \to L$, the theoratical maximum (such maximum exists by compactness)? Does it help if we know the smoothness of $f$?

My unproved claim: if $f$ is strictly increasing respect to both variables and is Lipschitz (why the hell do we need such assumption?) then such algorithms exists. Don't ask me for further proof...

-------------------

I do not intend to include any explicit mathematics here, but it seems like a simple example is unavoidable, so let us consider the following.

Consider two initial values $A_0, B_0$ from two players A and B. At round $n$, player $A$ will know the his own number $A_n$ as well as the absolute distance $|A_n-B_n|$, and vice versa. Without any communication we want to devise an algorithm so that $|A_n-B_n| \to 0$.

We give the algorithm as follows. For $k>1$ we iterate as follows:

$A_{n+1} = A_n + (-1)^n |A_n-B_n|/k$
$B_{n+1} = B_n + (-1)^{n+1}|A_n-B_n|/k$

then by induction the value $|A_n-B_n|$ decreases every 2 rounds, and hence it converges to zero by the monotone convergence theorem. (Well, if we take $k=2$ we get it sorted out in 2 rounds, and we get the exact solution. However convergence holds for any $k>1$, too.)

Here we used the fact that there are only 2 players, so we implemented something that has period 2. In general when there are $N$ players we want to implement algorithms that are genuinely the same on each of the players.

-------------------

The first example is definitely an interesting case to think about, but $f$ is too vague to deal with. For concrete non-trivial examples we may consider this one instead:

Consider $N$ base stations $X_1,...,X_N \in \mathbb{R}^2$, and the convex polygon created $\Omega = conv(X_1,...,X_N)$. We may assign a radius $r_i$ to each station so that the area $\Omega \cap B(X_i; r_i)$ is now covered by the station $X_i$.

Larger coverage, of course, takes more energy. The energy required to maintain radius $r_i$ is proportional to $r_i^{2+\alpha}$, where $\alpha \in [0,1]$. The goal is to find $(r_i)$ so that 100% coverage is attained in $\Omega$ and the energy consumption is minimized.

Again communication among stations is prohibited. The only information each station $X_i$ knows is the coverage rate in the area $\Omega \cap B(X_i; R_i)$, where $R_i$ is the distance between $X_i$ and the closest station. Can you devise an algorithm for stations to adjust their radius $r_i$ towards the goal? Does it become any simpler in the case $\alpha = 0$, or $\alpha = 1$?

(Note: since we have the information on coverage rates, we allow stations imperfect coverage in the mean time -- we call that beta testing -- the algorithm is fine as long as the coverage rate converges to 100% AND the energy consumption converges to the optimal number.)

-------------------

Above are games where players cooperate under limited information. These type of games are extremely useful in various fields (economics and engineering) and are also actively researched. It is important in the sense that communication is always expensive.

Given linear/convex/smooth/well-behaved functions there are systemic methods to deal with those, or at least approximation-ish result are available. But what if the 'player' is in fact a mix between a selfish self (takes adjustments to maximize sole profit) and a generous self (take adjustments to maximize total profit)? That could well happen during political elections...or game voting events. The only prediction we can make it that things are unpredictable.

That is precisely why flame arised when Camilla beat Lyn with much less 'votes' in FEH's voting event. Things are event worse in the sense that this is a zero sum game so that it is impossible to cooperate after all. People thought that they are going to tweak the result but were only dominated by the 'selfish self' - the large portion of players who simply play on their own pace and not even hardly optimizing - and when things did not go naturally in their way they went annoyed and shit everywhere...

And for me, it is no more than a sleepless currency-earning event because I did not find my favourite characters (Ursula, and perhaps Tana too) there. Hehehe.

No comments:

Post a Comment