P9142 [THUPC 2023 初赛] LIAR GAME! 题解 & 纳什均衡浅探

· · 题解

纳什均衡与求解方法

考虑一个两名玩家 A 和 B 参与的游戏，先手有 n 种策略，记作 \mathcal F_{1, 2, \cdots, n}，后手有 m 种策略，记作 \mathcal G_{1, 2, \cdots, n}。对于任意 x\in [1, n] 和 y\in [1, m]，可以定义一个分数 P_{x, y} 为实数，代表若先手采取 \mathcal F_x 而后手采取 \mathcal G_y，则先手得到 P_{x, y} 分。

我们称 A 的一种策略为一个长度为 n 的实数数列 p，且诸项之和为 1，p_i 代表以 p_i 的概率选取 \mathcal F_i。定义一个操作的分数为 \min\limits_{q_1+q_2+\cdots+q_m = 1, \forall i , q_i\in[0, 1]} \{\sum\limits_{i, j} p_i q_j P_{i, j}\}。

先手必然有一个策略最大化其分数，后手必然也有一个策略最小化先手的分数，这两个值必然是相等的，这两个策略称作纳什均衡。

若欲求纳什均衡，不妨假设最大分数为 E，可以列出条件：

\exists \{p_i\}, p_i\in[0, 1], \sum p_i=1, \forall \{q_i\},q_i\in[0, 1], \sum q_i = 1, \sum\limits_{i, j} p_i q_j P_{i, j}\leq E

显然我们不需要这么多条件：只需要 m 个就够了。

\exists \{p_i\}, p_i\in[0, 1], \sum p_i=1, \forall j\in[1, m], \sum\limits_{i} p_i P_{i, j}\leq E

若能满足这 m 个条件，则必然可以满足任意选取 q_j 的不等式，只需要将所有 j，第 j 个条件的不等式乘上 q_j，然后求和，就可以得到对应的 q_j 的不等式。

重写成另一种形式：

\max E. \text{ subject to} \\ \left\{ \begin{aligned} &p_1, p_2, \cdots , p_n \in [0, 1] \\ &\sum p_i = 1\\ &\sum\limits p_i P_{i, 1}\leq E \\ &\sum\limits p_i P_{i, 2}\leq E \\ &\cdots \\ &\sum\limits p_i P_{i, m}\leq E \end{aligned} \right.

令 x_i 为若干未知数，满足 x_i = \frac{p_i}{E}，可以重写为

\min \sum x_i. \text{ subject to} \\ \left\{ \begin{aligned} &\sum\limits x_i P_{i, 1}\leq 1 \\ &\sum\limits x_i P_{i, 2}\leq 1 \\ &\cdots \\ &\sum\limits x_i P_{i, m}\leq 1 \end{aligned} \right.

可以直接利用线性规划求解。

但是线性规划太麻烦了，能不能再给力一点？

我们直接考虑方程组

\left\{ \begin{aligned} &\sum p_i = 1\\ &\sum\limits p_i P_{i, 1} = \sum\limits p_i P_{i, m}\\ &\sum\limits p_i P_{i, 2} = \sum\limits p_i P_{i, m}\\ &\cdots \\ &\sum\limits p_i P_{i, m-1} = \sum\limits p_i P_{i, m} \end{aligned} \right.

若方程组的解满足所有 p_i 均为正数，那么方程组的解 p_i 就是先手的最优策略。

证明留给读者做作业。

P9142 题解

列出纳什均衡后直接求解方程组即可。

#include<bits/stdc++.h>
#define f(i,x,y) for(int i=x, i##end=y; i<=i##end; ++i)
#define d(i,x,y) for(int i=y, i##end=x; i>=i##end; --i)
#define uf(i,x,y) for(int i=x, i##end=y; i<i##end; ++i)
#define ll long long
#define pir pair<int, int>
#define fir first
#define sec second
#define mp make_pair
#define pb push_back 
#define int long long
char ch;
int rd() {
  int f=1, x=0; ch=getchar();
  while(!isdigit(ch)) { f=((ch=='-')?-1:f); ch=getchar(); }
  while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
  return x*f;
}
void rd(int& x) { x=rd(); }
using namespace std;
const int _ = 1e6 + 5, mod = 998244353;
int qpow(int a, int b) {
  int res=1; for(; b; b>>=1, a=a*a%mod) if(b&1) res=res*a%mod; return res;
}
int v[_], s[_];
// n/2 v_n = \sum i=0 .. n-1 vi + (n-1)v{n-1}
// q1 = 2q0
// q2 = 5q0
int n;
signed main() {
  rd(n);
  v[0] = 1; v[1] = 2; s[0] = 1; s[1] = 3;
  f(i,2,n) {
    v[i] = (s[i-1] + (i-1) * v[i-1] % mod) % mod;
    v[i] = v[i] * 2 * qpow(i, mod-2) % mod;
    s[i] = s[i-1] + v[i];
    // cerr << i << ' ' << v[i] << endl;
  }
  // cerr << v[2] << endl;
  int ans = 2 * qpow(n+2, mod-2) % mod;
  cout << ans << ' ';
  f(i,1,n) {
    ans = qpow(n+2, mod-2);
    cout << ans << ' ';
  }
  cout << endl;
  ll s = 0;
  f(i,0,n) { s += v[i]; s %= mod; }
  s = qpow(s, mod-2);
  // cerr << "s = " << s << endl;
  f(i,0,n) {
    ans = v[i] * s % mod;
    cout << ans << ' ';
  }
  cout << endl;
  return 0;
}