Непревзойденное решение для рок-бумаги-ножниц в матричной игре (ГЛПК)

Question

Я попытался реализовать эту линейную задачу, используя GLPK. Когда я проверил это против игры "камень-ножницы-бумага" (в равновесии в смешанных стратегиях) x=(1/3, 1/3, 1/3), y=(1/3, 1/3, 1/3У меня есть неоспоримое решение.

Я вернулся в MathProg, чтобы проверить, удастся ли это. К сожалению, это также не удалось. Я думаю, это связано с -1 значения, поскольку базовый симплекс-метод не допускает отрицательных переменных и требует некоторого преобразования, чтобы обойти его (хотя я думал, что это касается только переменных, и GLPK делает это автоматически).

Я определил проблему следующим образом:

• модель для игрока 1:

  set P1S;
  set P2S;
  
  param Payoff{P1S, P2S};
  
  var y{P1S} >= 0;
  
  minimize GameValue: sum{i in P1S} y[i];
  
  s.t. Condition2{j in P2S}:
      sum{i in P1S} Payoff[i,j] * y[i] >= 1;
  
  solve;
  
  printf "Value: %s\n", GameValue;
  
  printf "Player 1 strategies:\n";
  
  for{i in P1S}
      printf "Found %s, actual %s\n", y[i], y[i]/GameValue;
  
  end;
  

• данные:

  data;
  
  set P1S := r p s;
  set P2S := r p s;
  
  param Payoff
      :  r  p  s :=
      r  0 -1  1
      p  1  0 -1
      s -1  1  0;
  
  end;
  

Я запускаю это:

$ glpsol --model rps.mod --data rps.dat
GLPSOL: GLPK LP/MIP Solver, v4.54
Parameter(s) specified in the command line:
 --model rps.mod --data rps.dat
Reading model section from rps.mod...
22 lines were read
Reading data section from rps.dat...
12 lines were read
Generating GameValue...
Generating Condition2...
Model has been successfully generated
GLPK Simplex Optimizer, v4.54
4 rows, 3 columns, 9 non-zeros
Preprocessing...
3 rows, 3 columns, 6 non-zeros
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  1.000e+00  ratio =  1.000e+00
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part is 3
      0: obj =   0.000000000e+00  infeas =  3.000e+00 (0)
LP HAS NO PRIMAL FEASIBLE SOLUTION
glp_simplex: unable to recover undefined or non-optimal solution
Time used:   0.0 secs
Memory used: 0.1 Mb (126428 bytes)

Правильно ли мое предположение, и я могу применить какой-то простой способ (например, установить флаг)? Или это что-то еще, что я испортил (записал проблему неправильно или что-то упустил)?

РЕДАКТИРОВАТЬ:

После увеличения каждого значения матрицы на постоянную 1 (делая все значения неотрицательными) Я получил правильное решение (GameValue был также сдвинут 1 чтобы я мог восстановить его, вычтя). Это действительно только в этом случае, или оно сломается, если (перед запуском GLPK) я увеличу все параметры на константу, чтобы сделать их все неотрицательными? Есть ли какой-нибудь флаг, который я могу установить в GLPK, чтобы сделать это автоматически?

Answer 1

Нам разрешено увеличивать матрицу выплат на константу, чтобы сделать все элементы положительными - это также увеличит нашу GameValue на эту константу ( вики).

Поэтому, прежде чем делегировать проблему в GLPK, мы должны найти наименьший элемент матрицы (скажем, m) и рассчитать m' = min(m, 0), Тогда мы должны увеличить все элементы на abs(m'), решить проблему как обычно, и получить GameValue уменьшить на abs(m'),

Как в MathProg, так и в GLPK это можно сделать вручную (на самом деле MathProg имеет хороший min а также abs функции для расчета параметров - см. руководство), но, видимо, для этого нет флагов. Это преобразование не меняет правильность проблемы NE, но может повлиять на правильность других проблем LP, и мы не можем принять это как должное.