mirror of
https://github.com/BlackLight/nash.git
synced 2025-02-11 11:03:47 +01:00
259 lines
4.8 KiB
C++
259 lines
4.8 KiB
C++
/*
|
|
* =====================================================================================
|
|
*
|
|
* Filename: nash.cpp
|
|
*
|
|
* Description: Simulation of a cooperative-competitive environemnt of individuals
|
|
* using Nash's models
|
|
*
|
|
* Version: 0.1
|
|
* Created: 31/10/2010 18:35:14
|
|
* Revision: none
|
|
* Compiler: gcc
|
|
*
|
|
* Author: BlackLight (http://0x00.ath.cx), <blacklight@autistici.org>
|
|
* Licence: GNU GPL v.3
|
|
* Company: DO WHAT YOU WANT CAUSE A PIRATE IS FREE, YOU ARE A PIRATE!
|
|
*
|
|
* =====================================================================================
|
|
*/
|
|
|
|
#include <iostream>
|
|
#include <fstream>
|
|
#include <vector>
|
|
#include "nash.h"
|
|
|
|
using std::cout;
|
|
using std::endl;
|
|
using std::vector;
|
|
using std::ifstream;
|
|
|
|
NashEnvironment::NashEnvironment ( int rows, int cols )
|
|
{
|
|
this->rows = rows;
|
|
this->cols = cols;
|
|
|
|
for ( int i=0; i < rows; i++ )
|
|
{
|
|
vector<nash_strategy> row;
|
|
|
|
for ( int j=0; j < cols; j++ )
|
|
{
|
|
row.push_back(coop);
|
|
}
|
|
|
|
matrix.push_back(row);
|
|
}
|
|
}
|
|
|
|
NashEnvironment::NashEnvironment ( const char *file )
|
|
{
|
|
vector<nash_strategy> row;
|
|
char ch;
|
|
|
|
rows = 0;
|
|
cols = 0;
|
|
|
|
ifstream in ( file );
|
|
|
|
if ( !in )
|
|
{
|
|
throw NashException("Could not open the specified file");
|
|
}
|
|
|
|
while ( !in.eof() )
|
|
{
|
|
ch = (char) in.get();
|
|
|
|
if ( ch == '\n' )
|
|
{
|
|
if ( cols == 0 )
|
|
{
|
|
cols = row.size();
|
|
} else {
|
|
if ( row.size() != 0 && cols != row.size() )
|
|
{
|
|
throw NashException("The size of the rows does not match");
|
|
}
|
|
}
|
|
|
|
if ( row.size() != 0 )
|
|
{
|
|
rows++;
|
|
matrix.push_back( row );
|
|
row.clear();
|
|
}
|
|
} else if ( ch == '.' ) {
|
|
row.push_back( coop );
|
|
} else if ( ch == 'X' ) {
|
|
row.push_back( comp );
|
|
}
|
|
}
|
|
|
|
if ( !row.empty() )
|
|
{
|
|
matrix.push_back( row );
|
|
row.clear();
|
|
}
|
|
|
|
if ( rows == 0 )
|
|
{
|
|
throw NashException("Invalid or empty strategy file");
|
|
}
|
|
}
|
|
|
|
const int
|
|
NashEnvironment::getRows()
|
|
{
|
|
return rows;
|
|
}
|
|
|
|
const int
|
|
NashEnvironment::getCols()
|
|
{
|
|
return cols;
|
|
}
|
|
|
|
void
|
|
NashEnvironment::init_costs ( double coop_coop, double coop_comp, double comp_coop, double comp_comp )
|
|
{
|
|
costs[coop][coop] = coop_coop;
|
|
costs[comp][comp] = comp_comp;
|
|
costs[comp][coop] = comp_coop;
|
|
costs[coop][comp] = coop_comp;
|
|
} /* ----- end of function nash_init_costs ----- */
|
|
|
|
void
|
|
NashEnvironment::print ()
|
|
{
|
|
for ( int i=0; i < rows; i++ )
|
|
{
|
|
for ( int j=0; j < cols; j++ )
|
|
{
|
|
cout << (( matrix[i][j] == coop ) ? "." : "X" ) << " ";
|
|
}
|
|
|
|
cout << endl;
|
|
}
|
|
} /* ----- end of function nash_print_matrix ----- */
|
|
|
|
void
|
|
NashEnvironment::update_utilities ( vector< vector< double > >& utilities )
|
|
{
|
|
for ( int x=0; x < rows; x++ )
|
|
{
|
|
for ( int y=0; y < cols; y++ )
|
|
{
|
|
utilities[x][y] = 0.0;
|
|
|
|
for ( int i = (( x == 0 ) ? x : x-1 ); i <= (( x == rows-1 ) ? x : x+1 ); i++ )
|
|
{
|
|
for ( int j = (( y == 0 ) ? y : y-1 ); j <= (( y == cols-1 ) ? y : y+1 ); j++ )
|
|
{
|
|
if ( !( x == i && y == j ))
|
|
{
|
|
utilities[x][y] += costs [matrix[x][y]] [matrix[i][j]];
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
bool
|
|
NashEnvironment::refresh_strategies ()
|
|
{
|
|
double best_utility = 0.0;
|
|
int best_x = 0, best_y = 0;
|
|
vector< vector<int> > changes;
|
|
vector< vector<double> > utilities;
|
|
|
|
for ( int i=0; i < rows; i++ )
|
|
{
|
|
vector<double> row(cols);
|
|
utilities.push_back(row);
|
|
}
|
|
|
|
update_utilities ( utilities );
|
|
|
|
for ( int x=0; x < rows; x++ )
|
|
{
|
|
for ( int y=0; y < cols; y++ )
|
|
{
|
|
best_x = x;
|
|
best_y = y;
|
|
best_utility = utilities[best_x][best_y];
|
|
|
|
for ( int i = (( x == 0 ) ? x : x-1 ); i <= (( x == rows-1 ) ? x : x+1 ); i++ )
|
|
{
|
|
for ( int j = (( y == 0 ) ? y : y-1 ); j <= (( y == cols-1 ) ? y : y+1 ); j++ )
|
|
{
|
|
if ( !( x == i && y == j ))
|
|
{
|
|
if ( utilities[i][j] > best_utility )
|
|
{
|
|
best_x = i;
|
|
best_y = j;
|
|
best_utility = utilities[best_x][best_y];
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
if ( matrix[best_x][best_y] != matrix[x][y] )
|
|
{
|
|
vector<int> pair(2);
|
|
pair[0] = x;
|
|
pair[1] = y;
|
|
changes.push_back (pair);
|
|
}
|
|
}
|
|
}
|
|
|
|
for ( int i=0; i < changes.size(); i++ )
|
|
{
|
|
matrix[changes[i][0]][changes[i][1]] = ( matrix[changes[i][0]][changes[i][1]] == coop ) ? comp : coop;
|
|
}
|
|
|
|
if ( changes.size() > 0 )
|
|
{
|
|
if ( check_loop() )
|
|
{
|
|
throw NashException ("Loop detected - No Nash's equilibrium is possible for this configuration");
|
|
}
|
|
}
|
|
|
|
visited_combinations.push_back(matrix);
|
|
return ( changes.size() > 0 );
|
|
} /* ----- end of function nash_refresh_strategies ----- */
|
|
|
|
|
|
bool
|
|
NashEnvironment::check_loop ()
|
|
{
|
|
bool found = false;
|
|
|
|
for ( int n=0; n < visited_combinations.size(); n++ )
|
|
{
|
|
found = true;
|
|
|
|
for ( int i=0; i < rows && found; i++ )
|
|
{
|
|
for ( int j=0; j < cols && found; j++ )
|
|
{
|
|
if ( matrix[i][j] != visited_combinations[n][i][j] )
|
|
{
|
|
found = false;
|
|
}
|
|
}
|
|
}
|
|
|
|
if ( found )
|
|
{
|
|
return true;
|
|
}
|
|
}
|
|
|
|
return false;
|
|
} /* ----- end of function check_loop ----- */
|
|
|