{
  "id": "2009.04425",
  "version": "v1",
  "published": "2020-09-09T17:15:55.000Z",
  "updated": "2020-09-09T17:15:55.000Z",
  "title": "(In)Existence of Equilibria for 2-Players, 2-Values Games with Concave Valuations",
  "authors": [
    "Chryssis Georgiou",
    "Marios Mavronicolas",
    "Burkhard Monien"
  ],
  "comment": "34 pages, 4 figures",
  "categories": [
    "cs.GT"
  ],
  "abstract": "We consider 2-players, 2-values minimization games where the players' costs take on two values, $a,b$, $a<b$. The players play mixed strategies and their costs are evaluated by unimodal valuations. This broad class of valuations includes all concave, one-parameter functions $\\mathsf{F}: [0,1]\\rightarrow \\mathbb{R}$ with a unique maximum point. Our main result is an impossibility result stating that: If the maximum is obtained in $(0,1)$ and $\\mathsf{F}\\left(\\frac{1}{2}\\right)\\ne b$, then there exists a 2-players, 2-values game without $\\mathsf{F}$-equilibrium. The counterexample game used for the impossibility result belongs to a new class of very sparse 2-players, 2-values bimatrix games which we call normal games. In an attempt to investigate the remaining case $\\mathsf{F}\\left(\\frac{1}{2}\\right) = b$, we show that: - Every normal, $n$-strategies game has an ${\\mathsf{F}}$-equilibrium when ${\\mathsf{F}}\\left( \\frac{1}{2} \\right) = b$. We present a linear time algorithm for computing such an equilibrium. - For 2-players, 2-values games with 3 strategies we have that if $\\mathsf{F}\\left(\\frac{1}{2}\\right) \\le b$, then every 2-players, 2-values, 3-strategies game has an $\\mathsf{F}$-equilibrium; if $\\mathsf{F}\\left(\\frac{1}{2}\\right) > b$, then there exists a normal 2-players, 2-values, 3-strategies game without $\\mathsf{F}$-equilibrium. To the best of our knowledge, this work is the first to provide an (almost complete) answer on whether there is, for a given concave function $\\mathsf{F}$, a counterexample game without $\\mathsf{F}$-equilibrium.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-09-09T17:15:55.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "equilibrium",
      "concave valuations",
      "counterexample game",
      "players play mixed strategies",
      "linear time algorithm"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 34,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}