edu.princeton.repeatedgames.rgsolve
Class RGSolve

java.lang.Object
  extended by edu.princeton.repeatedgames.rgsolve.RGSolve
All Implemented Interfaces:
java.io.Serializable

public class RGSolve
extends java.lang.Object
implements java.io.Serializable

This class contains the heart of the rgsolve package. It implements the Abreu-Sannikov operator and solves the games. One instantiates the solver with a game and then calls its solve method.

See Also:
Serialized Form

Nested Class Summary
private  class RGSolve.RecursiveActionLoop
          Class for parallelizing the generation extreme points, by partitioning the action space.
 
Field Summary
private  int[] BR1
          m2-length vector of player 1 best responses
private  int[] BR2
          m1-length vector of player 2 best responses
static int BYTES_PER_MB
          bits per megabyte
private  double delta
          local reference to discount factor
private  boolean doMultiThread
          Does this solver parallelize?
private  Game game
          The repeated game associated with this instance of the solver
private  boolean innerApprox
          A boolean on whether this solver is for inner approximations.
private  int m1
          local reference to number of player 1 actions
private  int m2
          local reference to number of player 2 actions
private  AlgoParameters params
          the parameters/settings associated with this instance of the solver
private static int PLAYER_1
          player 1 index (0) for code
private static int PLAYER_2
          player 2 index (1) for code
private  RGSolveProgressUpdater progressUpdater
          An instance implementing RGSolveProgressUpdater that tells RGSolve where to print status updates
private static long serialVersionUID
          Serialization ID
(package private)  java.util.ArrayList<GameExtremePoint> staticNashPayoffs
          As a safety precaution, we add in the static pure strategy nash equilibria on every iteration to make sure we don't miss them
private  BitSetFixed usableActions
          The usable action profiles; is modified as unsupportable actions are dropped
private  boolean useRectangleW0
          Use a rectangle containing feasible set as W0 rather than hull of feasible payoffs
 
Constructor Summary
RGSolve(Game game)
          Constructor using rgsolve default parameters, and which prints status updates to the console
RGSolve(Game game, AlgoParameters params)
          Constructor using user-passed-in parameters params, and which prints status updates to the console
RGSolve(Game game, AlgoParameters params, RGSolveProgressUpdater progressUpdater)
          Constructor using user-passed-in parameters params, and which prints status updates to progressUpdater
 
Method Summary
 GameExtremePoint[] AbreuSannikovOperator(GameExtremePoint[] W, Point u, RGIter rg_iter)
          This applies the Abreu-Sannikov (or APS) operator to a set.
 double bestResponseProfit(int a1, int a2, int player)
           
 boolean g_a_enforceable(int a1, int a2, Point u, int player)
           
private  java.util.List<GameExtremePoint> generateSupportedPayoffs(int startAct, int endAct, GameExtremePoint[] W, Point u, RGIter rg_iter, int xmin_n, int xmin_s, int ymin_e, int ymin_w, int xmax_n, int xmax_s, int ymax_e, int ymax_w, double minXVal, double maxXVal, double minYVal, double maxYVal)
          A helper method within the Abreu-Sannikov (or APS) operator for calculating potential extreme points supported by actions in the range startAct to endAct.
 int[] getBR1()
          Returns the value of the field called 'bR1'.
 int[] getBR2()
          Returns the value of the field called 'bR2'.
static int getBytesPerMb()
          Returns the value of the field called 'bytesPerMb'.
 double getDelta()
          Returns the value of the field called 'delta'.
 Game getGame()
          Returns the value of the field called 'game'.
 int getM1()
          Returns the value of the field called 'm1'.
 int getM2()
          Returns the value of the field called 'm2'.
 AlgoParameters getParams()
          Returns the value of the field called 'params'.
static Point getPunishment(GameExtremePoint[] W, Point curPunishment)
          Gets the current threat point given payoff set W and old threat point curPunishment
 RGSolveProgressUpdater getRggui_interface()
          Returns the value of the field called 'rggui_interface'.
static long getSerialversionuid()
          Returns the value of the field called 'serialversionuid'.
 BitSetFixed getUsableActions()
          Returns the value of the field called 'usableActions'.
private  void initializeObject(Game game, AlgoParameters params, RGSolveProgressUpdater progressUpdater)
          Initializes all rgsolve-object data
 boolean isDoMultiThread()
          Returns the value of the field called 'doMultiThread'.
static boolean isWithin(double x1, double x2, double epsilon)
          Helper method which tells if x1 and x2 are within epsilon of one another
 java.lang.String outputFormat(double d, int digits)
          A helper method which converts a double d into a String, where digits many digits are kept.
 boolean setDiscount(double delta)
          Sets the discount factor in the solver and its associated game
 void setInnerApprox(boolean innerApprox)
          Sets whether this solver is doing inner approximation methods.
 void setParameters(AlgoParameters params)
          Sets new AlgoParameters in the solver
 RGSolution solveGame()
          Solves the game held in this solver object
 RGSolution solveGame(Point[] W_initial, Point punishment)
          Solves the game held in this solver object, using an initial guess of V*, W_initial
