enum.imp

Gambit 是一个游戏库理论软件

//
// $Source: /home/gambit/CVS/gambit/sources/nash/enum.imp,v $
// $Date: 2002/09/10 14:27:41 $
// $Revision: 1.3.2.1 $
//
// DESCRIPTION:
// Compute Nash equilibria via Mangasarian's 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 "game/nfg.h"
#include "game/nfgiter.h"
#include "numerical/vertenum.h"

#include "enum.h"
#include "clique.h"


template <class T> nfgEnumMixed<T>::nfgEnumMixed(void)
  : m_stopAfter(0), m_cliques(false)
{ }

template <class T> 
gList<MixedSolution> nfgEnumMixed<T>::Solve(const NFSupport &p_support,
					    gStatus &p_status)
{
  const Nfg &nfg = p_support.Game();
  gList<gVector<T> > key1, key2;  
  gList<int> node1, node2;   // IDs of each component of the extreme equilibria

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

  NfgIter iter(p_support); 

  T min = MinPayoff(nfg) - gNumber(1);
  T max = MaxPayoff(nfg);
  T fac = ((T)1)/(max - min);

  // Construct matrices A1, A2
  gMatrix<T> A1(1, p_support.NumStrats(1), 1, p_support.NumStrats(2));
  gMatrix<T> A2(1, p_support.NumStrats(2), 1, p_support.NumStrats(1));

  for (int i = 1; i <= p_support.NumStrats(1); i++) {
    for (int j = 1; j <= p_support.NumStrats(2); j++) {
      A1(i, j) = nfg.Payoff(iter.GetOutcome(), 1) - gNumber(min);
      A2(j, i) = nfg.Payoff(iter.GetOutcome(), 2) - gNumber(min);
      A1(i, j) *= fac;
      A2(j, i) *= fac;
      iter.Next(2);
    }
    iter.Next(1);
  }

  // Construct vectors b1, b2
  gVector<T> b1(1, p_support.NumStrats(1)), b2(1, p_support.NumStrats(2));
  b1 = (T) -1;
  b2 = (T) -1;

  // enumerate vertices of A1 x + b1 <= 0 and A2 x + b2 <= 0
  p_status.SetProgress(0.0);
  p_status << "Step 1 of 3: Enumerating vertices for player 1";

  VertEnum<T> poly1(A1, b1, p_status);

  p_status.SetProgress(0.0);
  p_status << "Step 2 of 3: Enumerating vertices for player 2";

  VertEnum<T> poly2(A2, b2, p_status);

  p_status.SetProgress(0.0);
  p_status << "Step 3 of 3: Searching for equilibria";
  
  const gList<BFS<T> > &verts1(poly1.VertexList());
  const gList<BFS<T> > &verts2(poly2.VertexList());
  int v1 = verts1.Length();
  int v2 = verts2.Length();

  gArray<int> vert1id(v1);
  gArray<int> vert2id(v2);
  for (int i = 1; i <= vert1id.Length(); vert1id[i++] = 0);
  for (int i = 1; i <= vert2id.Length(); vert2id[i++] = 0);

  int i = 0;
  int id1 = 0, id2 = 0;

  for (int i2 = 2; 
       i2 <= v2 &&
	 (m_stopAfter == 0 || solutions.Length() < m_stopAfter);
       i2++) {
    p_status.Get();
    BFS<T> bfs1 = verts2[i2];
    p_status.SetProgress((double) (i-2) / (double) v2);
    i++;
    for (int i1 = 2; 
	 i1 <= v1 &&
	   (m_stopAfter==0 || solutions.Length() < m_stopAfter);
	 i1++) {
      BFS<T> bfs2 = verts1[i1];
      
      // check if solution is nash 
      // need only check complementarity, since it is feasible
      bool nash = true;
      for (int k = 1; nash && k <= p_support.NumStrats(1); k++) {
	if (bfs1.IsDefined(k) && bfs2.IsDefined(-k)) {
	  nash = nash && EqZero(bfs1(k) * bfs2(-k));
	}
      }

      for (int k = 1; nash && k <= p_support.NumStrats(2); k++) {
	if (bfs2.IsDefined(k) && bfs1.IsDefined(-k)) {
	  nash = nash && EqZero(bfs2(k) * bfs1(-k));
	}
      }

      if (nash) {
	MixedProfile<T> profile(p_support);
	T sum = (T) 0;
	for (int k = 1; k <= p_support.NumStrats(1); k++) {
	  profile(1, k) = (T) 0;
	  if (bfs1.IsDefined(k)) {
	    profile(1,k) = -bfs1(k);
	    sum += profile(1,k);
	  }
	} 

	for (int k = 1; k <= p_support.NumStrats(1); k++) {
	  if (bfs1.IsDefined(k)) { 
	    profile(1,k) /= sum;
	  }
	}

	sum = (T) 0;
	for (int k = 1; k <= p_support.NumStrats(2); k++) {
	  profile(2,k) = (T) 0;
	  if (bfs2.IsDefined(k)) {
	    profile(2,k) =-bfs2(k);
	    sum += profile(2,k);
	  }
	} 
	
	for (int k = 1; k <= p_support.NumStrats(2); k++) {
	  if (bfs2.IsDefined(k)) { 
	    profile(2,k) /= sum;
	  }
	}

	int index = solutions.Append(MixedSolution(profile, "EnumMixed[NFG]")); 
	//    solutions[index].SetEpsilon(eps);
    
	// note:  The keys give the mixed strategy associated with each node.  
	//        The keys should also keep track of the basis
	//        As things stand now, two different bases could lead to
	//        the same key... BAD!
	if (vert1id[i1] == 0) {
	  id1++;
	  vert1id[i1] = id1;
	  key2.Append(profile.GetRow(2));
	}
	if (vert2id[i2] == 0) {
	  id2++;
	  vert2id[i2] = id2;
	  key1.Append(profile.GetRow(1));
	}
	node1.Append(vert2id[i2]);
	node2.Append(vert1id[i1]);
      }
    }

  }
  return solutions;
}

template <class T> bool nfgEnumMixed<T>::EqZero(const T &x) const
{
  T eps;
  gEpsilon(eps, 12);
  return (x <= eps && x >= -eps);
}     

#ifdef UNUSED
template <class T> void EnumModule<T>::GetCliques(gOutput &p_stream) const
{
  int n = node1.Length();
  assert(node2.Length() == n);

  gArray<edge> edgelist(n);

  p_stream << "\nKey:\nPlayer 1:";
  for (int i = 1; i <= key1.Length(); i++) {
    p_stream << "\n" << i << ": " << key1[i];
  }
  p_stream << "\nPlayer 2:";
  for (int i = 1; i <= key2.Length(); i++) {
    p_stream << "\n" << i << ": " << key2[i];
  }
  p_stream << "\nExtreme equilibria:";
  for (int i = 1; i <= n; i++) {
    edgelist[i].node1 = node1[i];
    edgelist[i].node2 = node2[i];
    p_stream << "\n" << node1[i] << " " << node2[i];
  }
  EnumCliques clique(edgelist, v2+1, v1+1);
}

#endif  // UNUSED