burlap.behavior.stochasticgames.solvers

Class CorrelatedEquilibriumSolver

java.lang.Object

burlap.behavior.stochasticgames.solvers.CorrelatedEquilibriumSolver

public class CorrelatedEquilibriumSolver
extends java.lang.Object

This class provides static methods for solving correlated equilibrium problems for Bimatrix games or values represented in a Bimatrix. Correlated equilibrium provide joint strategy for the agents to follow such that there would be no incentive for an agent to change their behavior if a referee selected a joint action accroding to the joint strategy and informed each agent of the action they should take, assuming all other agents would follow their selected action.

4 different correlated equilibrium problems can be solved: utilitarian, egalitarian, libertarian, and republican, as defined by Greenwald and Hall [1]. The utilitarian objective maximizes the sum payoff of the found joint strategy. Egalitarian maximizes the minimum player payoff. Republican maximizes the maximum player payoff. Liberatarian maximizes the payoff for a specific player. These different objectives can be specified with the CorrelatedEquilibriumSolver.CorrelatedEquilibriumObjective enumeration.

The primary method to use to get the equilibrium is the getCorrelatedEQJointStrategy(CorrelatedEquilibriumObjective, double[][], double[][]) method.

This class depends on the SCPSolver library.

1. Greenwald, Amy, Keith Hall, and Roberto Serrano. "Correlated Q-learning." ICML. Vol. 3. 2003.

Author:

James MacGlashan

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	CorrelatedEquilibriumSolver.CorrelatedEquilibriumObjective The four different equilibrium objectives that can be used: UTILITARIAN, EGALITARIAN, REPUBLICAN, and LIBERTARIAN.

Constructor Summary

Constructors

Constructor and Description
CorrelatedEquilibriumSolver()

Method Summary

Methods

