论文标题
（IN）具有2个玩家，具有凹入估值的2个价值游戏的平衡
(In)Existence of Equilibria for 2-Players, 2-Values Games with Concave Valuations
论文作者
论文摘要
我们考虑2个玩家，2值最小化游戏，玩家的成本为两个值，$ a，b $，$ a <b $。玩家采用混合的策略，其成本通过单峰值估值来评估。这一广泛的估值包括所有凹面，单参数功能$ \ Mathsf {f}：[0,1] \ RightArrow \ Mathbb {R} $，具有唯一的最大点。我们的主要结果是一个不可能的结果表明：如果以$（0,1）$和$ \ MATHSF {f} \ left（\ frac {1} {2} {2} \ right）\ ne b $获得最大值，则在没有$ \ mathsf $ \ mathsf {f} $ quibrium的情况下，有2个竞争者，2-ValueS Game。 用于不可能结果的反例游戏属于一个非常稀疏的2个玩家，2值Bimatrix游戏的新类，我们称之为普通游戏。为了调查其余情况$ \ mathsf {f} \ left（\ frac {1} {2} {2} \ right）= b $，我们表明： - 每一个普通的$ n $ -strategies游戏都有$ {\ mathsf {f}} $ - 均衡 - $ {\ mathsf {f}}} \ left（\ frac {1} {2} {2} {2} \ right）= b $。我们提出了用于计算这种平衡的线性时间算法。 - 对于具有3种策略的2个玩家，我们有2个值游戏，如果$ \ mathsf {f} \ left（\ frac {1} {1} {2} {2} \ right）\ le b $，则每2个玩家，2个游戏，3-Values，3-Strategies游戏都有一个$ \ Mathsf {f} $ equirium {如果$ \ mathsf {f} \ left（\ frac {1} {2} \ right）> b $，则存在一个普通的2个玩家，2个值，3-策略游戏，而没有$ \ mathsf {f} $ - equilibium。 据我们所知，这项工作是第一个提供（几乎是完整的）答案，即对于给定的凹面函数$ \ mathsf {f} $，一个不带$ \ mathsf {f} $ equilibrium的反例游戏。
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.
