rahulsavani
commented
8 years ago Here is an extension that would use these different linear combinations of player's payoffs
The below comes from the Game Theory Explorer project and was offered as an idea for the Google Summer of Code in previous years.
For a game, the set of correlated equilibria is a convex polytope. For a two-player game, the set of its payoffs is a two-dimensional polygon. This is useful information to draw as a first picture of which equilibrium payoffs can be expected. One can use the above code to two-player strategic-form as input and draw the polygon of correlated equilibrium payoffs.
The "variables" of the CE polytope are the probabilities of a joint distribution over strategy profiles. Linear inequalities that define this polytope are "incentive constraints" that compare any two strategies of a player, and are derived from the payoffs of the game. Consequently, one can maximize a linear function over this polytope by linear programming, for example any linear combination of the players' payoffs.
In a two-player game, the possible payoffs for the two players in a CE define a polygon. (For three players, they define a polytope of dimension three, and so on.) These payoffs give useful information about the game, for example which Nash equilibrium payoffs - which are special CE payoffs - can at most be expected. What is unknown about the polygon are its vertices. The following picture shows a polygon with 7 vertices numbered 1,2,...,7.
In this figure, if the horizontal direction is the payoff to player 1 and the vertical direction is the payoff to player 2, then vertices 5 and 1 are the CE with maximum (minimum) payoff to player 1, vertices 2 and 3 give maximum payoff to player 2, and vertex 6 gives minimum payoff to player 2.
How can one identify the vertices when the only access to the polygon is via maximizing linear functions of the two coordinates? By trying out different directions intelligently. Maximizing in direction x gives vertex 2, maximizing in direction y gives vertex 3. If the linear function z that is orthogonal to the line that connects 2 and 3 is maximized at both 2 and 3, then there is no further vertex between them. For comparison, suppose direction w is maximized at 5. Then the line that connects 3 and 5 gives a direction (not shown) that is not maximized at both 3 and 5, but instead yields another vertex 4.
Extending this to 3 players is a whole new challenge, and would require interfacing with 3D-drawing programs.
An optimal correlated equilibrium is optimal according to some linear combination of all probabilities.
Current linear combination: The coefficient of an outcome its probability variable is the sum of the payoff values for all players in that outcome. This way, the result from the LP will be the correlated equilibrium that is best for the group i.e. the sum of all players their expected payoff in the equilibrium is optimized.
TO DO: Let user choose what linear combination to use. (e.g. maybe user is more interested in finding a correlated equilibrium where the expected payoff of a certain player is optimized instead of the full group. Another example could be that the user is interested in an correlated equilibrium where the probability of a certain outcome is optimized.)