static RGSolution staticSolveGame(Game game)
          Solves the game statically (no RGSolve object) using rgsolve default parameters, and which prints status updates to the console
static RGSolution staticSolveGame(Game game, AlgoParameters params)
          Solves the game statically (no RGSolve object) and which prints status updates to the console
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

PLAYER_1

private static final int PLAYER_1
player 1 index (0) for code

See Also:
Constant Field Values

PLAYER_2

private static final int PLAYER_2
player 2 index (1) for code

See Also:
Constant Field Values

serialVersionUID

private static final long serialVersionUID
Serialization ID

See Also:
Constant Field Values

BYTES_PER_MB

public static final int BYTES_PER_MB
bits per megabyte

See Also:
Constant Field Values

doMultiThread

private boolean doMultiThread
Does this solver parallelize?


useRectangleW0

private boolean useRectangleW0
Use a rectangle containing feasible set as W0 rather than hull of feasible payoffs


game

private Game game
The repeated game associated with this instance of the solver


params

private AlgoParameters params
the parameters/settings associated with this instance of the solver


delta

private double delta
local reference to discount factor


m1

private int m1
local reference to number of player 1 actions


m2

private int m2
local reference to number of player 2 actions


BR1

private int[] BR1
m2-length vector of player 1 best responses


BR2

private int[] BR2
m1-length vector of player 2 best responses


usableActions

private BitSetFixed usableActions
The usable action profiles; is modified as unsupportable actions are dropped


progressUpdater

private RGSolveProgressUpdater progressUpdater
An instance implementing RGSolveProgressUpdater that tells RGSolve where to print status updates


innerApprox

private boolean innerApprox
A boolean on whether this solver is for inner approximations. In inner approximation mode, no actions are ever dropped.


staticNashPayoffs

java.util.ArrayList<GameExtremePoint> staticNashPayoffs
As a safety precaution, we add in the static pure strategy nash equilibria on every iteration to make sure we don't miss them

Constructor Detail

RGSolve

public RGSolve(Game game)
Constructor using rgsolve default parameters, and which prints status updates to the console

Parameters:
game -

RGSolve

public RGSolve(Game game,
               AlgoParameters params)
Constructor using user-passed-in parameters params, and which prints status updates to the console

Parameters:
game - the game to solve
params - user parameters

RGSolve

public RGSolve(Game game,
               AlgoParameters params,
               RGSolveProgressUpdater progressUpdater)
Constructor using user-passed-in parameters params, and which prints status updates to progressUpdater

Parameters:
game - the game to solve
params - user parameters
progressUpdater - where to print progress updates
Method Detail

staticSolveGame

public static RGSolution staticSolveGame(Game game)
Solves the game statically (no RGSolve object) using rgsolve default parameters, and which prints status updates to the console

Parameters:
game -
Returns:
an RGSolution representing the solution to the game

staticSolveGame

public static RGSolution staticSolveGame(Game game,
                                         AlgoParameters params)
Solves the game statically (no RGSolve object) and which prints status updates to the console

Parameters:
game -
params -
Returns:
an RGSolution representing the solution to the game

initializeObject

private void initializeObject(Game game,
                              AlgoParameters params,
                              RGSolveProgressUpdater progressUpdater)
Initializes all rgsolve-object data

Parameters:
game - the StageGame in question
params - the parameters of the algorithm
progressUpdater - a GUI for showing algo progress (possibly null)

solveGame

public RGSolution solveGame()
Solves the game held in this solver object

Returns:
an RGSolution representing the solution to the game

solveGame

public RGSolution solveGame(Point[] W_initial,
                            Point punishment)
Solves the game held in this solver object, using an initial guess of V*, W_initial

Parameters:
W_initial - A set containing V*. If null, use the hull of feasible payoffs.
punishment - the starting punishment to use (can be null)
Returns:
an object representing the solution to the game

AbreuSannikovOperator

public GameExtremePoint[] AbreuSannikovOperator(GameExtremePoint[] W,
                                                Point u,
                                                RGIter rg_iter)
This applies the Abreu-Sannikov (or APS) operator to a set.

Parameters:
W - a vector of GameExtremePoints representing the current payoff set
u - the current threat point
rg_iter - an object representing the current iteration data structure
Returns:
B(W), where B is the Abreu-Sannikov operator (or APS operator)

g_a_enforceable

public boolean g_a_enforceable(int a1,
                               int a2,
                               Point u,
                               int player)
Parameters:
a1 - player 1 action
a2 - player 2 action
u - "punishment" payoff profile u = {u1,u2};
player - the player to check the IC for
Returns:
true iff action a = (a1,a2) is enforceable with punishment u for player 1

bestResponseProfit

