nfdommix.imp

Gambit 是一个游戏库理论软件

//
// $Source: /home/gambit/CVS/gambit/sources/game/nfdommix.imp,v $
// $Date: 2002/08/26 05:50:09 $
// $Revision: 1.2 $
//
// DESCRIPTION:
// Compute dominated mixed strategies on normal forms
//
// 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/gnullstatus.h"

template <class T>
bool ComputeMixedDominated(const NFSupport &S, NFSupport &R,
			   int pl, bool strong, T /*junk*/,
			   gOutput &tracefile, gStatus &status)
{
  Nfg nfg = S.Game();
  NfgContIter s(S);

  s.Freeze(pl);
  double d1,d2;
  d1 = (double)(pl-1)/(double)S.Game().NumPlayers();
  d2 = (double)pl/(double)S.Game().NumPlayers();
  
  gArray<bool> dom(S.NumStrats(pl));
  
  T eps;
  gEpsilon(eps);
  
  gVector<T> dominator(S.NumStrats(pl));
  
  int st,i,k,n;
  
  if (strong)   {
    T COpt;
    bool ret = false;
    int strats = S.NumStrats(pl);
    int contingencies = 1;
    for(k=1;k<=nfg.NumPlayers();k++)
      if(k!=pl) contingencies*=S.NumStrats(k);
    
    gMatrix<T> A(1,contingencies+1,1,strats);
    gVector<T> B(1,contingencies+1);
    gVector<T> C(1,strats);
    
    n = contingencies + 1;
    for (k = 1; k < strats; k++) {
      C[k] = (T) 0;
      A(n, k) = (T) 1;
    }
    A(n, k) = (T) 0;
    B[n] = (T) 1;
    C[k] = (T) 1;
    
    s.First();
    for (n = 1; n <= contingencies; n++) {
      s.Set(pl, 1);
      B[n] = -nfg.Payoff(s.GetOutcome(), pl);
      for (k = 2; k <= strats; k++) {
	s.Set(pl, k);
	A(n, k - 1) = -nfg.Payoff(s.GetOutcome(), pl);
      }
      A(n, strats) = (T) 1;
      s.NextContingency();
    }
    
    for (k = 1; k <= strats; k++) {
      status.Get();
      double s1 = (double)k/(double)(strats);
      status.SetProgress((1.0-s1)*d1 + s1*d2);
      // tracefile << '\n' << (gRectArray<T> &)A << '\n';
      // tracefile << B << '\n';
      // tracefile << C << '\n';
      LPSolve<T> Tab(A, B, C, 1, status);
      
      COpt = Tab.OptimumCost();
      tracefile << "\nPlayer = " << pl << " Strat = "<< k;
      // tracefile << " F = " << Tab.IsFeasible();
      // tracefile << " x = " << Tab.OptimumVector();
      // tracefile << " Obj = " << COpt;
      
      dom[k] = false;
      
      if (Tab.IsFeasible() && COpt > eps) {
	tracefile << " Strongly Dominated by ";
	gVector<T> xx(Tab.OptimumVector());
	for(i=1,st=1;st<=strats;st++) {
	  if(st==k) dominator[st] = (T)0;
	  else {
	    dominator[st] = xx[i];
	    i++;
	  }
	}
	tracefile << dominator;
	ret = true;
	dom[k] = true;
      }
      if (k<strats)
	A.SwitchColumn(k,B);
    }
    // tracefile << "\n";
    
    if (!ret) 
      return false;
    
    for (k = 1; k <= strats; k++)
      if (dom[k])
	R.RemoveStrategy(S.Strategies(pl)[k]);
    
    return true;
  }
  else  {    // look for weak domination
    T C0 = (T) 0, COpt, TmpC;
    bool ret = false;
    int strats = S.NumStrats(pl);
    int contingencies = 1;
    for(k=1;k<=nfg.NumPlayers();k++)
      if(k!=pl) contingencies*=S.NumStrats(k);
    
    gMatrix<T> A(1,contingencies+1,1,strats-1);
    gVector<T> B(1,contingencies+1);
    gVector<T> C(1,strats-1);
    
    n=contingencies+1;
    for(k=1;k<strats;k++) {
      C[k] = (T) 0;
      A(n,k)=(T) 1;
    }
    B[n]=(T)1;
    
    s.First();
    for(n=1;n<=contingencies;n++) {
      s.Set(pl, 1);
      B[n]=-nfg.Payoff(s.GetOutcome(), pl);
      C0 -= B[n];
      for(k=2;k<=strats;k++) {
	s.Set(pl,k);
	A(n,k-1)=-nfg.Payoff(s.GetOutcome(), pl);
	C[k-1]-=A(n,k-1);
      }
      s.NextContingency();
    }
    
    for (k = 1; k <= strats; k++) {
      status.Get();
      double s1 = (double)k/(double)(strats);
      status.SetProgress((1.0-s1)*d1 + s1*d2);
      // tracefile << '\n' << (gRectArray<T> &)A << '\n';
      // tracefile << B << '\n';
      // tracefile << C << '\n';
      LPSolve<T> Tab(A, B, C, 1, status);
      
      COpt = Tab.OptimumCost();
      tracefile << "\nPlayer = " << pl << " Strat = "<< k;
      // tracefile << " F = " << Tab.IsFeasible();
      // tracefile << " x = " << Tab.OptimumVector();
      // tracefile << " Obj = " << COpt;
      
      dom[k] = false;
      
      if (Tab.IsFeasible() && (COpt >= C0-eps && COpt <=C0+eps))
	tracefile << " Duplicated strategy? ";
      else if (Tab.IsFeasible() && COpt > C0+eps) {
	tracefile << " Weakly Dominated by ";
	gVector<T> xx(Tab.OptimumVector());
	for(i=1,st=1;st<=strats;st++) {
	  if(st==k) dominator[st] = (T)0;
	  else {
	    dominator[st] = xx[i];
	    i++;
	  }
	}
	tracefile << dominator;
	ret = true;
	dom[k] = true;
      }
      // else  tracefile << "\n\n";
      if(k<strats) {
	A.SwitchColumn(k,B);
	TmpC=C0; C0=C[k]; C[k]=TmpC;
      }
      
    }
    // tracefile << "\n";
    
    if (!ret) 
      return false;
    
    for (k = 1; k <= strats; k++)
      if (dom[k])
	R.RemoveStrategy(S.Strategies(pl)[k]);
    
    return true;
  }
  
}

