Example code to extract from SGSolution_MaxMinMax a matrix of points that characterize equilibrium payoff set?

[skranz]

Hi Ben,

as you may recall, I had written an R interface to the old SGSolve version and was thinking to try to update it to account for your new MaxMinMax algorithm (unfortunately the old algorithm gets stuck in some games I wanted to solve).

But that update is not very straightforward for me. I just wanted to ask whether you have somewhere an example for a simple two player game, that shows how I can extract from an SGSolution_MaxMinMax object a matrix of points that characterize the computed equilibrium payoff set? (I must admit that I haven't worked through to your new theoretical paper, but probably such a matrix can be obtained, or not?) It would be such a matrix, I would like to return to R.

Best wishes, Sebastian

[babrooks]

Hi Sebastian,

Thanks for the message, and your interest in the update! That's great that you are maintaining an R interface.

The new code does not produce a list of extreme points. It returns a list of inequalities that define the payoff correspondence. The SGSolution_MaxMinMax object contains a list of SGIteration_MaxMinMax objects. The last SGIteration_MaxMinMax in the list is the final approximation. Each iteration contains a list of SGStep objects, each of which contains a SGHyperplane. The SGHyperplane contains a direction and a vector of levels, where there is one level for each state. The correspondence produced on that iteration is the intersection of the half spaces below the hyperplanes in the SGSteps.

I should add that each SGStep object also contains a "pivot", which is a SGTuple. These are the payoffs that were used to define the levels, although they are not necessarily payoffs that can be generated, so they may not be contained in the approximation. (Incidentally, the same was true of the points that were produced by the earlier program.)

For an example of how to access the data, you could look at the MATLAB file sgmex2.cpp, or you could look at the file sgsolutionhandler_v2.cpp, in particular the function plotSolution. You could write something like this:

... SGSolution_MaxMinMax soln = solver.getSolution(); for (auto it = soln.getIterations().back().getSteps().cbegin(); it != soln.getIterations().back().getSteps().cend(); ++it) { cout << "Direction: " << it->getHyperplane()->getNormal() << ", levels: "; for(int s = 0; s < soln.getGame().getNumStates(); s++) cout << it->getHyperplane().getLevels()[s] << ", "; cout << endl; }

This code should just print the hyperplanes for the last iteration to cout.

I hope this helps. The new code is more robust so I hope it will work better on your games. Also, I am hoping to release an update this week that fixes a bunch of bugs, delete deprecated code, and rename things in a much more sensible manner.

Cheers,

B

On Sat, Sep 7, 2019 at 4:23 AM Sebastian Kranz notifications@github.com wrote:

Hi Ben,

as you may recall, I had written an R interface to the old SGSolve version and was thinking to try to update it to account for your new MaxMinMax algorithm (unfortunately the old algorithm gets stuck in some games I wanted to solve).

But that update is not very straightforward for me. I just wanted to ask whether you have somewhere an example for a simple two player game, that shows how I can extract from an SGSolution_MaxMinMax object a matrix of points that characterize the computed equilibrium payoff set? (I must admit that I haven't worked through to your new theoretical paper, but probably such a matrix can be obtained, or not?) It would be such a matrix, I would like to return to R.

Best wishes, Sebastian

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/babrooks/SGSolve/issues/2?email_source=notifications&email_token=ACN5VFRV7WV73GXU5ALZSFLQINXIHA5CNFSM4IUPOVT2YY3PNVWWK3TUL52HS4DFUVEXG43VMWVGG33NNVSW45C7NFSM4HJ6FWGA, or mute the thread https://github.com/notifications/unsubscribe-auth/ACN5VFW6MMWYUBJANTNGXVLQINXIHANCNFSM4IUPOVTQ .

--

Ben Brooks Assistant Professor Department of Economics University of Chicago babrooks@uchicago.edu www.benjaminbrooks.net

[skranz]

Hi Ben,

thanks a lot for your detailed explanation, which is very helpful. By adapting your example, I managed to extract the relevant values and return them to R. Furthermore, I have tried to update my geometric knowledge and developed a first algorithm to compute the corner points of the relevant half-spaces intersection for 2 player games. Currently it is pure R code, but if you have not yet implemented such an algorithm but think it is useful to have in SGSolve, I could write a C++ version and send it to you.

Just some more questions:

In the simple example game I looked at so far, the area described by the pivot points looks visually the same than the half space intersection. Do you know whether in general the pivot points provide a good outer approximation of the equilibrium payoff set that is just some tolerance away from the halfspace intersection? Or could it be that in some examples the area described by the pivot points is way off from the true payoff set? In the former case, maybe I just omit all half space intersection stuff and return the pivots. Is there a difference how good the pivots approximate the equilibrium payoff set between your 2016 and 2019 algorithms? My old R interface just uses the 2016 algorithm and returns the pivots, is that roughly ok?

When computing the half space intersections, I get many corner points that are almost identical, and probably differ only due to numerical inaccuracies. In the end I have much more corner points but the area looks visually the same than the area spanned by the fewer pivots. I don't know whether the following sentences make sense in this context: This suggests to me that at least for some states some hyperplanes intersections are sort of irrelevant / redundant. Is there a simple indicator that tells me ex-ante that for some states I can ignore some hyperplane intersections?

Best wishes, Sebastian

[babrooks]

Hi Sebastian,

I would be very happy to include code to do the intersections. I have generally done this step in MATLAB. I wrote the code to do it a long time ago. If I remember correctly, it is basically a convex hull operation, using point/hyperplane duality, and the points end up corresponding to faces of the dual polytope. Is this how you approached it? MATLAB has a built-in interface to qhull that black boxes the convex hull step.

Each optimal payoff must be outside the intersection, but I do not know whether the convex hull of the optimal payoffs is equal to the intersection (or even if it contains the intersection). There are definitely examples with strict containment. For example, in a PD at a high discount factor, the algorithm could use the flow payoff from (C,D) or (D,C) as the optimal payoff for some directions. There is a tie between that payoff and the best binding payoff for those actions. The program will select one in basically an arbitrary manner. It can definitely also happen that the convex hull of the optimal payoffs is equal to the intersection. This would necessarily be the case if incentive constraints bind in the first period of the optimal equilibrium in every direction, e.g., in a Cournot game with a relatively low discount factor so that the minmax payoff can't be attained in equilibrium. I would not be surprised if there are examples with non-containment, but I don't have one to suggest off the top of my head.

In the 2016 paper, the trajectory of the pivots has to asymptotically trace out the equilibrium payoff correspondence. So in that case, it is legitimate to use the pivots themselves as the approximation.

There may be some redundancy. Basically, the theory tells us there is a finite collection of candidate face directions. The program throws out most of these candidates as being clearly not face directions, but it does not weed out all of the redundant directions. Some of them are just added to the list. In a future version, it would be nice to do more weeding of face directions (even though the redundant directions are harmless with regard to computing new binding payoffs). The new draft (which I will hopefully post in the next week) is clearer on this point.

I hope this helps!

All the best,

B

On Wed, Sep 11, 2019 at 2:01 AM Sebastian Kranz notifications@github.com wrote:

Hi Ben,

thanks a lot for your detailed explanation, which is very helpful. By adapting your example, I managed to extract the relevant values and return them to R. Furthermore, I have tried to update my geometric knowledge and developed a first algorithm to compute the corner points of the relevant half-spaces intersection for 2 player games. Currently it is pure R code, but if you have not yet implemented such an algorithm but think it is useful to have in SGSolve, I could write a C++ version and send it to you.

Just some more questions:

In the simple example game I looked at so far, the area described by the pivot points looks visually the same than the half space intersection. Do you know whether in general the pivot points provide a good outer approximation of the equilibrium payoff set that is just some tolerance away from the halfspace intersection? Or could it be that in some examples the area described by the pivot points is way off from the true payoff set? In the former case, maybe I just omit all half space intersection stuff and return the pivots. Is there a difference how good the pivots approximate the equilibrium payoff set between your 2016 and 2019 algorithms? My old R interface just uses the 2016 algorithm and returns the pivots, is that roughly ok?

When computing the half space intersections, I get many corner points that are almost identical, and probably differ only due to numerical inaccuracies. In the end I have much more corner points but the area looks visually the same than the area spanned by the fewer pivots. I don't know whether the following sentences make sense in this context: This suggests to me that at least for some states some hyperplanes intersections are sort of irrelevant / redundant. Is there a simple indicator that tells me ex-ante that for some states I can ignore some hyperplane intersections?

Best wishes, Sebastian

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/babrooks/SGSolve/issues/2?email_source=notifications&email_token=ACN5VFT4X55DWQPG76EDU53QJCJUNA5CNFSM4IUPOVT2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD6NPTZA#issuecomment-530250212, or mute the thread https://github.com/notifications/unsubscribe-auth/ACN5VFS2L5KCTBD7526FATTQJCJUNANCNFSM4IUPOVTQ .

--

Ben Brooks Assistant Professor Department of Economics University of Chicago babrooks@uchicago.edu www.benjaminbrooks.net