nfgcsum.imp

Gambit 是一个游戏库理论软件

//
// $Source: /home/gambit/CVS/gambit/sources/nash/nfgcsum.imp,v $
// $Date: 2002/09/10 14:27:42 $
// $Revision: 1.3.2.1 $
//
// DESCRIPTION:
// Implementation of algorithm to compute mixed strategy equilibria
// of constant sum normal form games via linear programming
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
//

#include "nfgcsum.h"
#include "game/nfgiter.h"

//-------------------------------------------------------------------------
//                      nfgLp<T>: Member functions
//-------------------------------------------------------------------------

template <class T> nfgLp<T>::nfgLp(void)
{ }

template <class T> 
gList<MixedSolution> nfgLp<T>::Solve(const NFSupport &p_support,
				     gStatus &p_status)
{
  BFS<T> cbfs((T) 0);
  
  if (p_support.Game().NumPlayers() != 2 || !IsConstSum(p_support.Game())) {
    return gList<MixedSolution>();
  }
  
  gList<BFS<T> > bfsList;
  
  int i,j,m,k;
  
  m = p_support.NumStrats(1);
  k = p_support.NumStrats(2);
  gMatrix<T> A(1,k+1,1,m+1);
  gVector<T> b(1,k+1);
  gVector<T> c(1,m+1);
  NfgIter iter(p_support);

  T minpay = MinPayoff(p_support.Game()) - gNumber(1);

  for (i = 1; i <= k; i++)  {
    for (j = 1; j <= m; j++)  {
      A(i, j) = gNumber(minpay) - p_support.Game().Payoff(iter.GetOutcome(), 1);
      iter.Next(1);
    }
    A(i,m+1) = (T)1;
    iter.Next(2);
  }
  for (j = 1;j<=m;j++)  {
    A(k+1,j)= (T)1;
  }
  A(k+1,m+1) = (T)0;

  b = (T)0;
  b[k+1] = (T)1;
  c = (T)0;
  c[m+1] = (T)1;

  LPSolve<T> LP(A,b,c,1,p_status);

  if (!LP.IsAborted()) {
    Add_BFS(p_support, LP, bfsList); 
  }

  gList<MixedSolution> solutions;
  GetSolutions(p_support, bfsList, solutions, LP.Epsilon());
  return solutions;
}

template <class T> int nfgLp<T>::Add_BFS(const NFSupport &p_support,
					 /*const*/ LPSolve<T> &lp,
					 gList<BFS<T> > &p_list)
{
  BFS<T> cbfs((T) 0);

  // LPSolve<T>::GetAll() does not currently work correctly; for now,
  // LpSolve is restricted to returning only one equilibrium
  lp.OptBFS(cbfs);
  cbfs.Remove(p_support.Game().NumStrats(1)+1);
  cbfs.Remove(-p_support.Game().NumStrats(2)-1);
  if (p_list.Contains(cbfs))  return 0;
  p_list.Append(cbfs);
  return 1;
}

template <class T>
void nfgLp<T>::GetSolutions(const NFSupport &p_support,
			    const gList<BFS<T> > &p_list,
			    gList<MixedSolution > &solutions,
			    const T &p_epsilon) const
{
  int index;
  int n1 = p_support.NumStrats(1);
  int n2=p_support.NumStrats(2);
  solutions.Flush();

  for (int i = 1; i <= p_list.Length(); i++)    {
    MixedProfile<T> profile(p_support);
    int j;
    for (j = 1; j <= n1; j++) 
      if (p_list[i].IsDefined(j))   
	profile(1, j) = p_list[i](j);
      else  profile(1, j) = (T) 0;

    for (j = 1; j <= n2; j++)
      if (p_list[i].IsDefined(-j))
	profile(2, j) = p_list[i](-j);
      else
	profile(2, j) = (T) 0;

    index = solutions.Append(MixedSolution(profile, "Lp[NFG]"));
    solutions[index].SetEpsilon(p_epsilon);
  }
}