template <class T>
bool IsMixedDominated(const NFSupport &S,Strategy *str,
			   bool strong, T /*junk*/,
			   gOutput &tracefile)
{
  int pl = str->Player()->GetNumber();
  Nfg nfg = str->Player()->Game();
  int whichstrat = str->Number();
  int strats = S.NumStrats(pl);

  NfgContIter s(S);
  s.Freeze(pl);
  
  
  T eps;
  gEpsilon(eps);
  
  gVector<T> dominator(S.NumStrats(pl));
  
  int st,i,k,n;
  bool ret = false;
  int contingencies = 1;
  for(k=1;k<=nfg.NumPlayers();k++)
    if(k!=pl) contingencies*=S.NumStrats(k);
  
  
  if (strong)   {
    T COpt;
    gMatrix<T> A(1,contingencies+1,1,strats);
    gVector<T> B(1,contingencies+1);
    gVector<T> C(1,strats);
    
    n = contingencies + 1;
    for (k = 1; k < strats; k++) {
      C[k] = (T) 0;
      A(n, k) = (T) 1;
    }
    A(n, k) = (T) 0;
    B[n] = (T) 1;
    C[k] = (T) 1;
    
    s.First();
    for (n = 1; n <= contingencies; n++) {
      s.Set(pl, whichstrat);
      B[n] = -nfg.Payoff(s.GetOutcome(), pl);
      for (k = 1; k <= strats; k++) 
	if(k< whichstrat) {
	  s.Set(pl, k);
	  A(n, k) = -nfg.Payoff(s.GetOutcome(), pl);
	}
	else if (k > whichstrat) {
	  s.Set(pl, k);
	  A(n, k - 1) = -nfg.Payoff(s.GetOutcome(), pl);
	}
      A(n, strats) = (T) 1;
      s.NextContingency();
    }
    
    // tracefile << '\n' << (gRectArray<T> &)A << '\n';
    // tracefile << B << '\n';
    // tracefile << C << '\n';
    gNullStatus status;
    LPSolve<T> Tab(A, B, C, 1, status);
    COpt = Tab.OptimumCost();
    tracefile << "\nPlayer = " << pl << " Strat = "<< whichstrat;
    // tracefile << " F = " << Tab.IsFeasible();
    // tracefile << " x = " << Tab.OptimumVector();
    // tracefile << " Obj = " << COpt;
    
    if (Tab.IsFeasible() && COpt > eps) {
      tracefile << " Strongly Dominated by ";
      gVector<T> xx(Tab.OptimumVector());
      for(i=1,st=1;st<=strats;st++) {
	if(st==whichstrat) dominator[st] = (T)0;
	else {
	  dominator[st] = xx[i];
	  i++;
	}
      }
      tracefile << dominator;
      ret = true;
    }
    // tracefile << "\n";
    
    if (!ret) 
      return false;
    
    return true;
  }
  else  {    // look for weak domination
    T C0 = (T) 0, COpt;

    gMatrix<T> A(1,contingencies+1,1,strats-1);
    gVector<T> B(1,contingencies+1);
    gVector<T> C(1,strats-1);
    
    n=contingencies+1;
    for(k=1;k<strats;k++) {
      C[k] = (T) 0;
      A(n,k)=(T) 1;
    }
    B[n]=(T)1;
    
    s.First();
    for(n=1;n<=contingencies;n++) {
      s.Set(pl, whichstrat);
      B[n]=-nfg.Payoff(s.GetOutcome(), pl);
      C0 -= B[n];
      for(k=1;k<=strats;k++) 
	if(k<whichstrat) {
	  s.Set(pl,k);
	  A(n,k)=-nfg.Payoff(s.GetOutcome(), pl);
	  C[k]-=A(n,k);
	}
	else if (k > whichstrat) {
	  s.Set(pl,k);
	  A(n,k-1)=-nfg.Payoff(s.GetOutcome(), pl);
	  C[k-1]-=A(n,k-1);
	}
      s.NextContingency();
    }
    
    // tracefile << '\n' << (gRectArray<T> &)A << '\n';
    // tracefile << B << '\n';
    // tracefile << C << '\n';
    gNullStatus status;
    LPSolve<T> Tab(A, B, C, 1, status);
    
    COpt = Tab.OptimumCost();
    tracefile << "\nPlayer = " << pl << " Strat = "<< whichstrat;
    // tracefile << " F = " << Tab.IsFeasible();
    // tracefile << " x = " << Tab.OptimumVector();
    // tracefile << " Obj = " << COpt;
    
    if (Tab.IsFeasible() && (COpt >= C0-eps && COpt <=C0+eps))
      tracefile << " Duplicated strategy? ";
    else if (Tab.IsFeasible() && COpt > C0+eps) {
      tracefile << " Weakly Dominated by ";
      gVector<T> xx(Tab.OptimumVector());
      for(i=1,st=1;st<=strats;st++) {
	if(st==whichstrat) dominator[st] = (T)0;
	else {
	  dominator[st] = xx[i];
	  i++;
	}
      }
      tracefile << dominator;
      ret = true;
    }
    // else  tracefile << "\n\n";
    // tracefile << "\n";
    
    if (!ret) 
      return false;
    
    return true;
  }
  
}

