lemke.imp

Gambit 是一个游戏库理论软件

//
// $Source: /home/gambit/CVS/gambit/sources/nash/lemke.imp,v $
// $Date: 2002/09/10 14:27:41 $
// $Revision: 1.3.2.1 $
//
// DESCRIPTION:
// Compute Nash equilibria via Lemke-Howson algorithm
//
// This file is part of Gambit
// Copyright (c) 2002, The Gambit Project
//
// 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 "base/base.h"
#include "math/gpvector.h"

#include "game/nfg.h"

#include "lemke.h"
template <class T> gMatrix<T> Make_A1(const Nfg &, const NFSupport &, 
				      const T &);
template <class T> gVector<T> Make_b1(const Nfg &, const NFSupport &, 
				      const T &);
template <class T> gMatrix<T> Make_A2(const Nfg &, const NFSupport &,
				      const T &);
template <class T> gVector<T> Make_b2(const Nfg &, const NFSupport &,
				      const T &);


//---------------------------------------------------------------------------
//                        nfgLcp: member functions
//---------------------------------------------------------------------------

template <class T> 
gList<MixedSolution> nfgLcp<T>::Solve(const NFSupport &p_support,
				      gStatus &p_status)
{
  BFS<T> cbfs((T) 0);

  if (p_support.Game().NumPlayers() != 2) {
    return gList<MixedSolution>();
  }

  gList<BFS<T> > bfsList;

  try {
    gMatrix<T> A1 = Make_A1(p_support.Game(), p_support, (T) 0);
    gVector<T> b1 = Make_b1(p_support.Game(), p_support, (T) 0);
    gMatrix<T> A2 = Make_A2(p_support.Game(), p_support, (T) 0);
    gVector<T> b2 = Make_b2(p_support.Game(), p_support, (T) 0);
    LHTableau<T> B(A1,A2,b1,b2);
    if (m_stopAfter != 1) {
      AllLemke(p_support,0,B,bfsList,m_maxDepth, p_status);
    }
    else  {
      B.LemkePath(1);
      AddBfs(B, bfsList);
    }

    return AddSolutions(p_support, bfsList, B.Epsilon());
  }
  catch (gSignalBreak &E) {
    // for now, we won't give *any* solutions -- but we should list
    // any solutions found!
    throw;
  }
  // any other exceptions will propagate out.
}

template <class T> int nfgLcp<T>::AddBfs(LHTableau<T> &p_tableau,
					      gList<BFS<T> > &p_list)
{
  BFS<T> cbfs((T) 0);
  cbfs = p_tableau.GetBFS();
  if ((m_stopAfter > 0 && p_list.Length() > m_stopAfter) ||
      p_list.Contains(cbfs)) {  
    return 0;
  }
  p_list.Append(cbfs);
  return 1;
}

//
// AllLemke finds all accessible Nash equilibria by recursively 
// calling itself.  List maintains the list of basic variables 
// for the equilibria that have already been found.  
// From each new accessible equilibrium, it follows
// all possible paths, adding any new equilibria to the List.  
//
template <class T> void nfgLcp<T>::AllLemke(const NFSupport &p_support,
					    int j, LHTableau<T> &B,
					    gList<BFS<T> > &p_list,
					    int depth,
					    gStatus &p_status)
{
  if (m_maxDepth != 0 && depth > m_maxDepth) {
    return;
  }

  if (!AddBfs(B, p_list)) {
    return;
  }
  
  for (int i = B.MinCol(); 
       i <= B.MaxCol() &&
       (m_stopAfter==0 || (p_list.Length()-1) < m_stopAfter);
       i++) {
    p_status.Get();
    if (i != j)  {
      int len = p_list.Length() - 1;
      double p1 = (double) len / (double) (len+1);
      double p2 = (double) (len+1) / (double) (len+2);
      double aa = (double) i / (double) (B.MaxCol() - B.MinCol());
      p_status.SetProgress(p1 + aa * (p2 - p1));
      LHTableau<T> Bcopy(B);
      Bcopy.LemkePath(i);
      AllLemke(p_support,i,Bcopy, p_list, depth+1, p_status);
    }
  }
  return;
}

template <class T>
gList<MixedSolution> nfgLcp<T>::AddSolutions(const NFSupport &p_support,
					     const gList<BFS<T> > &p_list,
					     const T &epsilon)
{
  int i,j;
  int n1 = p_support.NumStrats(1);
  int n2 = p_support.NumStrats(2);
  gList<MixedSolution> solutions;

  for (i = 1; i <= p_list.Length(); i++)    {
    MixedProfile<T> profile(p_support);
    T sum = (T) 0;

    for (j = 1; j <= n1; j++)
      if (p_list[i].IsDefined(j))   sum += p_list[i](j);

    if (sum == (T) 0)  continue;

    for (j = 1; j <= n1; j++) 
      if (p_list[i].IsDefined(j))   profile(1, j) = p_list[i](j) / sum;
      else  profile(1, j) = (T) 0;

    sum = (T) 0;

    for (j = 1; j <= n2; j++)
      if (p_list[i].IsDefined(n1 + j))  
	sum += p_list[i](n1 + j);

    if (sum == (T) 0)  continue;

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

    int index = solutions.Append(MixedSolution(profile, "Lcp[NFG]"));
    solutions[index].SetEpsilon(epsilon);
  }

  return solutions;
}

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

template <class T>
nfgLcp<T>::nfgLcp(void)
  : m_stopAfter(1), m_maxDepth(0)
{ }