Modifier and Type	Method and Description
protected static int	addCorrelatedEquilibriumMainConstraints(scpsolver.problems.LinearProgram lp, double[][] payoffRow, double[][] payoffCol, int n, int cCount) Adds the common LP constraints for the correlated equilribum problem: rationalaity constraits (no agent has a motivation to diverge from a joint policy selection), the probability of all joint action variables must sum to 1, and all joint action variables are lower bound at 0.0.
static double[][]	getCorrelatedEQJointStrategy(CorrelatedEquilibriumSolver.CorrelatedEquilibriumObjective objectiveType, double[][] payoffRow, double[][] payoffCol) Returns the correlated equilibrium joint strategy in a 2D double matrix, which represents the probability of each joint actino (where rows are player 1s actions and columns are player 2's actions).
static double[][]	getCorrelatedEQJointStrategyEgalitarian(double[][] payoffRow, double[][] payoffCol) Returns the correlated equilibrium joint strategy in a 2D double matrix for the Egalitarian objective.
static double[][]	getCorrelatedEQJointStrategyLibertarianForCol(double[][] payoffRow, double[][] payoffCol) Returns the correlated equilibrium joint strategy in a 2D double matrix for the Libertarian objective.
static double[][]	getCorrelatedEQJointStrategyLibertarianForRow(double[][] payoffRow, double[][] payoffCol) Returns the correlated equilibrium joint strategy in a 2D double matrix for the Libertarian objective.
static double[][]	getCorrelatedEQJointStrategyRepublican(double[][] payoffRow, double[][] payoffCol) Returns the correlated equilibrium joint strategy in a 2D double matrix for the Republican objective.
protected static double[][]	getCorrelatedEQJointStrategyUsingJOptimizer(double[][] payoffRow, double[][] payoffCol) Deprecated.
static double[][]	getCorrelatedEQJointStrategyUtilitarian(double[][] payoffRow, double[][] payoffCol) Returns the correlated equilibrium joint strategy in a 2D double matrix for the Utilitarian objective.
static double[]	getEgalitarianObjective(double[][] payoffRow, double[][] payoffCol) Returns the egalitarian objective for the given payoffs for the row and column player.
static double[]	getRepublicanObjective(double[][] payoffForQueryPlayer) Returns the republican/libertarian objective for the given player's payoffs that are to be maximized.
static double[]	getUtilitarianObjective(double[][] payoffRow, double[][] payoffCol) Returns the utilitarian objective for the given payoffs for the row and column player.
protected static boolean	isZeroArray(double[] a) Returns true if a if the input array is all zeros.
protected static int	jointIndex(int r, int c, int nCols) Returns the 1D array index for a given row and column of a matrix with the given number of columns.
static void	main(java.lang.String[] args)
protected static double[][]	removeZeroRows(double[][] m) Takes an input 2D double matrix and returns a new matrix will all the all zero rows removed.
static double[]	roundNegativesToZero(double[] a) Creates a new 1D double array with all negative values rounded to 0.
protected static int[]	rowCol(int i, int nCols) Returns the 2D row column index in a matrix of a given number of columns for a given 1D array index.
protected static double[][]	runLPAndGetJointActionProbs(scpsolver.problems.LinearProgram lp, int nRows, int nCols) Helper method for running the linear program optimization (after its constraints have already been set) and returning the result in the form of the 2D double matrix joint strategy.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

CorrelatedEquilibriumSolver

public CorrelatedEquilibriumSolver()

Method Detail

main

public static void main(java.lang.String[] args)

getCorrelatedEQJointStrategy

public static double[][] getCorrelatedEQJointStrategy(CorrelatedEquilibriumSolver.CorrelatedEquilibriumObjective objectiveType,
                                      double[][] payoffRow,
                                      double[][] payoffCol)

Returns the correlated equilibrium joint strategy in a 2D double matrix, which represents the probability of each joint actino (where rows are player 1s actions and columns are player 2's actions). If the @{linke CorrelatedEquilibriumSolver.CorrelatedEquilibriumObjective.LIBERTARIAN objective is selected, it will maximize with respect to the row player's payoffs and return the strategy from their perspecitve. Therefore for a combined joint strategy for each player in libertrain, this method should then be called for each player and then combined as necessary to get a final joint strategy that will be followed by the players.

Parameters:

objectiveType - the maximizing objective for the correlated equilibrium being solved.

payoffRow - the payoff for the player whose actions correspond to the rows of the matrix

payoffCol - the payoff for the player whose actions correspond to the columns of the matrix

Returns:

the correlated equilibrium joint strategy as a 2D double matrix.

getCorrelatedEQJointStrategyUtilitarian

public static double[][] getCorrelatedEQJointStrategyUtilitarian(double[][] payoffRow,
                                                 double[][] payoffCol)

Returns the correlated equilibrium joint strategy in a 2D double matrix for the Utilitarian objective.

Parameters:

payoffRow - the payoff for the player whose actions correspond to the rows of the matrix

payoffCol - the payoff for the player whose actions correspond to the columns of the matrix

Returns:

the correlated equilibrium joint strategy as a 2D double matrix.

getCorrelatedEQJointStrategyEgalitarian

public static double[][] getCorrelatedEQJointStrategyEgalitarian(double[][] payoffRow,
                                                 double[][] payoffCol)

Returns the correlated equilibrium joint strategy in a 2D double matrix for the Egalitarian objective.

Parameters:

payoffRow - the payoff for the player whose actions correspond to the rows of the matrix

payoffCol - the payoff for the player whose actions correspond to the columns of the matrix

Returns:

the correlated equilibrium joint strategy as a 2D double matrix.

getCorrelatedEQJointStrategyRepublican

public static double[][] getCorrelatedEQJointStrategyRepublican(double[][] payoffRow,
                                                double[][] payoffCol)

Returns the correlated equilibrium joint strategy in a 2D double matrix for the Republican objective.

Parameters:

payoffRow - the payoff for the player whose actions correspond to the rows of the matrix

payoffCol - the payoff for the player whose actions correspond to the columns of the matrix

Returns:

the correlated equilibrium joint strategy as a 2D double matrix.

getCorrelatedEQJointStrategyLibertarianForRow

public static double[][] getCorrelatedEQJointStrategyLibertarianForRow(double[][] payoffRow,
                                                       double[][] payoffCol)

Returns the correlated equilibrium joint strategy in a 2D double matrix for the Libertarian objective. The player payoff being used for maximization is the row player.

Parameters:

payoffRow - the payoff for the player whose actions correspond to the rows of the matrix

payoffCol - the payoff for the player whose actions correspond to the columns of the matrix

Returns:

the correlated equilibrium joint strategy as a 2D double matrix.

getCorrelatedEQJointStrategyLibertarianForCol

public static double[][] getCorrelatedEQJointStrategyLibertarianForCol(double[][] payoffRow,
                                                       double[][] payoffCol)

Returns the correlated equilibrium joint strategy in a 2D double matrix for the Libertarian objective. The player payoff being used for maximization is the column player.

Parameters:

payoffRow - the payoff for the player whose actions correspond to the rows of the matrix

payoffCol - the payoff for the player whose actions correspond to the columns of the matrix

Returns:

the correlated equilibrium joint strategy as a 2D double matrix.

runLPAndGetJointActionProbs

protected static double[][] runLPAndGetJointActionProbs(scpsolver.problems.LinearProgram lp,
                                     int nRows,
                                     int nCols)

Helper method for running the linear program optimization (after its constraints have already been set) and returning the result in the form of the 2D double matrix joint strategy.

Parameters:

lp - the linear program to be optimized

nRows - the number of rows in the bimatrix (number of player 1 actions)

nCols - the number of columns in the bimatrix (number of player 2 actions)

Returns:

a 2D double representing the joint strategy for the given linear program correlated equilibrium problem.

addCorrelatedEquilibriumMainConstraints

protected static int addCorrelatedEquilibriumMainConstraints(scpsolver.problems.LinearProgram lp,
                                          double[][] payoffRow,
                                          double[][] payoffCol,
                                          int n,
                                          int cCount)

Adds the common LP constraints for the correlated equilribum problem: rationalaity constraits (no agent has a motivation to diverge from a joint policy selection), the probability of all joint action variables must sum to 1, and all joint action variables are lower bound at 0.0. Note that depending on the objective, additional variables beyond the joint action variables may be part of the lp formulation. It is assumed that the first variables in the variable arrays are the sequnce of joint action variables and that any auxiliary variables that are necessary follow them. The parameter n is the total number of lp variables (joint actions and auxiliary).

Parameters:

lp - the lineary program to which the constraints will be added

payoffRow - the payoffs for the row player

payoffCol - the payoffs for the col player

n - the total number of lp variables

cCount - the number of constraints that have been added to the lp so far

Returns:

the new number of constraints added to the lp

getCorrelatedEQJointStrategyUsingJOptimizer

@Deprecated
protected static double[][] getCorrelatedEQJointStrategyUsingJOptimizer(double[][] payoffRow,
                                                                double[][] payoffCol)

Deprecated.

Old code for solving the utilitarian equilibrium with JOptimizer. JOptmizer is often not able to find solutions to these problems because it uses an interior point method that requires an feasible solution on the interior and in the initial stages of stochastic games VI, this may not be the case. Therefore, this code is deprecatd, but is retained for reference.

Parameters:

payoffRow - the payoffs for the row player

payoffCol - the payoffs for the col player

Returns:

the correlated equilibrium

getUtilitarianObjective

public static double[] getUtilitarianObjective(double[][] payoffRow,
                               double[][] payoffCol)

Returns the utilitarian objective for the given payoffs for the row and column player.

Parameters:

payoffRow - the row player's payoffs

payoffCol - the column player's payoffs

Returns:

the objective function as a double array of the LP variable coeffecients.

getEgalitarianObjective

public static double[] getEgalitarianObjective(double[][] payoffRow,
                               double[][] payoffCol)

Returns the egalitarian objective for the given payoffs for the row and column player.

Parameters:

payoffRow - the row player's payoffs

payoffCol - the column player's payoffs

Returns:

the objective function as a double array of the LP variable coeffecients.

getRepublicanObjective

public static double[] getRepublicanObjective(double[][] payoffForQueryPlayer)

Returns the republican/libertarian objective for the given player's payoffs that are to be maximized. The repubilican objective will use this method to solve an LP for each player. The libertarian will use this method to solve a single LP for the selected player.

Parameters:

payoffForQueryPlayer - the given player's player's payoffs that are to be maximized

Returns:

the objective function as a double array of the LP variable coeffecients.

jointIndex

protected static int jointIndex(int r,
             int c,
             int nCols)

Returns the 1D array index for a given row and column of a matrix with the given number of columns. Computed as r * nCols + c;

Parameters:

r - the row index

c - the column index

nCols - the number of columns in the matrix

Returns:

the 1D array index

rowCol

protected static int[] rowCol(int i,
           int nCols)

Returns the 2D row column index in a matrix of a given number of columns for a given 1D array index. The row is computed as i / nCols; the column is computed as i mod nCols.

Parameters:

i - the 1D array index

nCols - the number of columns in the matrix

Returns:

an int array of length 2, with a[0] = rowIndex and a[1] = columnIndex.

removeZeroRows

protected static double[][] removeZeroRows(double[][] m)

Takes an input 2D double matrix and returns a new matrix will all the all zero rows removed.

Parameters:

m - input 2D double matrix

Returns:

a new matrix will all the all zero rows removed.

isZeroArray

protected static boolean isZeroArray(double[] a)

Returns true if a if the input array is all zeros.

Parameters:

a - the input array

Returns:

true if a if the input array is all zeros; false otherwise

roundNegativesToZero

public static double[] roundNegativesToZero(double[] a)

Creates a new 1D double array with all negative values rounded to 0.

Parameters:

a - and input array

Returns:

a new 1D double array with all negative values rounded to 0.