#include "game/mixed.h"

template <class T>
bool IsMixedDominated(const MixedProfile<T> &pr, int pl,
		      bool strong, gOutput &tracefile)
{
  NFSupport S = pr.Support();
  Nfg nfg = pr.Game();
  int strats = S.NumStrats(pl);
  gVector<T> prob = pr.GetRow(pl);
  assert( prob.Length() == strats);

  NfgContIter s(S);
  s.Freeze(pl);
  
  
  T eps,x;
  gEpsilon(eps);
  
  gVector<T> dominator(S.NumStrats(pl));
  
  int st,i,k,n;
  bool ret = false;
  int contingencies = 1;
  for(k=1;k<=nfg.NumPlayers();k++)
    if(k!=pl) contingencies*=S.NumStrats(k);
  
  
  if (strong)   {
    T COpt;
    gMatrix<T> A(1,contingencies+1,1,strats+1);
    gVector<T> B(1,contingencies+1);
    gVector<T> C(1,strats+1);
    
    n = contingencies + 1;
    for (k = 1; k <= strats; k++) {
      C[k] = (T) 0;
      A(n, k) = (T) 1;
    }
    A(n, k) = (T) 0;
    B[n] = (T) 1;
    C[k] = (T) 1;
    
    s.First();
    for (n = 1; n <= contingencies; n++) {
      B[n]=(T)0;
      for(int j=1;j<=strats;j++) {
	s.Set(pl, j);
	T x1 = nfg.Payoff(s.GetOutcome(), pl);
	T x2 = prob[j];
	x = -x1*x2;
	// x = - ((T)nfg.Payoff(s.GetOutcome(), pl))*((T)prob[j]);
	B[n] += -nfg.Payoff(s.GetOutcome(), pl);
      }
      for (k = 1; k <= strats; k++) {
	s.Set(pl, k);
	A(n, k) = -nfg.Payoff(s.GetOutcome(), pl);
      }
      A(n, strats+1) = (T) 1;
      s.NextContingency();
    }
    // tracefile << '\n' << (gRectArray<T> &)A << '\n';
    // tracefile << B << '\n';
    // tracefile << C << '\n';
    gNullStatus status;
    LPSolve<T> Tab(A, B, C, 1, status);
    COpt = Tab.OptimumCost();
    tracefile << "\nPlayer = " << pl << " Strat: " << prob;
    // tracefile << " F = " << Tab.IsFeasible();
    // tracefile << " x = " << Tab.OptimumVector();
    // tracefile << " Obj = " << COpt;
    
    if (Tab.IsFeasible() && COpt > eps) {
      tracefile << " Strongly Dominated by ";
      gVector<T> xx(Tab.OptimumVector());
      for(i=1,st=1;st<=strats;st++) {
	dominator[st] = xx[i];
	i++;
      }
      tracefile << dominator;
      ret = true;
    }
    // tracefile << "\n";
    
    if (!ret) 
      return false;
    
    return true;
  }
  else  {    // look for weak domination
    T C0 = (T) 0, COpt;

    gMatrix<T> A(1,contingencies+1,1,strats);
    gVector<T> B(1,contingencies+1);
    gVector<T> C(1,strats);
    
    n=contingencies+1;
    for(k=1;k<=strats;k++) {
      C[k] = (T) 0;
      A(n,k)=(T) 1;
    }
    B[n]=(T)1;
    
    s.First();
    for(n=1;n<=contingencies;n++) {
      B[n]=(T)0;
      for(int j=1;j<=strats;j++) {
	s.Set(pl, j);
	T x1 = nfg.Payoff(s.GetOutcome(), pl);
	T x2 = prob[j];
	x = - x1 * x2;
	// x=-nfg.Payoff(s.GetOutcome(), pl)*prob[j];
	B[n]+=x;
	C0 -= x;
      }
      for(k=1;k<=strats;k++) {
	s.Set(pl,k);
	x=-nfg.Payoff(s.GetOutcome(), pl);
	A(n,k)=x;
	C[k]-=x;
      }
      s.NextContingency();
    }
    
    // tracefile << '\n' << (gRectArray<T> &)A << '\n';
    // tracefile << B << '\n';
    // tracefile << C << '\n';
    gNullStatus status;
    LPSolve<T> Tab(A, B, C, 1, status);
    
    COpt = Tab.OptimumCost();
    tracefile << "\nPlayer = " << pl << " Strat: " << prob;
    // tracefile << " F = " << Tab.IsFeasible();
    // tracefile << " x = " << Tab.OptimumVector();
    // tracefile << " Obj = " << COpt;
    
    //if (Tab.IsFeasible() && (COpt >= C0-eps && COpt <=C0+eps))
    //  tracefile << " Duplicated strategy? ";
    // else 
    if (Tab.IsFeasible() && COpt > C0+eps) {
      tracefile << " Weakly Dominated by ";
      gVector<T> xx(Tab.OptimumVector());
      for(i=1,st=1;st<=strats;st++) {
	dominator[st] = xx[i];
	i++;
      }
      tracefile << dominator;
      ret = true;
    }
    // else  tracefile << "\n\n";
    // tracefile << "\n";
    
    if (!ret) 
      return false;
    
    return true;
  }
}