public double bestResponseProfit(int a1,
                                 int a2,
                                 int player)
Parameters:
a1 - action of player 1
a2 - action of player 2
player - who we are calculating deviation for
Returns:
the stage profit available to player from deviating

getPunishment

public static Point getPunishment(GameExtremePoint[] W,
                                  Point curPunishment)
Gets the current threat point given payoff set W and old threat point curPunishment

Parameters:
W - current payoff set
curPunishment - old threat point
Returns:
pointwise minimum of W set, joined with curPunishment

isWithin

public static boolean isWithin(double x1,
                               double x2,
                               double epsilon)
Helper method which tells if x1 and x2 are within epsilon of one another

Parameters:
x1 -
x2 -
epsilon -
Returns:
Math.abs(x1-x2) < epsilon

outputFormat

public java.lang.String outputFormat(double d,
                                     int digits)
A helper method which converts a double d into a String, where digits many digits are kept. The method decides whether absolute or scientitific notation is more informative.

Parameters:
d -
digits -
Returns:
A String of the double d

setParameters

public void setParameters(AlgoParameters params)
Sets new AlgoParameters in the solver

Parameters:
params - new settings

setDiscount

public boolean setDiscount(double delta)
Sets the discount factor in the solver and its associated game

Parameters:
delta - new discount factor
Returns:
if the assignment is succesful

getSerialversionuid

public static long getSerialversionuid()
Returns the value of the field called 'serialversionuid'.

Returns:
Returns the serialversionuid.

getBytesPerMb

public static int getBytesPerMb()
Returns the value of the field called 'bytesPerMb'.

Returns:
Returns the bytesPerMb.

isDoMultiThread

public boolean isDoMultiThread()
Returns the value of the field called 'doMultiThread'.

Returns:
Returns the doMultiThread.

getGame

public Game getGame()
Returns the value of the field called 'game'.

Returns:
Returns the game.

getParams

public AlgoParameters getParams()
Returns the value of the field called 'params'.

Returns:
Returns the params.

getDelta

public double getDelta()
Returns the value of the field called 'delta'.

Returns:
Returns the delta.

getM1

public int getM1()
Returns the value of the field called 'm1'.

Returns:
Returns the m1.

getM2

public int getM2()
Returns the value of the field called 'm2'.

Returns:
Returns the m2.

getBR1

public int[] getBR1()
Returns the value of the field called 'bR1'.

Returns:
Returns the bR1.

getBR2

public int[] getBR2()
Returns the value of the field called 'bR2'.

Returns:
Returns the bR2.

getUsableActions

public BitSetFixed getUsableActions()
Returns the value of the field called 'usableActions'.

Returns:
Returns the usableActions.

getRggui_interface

public RGSolveProgressUpdater getRggui_interface()
Returns the value of the field called 'rggui_interface'.

Returns:
Returns the rggui_interface.

generateSupportedPayoffs

private java.util.List<GameExtremePoint> generateSupportedPayoffs(int startAct,
                                                                  int endAct,
                                                                  GameExtremePoint[] W,
                                                                  Point u,
                                                                  RGIter rg_iter,
                                                                  int xmin_n,
                                                                  int xmin_s,
                                                                  int ymin_e,
                                                                  int ymin_w,
                                                                  int xmax_n,
                                                                  int xmax_s,
                                                                  int ymax_e,
                                                                  int ymax_w,
                                                                  double minXVal,
                                                                  double maxXVal,
                                                                  double minYVal,
                                                                  double maxYVal)
A helper method within the Abreu-Sannikov (or APS) operator for calculating potential extreme points supported by actions in the range startAct to endAct. It takes the set of feasible continuations to be W and uses the punishment threat point u

Parameters:
startAct - the starting action
endAct - the ending action
W - the feasible continuation set
u - the current threat point
rg_iter - the RGIter storing information on this iteration
xmin_n - the northernmost index of the point with the smallest x-coordinate in the polygon W
xmin_s - the southernmost index of the point with the smallest x-coordinate in the polygon W
ymin_e - the easternmost index of the point with the smallest y-coordinate in the polygon W
ymin_w - the westernmost index of the point with the smallest y-coordinate in the polygon W
xmax_n - the northernmost index of the point with the largest x-coordinate in the polygon W
xmax_s - the southernmost index of the point with the largest x-coordinate in the polygon W
ymax_e - the easternmost index of the point with the largest y-coordinate in the polygon W
ymax_w - the westernmost index of the point with the largest y-coordinate in the polygon W
minXVal - the smallest x-coordinate in the polygon W
maxXVal - the largest x-coordinate in the polygon W
minYVal - the smallest y-coordinate in the polygon W
maxYVal - the largest y-coordinate in the polygon W
Returns:
potential extreme points supported by actions in the range startAct to endAct

setInnerApprox

public void setInnerApprox(boolean innerApprox)
Sets whether this solver is doing inner approximation methods.

Parameters:
innerApprox -