5
$\begingroup$

Given a weight vector $w\in [0,1]^d$ such that $\sum w_i=1$, the game goes as follows:

Two players, $X,Y$ choose strategies $x,y\in [0,1]^d$ such that $\sum x_i = \sum y_i = 1$.

The utility (profit) for player $X$ is given by $$u_X=\sum_{i:x_i>y_i} x_i\cdot w_i$$

That is summing over all coordinates in which $x$ is larger than $y$, and the profit for the coordinate is given by $x_i\cdot w_i$.

Y's utility is symmetric ($u_Y=\sum_{i:y_i>x_i} y_i\cdot w_i$).

This also interests me for low dimension (say $d=3$) if it makes it easier.


We assume w.l.o.g that $i>j\implies w_i\geq w_j$.

If $w_1\geq \frac{1}{2}$ then this is trivial, so assume this is not the case.

If needed we may assume that if $x_i=y_i$ then they both get $\frac{x_i\cdot w_i}{2}$ utility for that coordinate.


Is there a known name for this game?

Is the equilibrium of this game computable or is it $PPAD$-hard?

$\endgroup$
  • $\begingroup$ Does an equilibrium definitely exist? $\endgroup$ – usul Sep 30 '14 at 16:37
  • $\begingroup$ @usul - doesn't Nash theorem shows that one has to exist? Rethinking the problem, it seems that a mixed strategy here would be a CDF/density function, which I'm not sure could be represented succinctly. I might need to rephrase the question. $\endgroup$ – R B Sep 30 '14 at 21:46
  • 1
    $\begingroup$ Technically I think Nash's theorem is only for finite action sets. For infinitely many pure strategies, the existence theorem I know of is Glicksberg's, which wants the strategy space to be compact (which is true here) and the payoffs to be continuous in the pure strategy. I'm worried about this last condition, continuity, since I think a small change in some $x_i$ can cause a payoff jump. Some slides about that theorem: ocw.mit.edu/courses/electrical-engineering-and-computer-science/… $\endgroup$ – usul Oct 1 '14 at 1:17
6
$\begingroup$

If you change the payoff to

$$\sum_{i:x_i>y_i} w_i $$

then this type of game is called a Colonel Blotto game or a Blotto game. It was studied by Borel. Your assumption that $\sum x_i = \sum y_i$ is not always a requirement.

In a 1950 paper, Gross and Wagner analyzed a few variants and contributed the name. They covered the cases of

  • $d=2$ in your notation, $n=2$ in theirs.
  • $d=3$, $\sum x_i = \sum y_i.$
  • $\sum x_i = \sum y_i$ and $w_j=1/d.$

Blotto games have been identified and analyzed in a few other papers.

$\endgroup$
  • $\begingroup$ Thanks for your answer. Do you know of any Blotto variant which corresponds to the fact my profit per-coordinate is dependent on both $w_i$ and $x_i$ (this is crucial for my application)? $\endgroup$ – R B Oct 2 '14 at 14:37
  • $\begingroup$ @RB: I had overlooked that part of the payoff function. What you have is not the same as a Blotto game, and perhaps you should not accept my answer. $\endgroup$ – Douglas Zare Oct 2 '14 at 19:43
  • $\begingroup$ As a real-world example, this is like Blotto's battlefield game where each soldier gets to advance somewhere (meaning the more soldiers that survive the better). $\endgroup$ – pfrank Oct 18 '14 at 6:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.