Removing Strictly Dominated Actions in Strategic Game

[robert-7]

Note:

This issue is similar to Removing Dominated Strategies in Strategic Game except it aims to address pruning a tree of strictly dominated strategies, rather than creating a new tree with "undominated" strategies.

The Idea

My question is: how should I (best) go about this? I know in the Gambit UI, you can simply select Tools > Dominance and press "remove" actions/branches that lead to bad outcomes, one level at a time (and this is done quickly). I'd like to know how to do the same in thing with the Python API after I'm done creating my tree. Heck, I'd settle for even a method that "just prunes all strictly dominated actions at once".

The Current Approach

My current approach would be to look at each at each information set in "reverse-level order". That is I'd start at the lowest row of non-terminal nodes, look at their actions, calculate the expected outcome of each action, and remove the sub-trees associated with the action in the information set that is strictly dominated. I'd then repeat the process with the information sets one level higher, and so on and so forth.

The Question

One question is: is my current approach a good way to go about it (or do am I overlooking some limitations)? Is there some built-in way that's better? Has this been done before elsewhere? If this might be the best way to go about it, then my one question is: in the pseudocode below, is my payoff variable being properly assigned?

Pseudocode

# a list of lists of infosets in reverse-level order
level_order_infosets = [...]

# the profile
profile = g.mixed_behavior_profile(rational=True)

# for each level of infosets
for level_of_infosets in level_order_infosets:
    
    # for each infoset in the level...
    for iset in level_of_infosets:
        
        # we want a list to store expected payoffs of each action
        expected_payoffs = []
	
        # for each action in an infoset
        for action in iset.actions:

            # get the expected payoff of performing this action
            expected_payoff = profile.payoff(action)
			
            # store the payoff
            expected_payoffs.append(expected_payoff)
			
        # remove actions with strictly worse payoffs, if they exist
        remove_strictly_dominated_actions(iset, expected_payoffs)

Any opinion or advice would be helpful? A screenshot of a sample of a tree I'm looking at can be seen below.

[tturocy]

First, do you mean actions or strategies - you switch back and forth in your description.

Eliminating dominated actions is tricky. It's not clear what the graphical interface does is correct in all cases, which is one of the reasons it's not implemented (yet) in Python.

What you're proposing definitely isn't right, though. You're measuring the expected payoff of an action against uniform randomisation. You actually need to iterate through all possible contingencies of actions, conditional on reaching a given information set. And that is rather messy.

The correct way to do it should be like this:

Pick an information set S and two actions A and B at S. To show A dominates B,
iterate over all pure behavior profiles. For each pure behavior profile P (that gives positive probability of reaching S), the payoff, conditional on reaching S, to playing A must be greater than the payoff, conditional on reaching S, to playing B.

[robert-7]

Hey, sorry for getting back to you so late:

Regarding the first paragraph, I want to delete ACTIONS from my game tree so that I can rid the game tree of strictly dominated strategies. For example, in the diagram listed, it's quite apparent that Rose (in the information set drawn furthest to the right) should always fold. Therefore, I want to delete the action "Rose Calls". (At this point, feel free to correct what I'm trying to say, if you can.)

That being said, if I wanted to take your approach, my understanding is this is how I'd want to go about it

# a list of lists of infosets in reverse-level order
level_order_infosets = [...]

# for each level of infosets
for level_of_infosets in level_order_infosets:
    
    # for each infoset in the level...
    for iset in level_of_infosets:

        # list of all moves
        conts = list(g.contingencies)

        # get all the contingencies that lead to iset
        relevent_conts = get_all_relevant_contingencies(conts, iset)

        # get all contingencies that involve choosing action A or action B from a player at this point
        actionA_conts = get_all_contingencies_choosing_action(relevent_conts, iset.actions[0])
        actionB_conts = get_all_contingencies_choosing_action(relevent_conts, iset.actions[1])

        # ASSUME ITS PLAYER 1'S CHOICE OF ACTION
        actionA_avg, actionB_avg = 0, 0

       # get the expected earnings for action A
        for cont in actionA_conts:
            actionA_avg += g[cont][0]
        actionA_avg = actionA_avg / len(actionA_conts)

        # get the expected earnings for action B
        for cont in actionB_conts:
            actionB_avg += g[cont][0]
        actionB_avg = actionB_avg / len(actionB_conts)

        # remove the action with a strictly worse expected payoff, if it exists
        if actionA_avg < actionB_avg:
            delete(iset.actions[0])
        elif actionA_avg > actionB_avg:
            delete(iset.actions[1])

Would this be roughly what you're implying I should do?

[tturocy]

No problem on the delay.

No, this is still veering far off path. A general suggestion: make sure you understand what you mean by the concept of "dominated" here - I'm getting the feeling you haven't internalised what the concept means.

Practical notes:

• You can't sort information sets by level in general - this is not well-defined in all game trees. In any event, you don't need it.
• Game.contingencies returns an iterator over strategy contingencies, not action contingencies.

That actually brings me to the more fundamental problem now that I have looked more closely. PureBehaviorProfile is not yet exposed in Python, which is what you need to be able to do what you're trying to do. You could write your own implementation of that, but you'd just be replicating what already exists in C++.

Unfortunately I can't give any timelines as to when PureBehaviorProfile might be wrapped and exposed. In a perfect world it would be soon, but this year I've been stuck with a senior admin job that will hoover up a lot of my time for the next 4-5 years.

If anyone reading this is a bit comfortable with Cython, wants to practice their skills, and wants to have a go, I can provide guidance on getting the wrapping done - there are models in the source code that can be imitated to do it.