Dominance-based solution concepts

dominance.py

"""
This is a first (and ugly) sketch of an implementation of 
dominance-based solution concepts according to [1], with yet
severe limitations (only works for bimatrix games, doesn't really 
support a set dominating a strategy), but it does serve as a nice 
prototype for future refinements.

[1]: http://dss.in.tum.de/files/brandt-research/dombased.pdf
"""

import itertools

class StrictDominance(object):
    def dominates(self, dom, sub, support=None):
        if support is None:
            support = dom.player.game.support_profile()
        strategies = [strategy for strategy in support if strategy.player != dom.player]
        num_player = dom.player.number
        for strategy in strategies:
            if self.outcome(dom, strategy)[num_player] <= self.outcome(sub, strategy)[num_player]:
                return False
        return True

    def outcome(self, fst, snd):
        game = fst.player.game
        number = fst.number * (fst.player.number * (len(snd.player.unrestrict().strategies) - 1) + 1) + \
                 snd.number * (snd.player.number * (len(fst.player.unrestrict().strategies) - 1) + 1)
        return game.outcomes[number]

class WeakDominance(object):
    def dominates(self, dom, sub, support=None):
        result = False
        if support is None:
            support = dom.player.game.support_profile()
        strategies = filter(lambda s: s.player != dom.player, support)#[s for s in support if s.player != dom.player]
        num_player = dom.player.number
        for strategy in strategies:
            if self.outcome(dom, strategy)[num_player] < self.outcome(sub, strategy)[num_player]:
                return False
            elif self.outcome(dom, strategy)[num_player] > self.outcome(sub, strategy)[num_player]:
                result = True
        return result

    def outcome(self, fst, snd):
        game = fst.player.game
        number = fst.number * (fst.player.number * (len(snd.player.unrestrict().strategies) - 1) + 1) + \
                 snd.number * (snd.player.number * (len(fst.player.unrestrict().strategies) - 1) + 1)
        return game.outcomes[number]

class VeryWeakDominance(object):
    def dominates(self, dom, sub, support=None):
        if support is None:
            support = dom.player.game.support_profile()
        strategies = filter(lambda s: s.player != dom.player, support)#[s for s in support if s.player != dom.player]
        num_player = dom.player.number
        for strategy in strategies:
            if self.outcome(dom, strategy)[num_player] < self.outcome(sub, strategy)[num_player]:
                return False
        return True

    def outcome(self, fst, snd):
        game = fst.player.game
        number = fst.number * (fst.player.number * (len(snd.player.unrestrict().strategies) - 1) + 1) + \
                 snd.number * (snd.player.number * (len(fst.player.unrestrict().strategies) - 1) + 1)
        return game.outcomes[number]

class Solution(object):
    """
    A D-solution (a solution according to a dominance concept D) sol is
    a support profile which satisfies two conditions:
     - no strategy in sol D-dominates another strategy in sol;
     - sol D-dominates all strategies outside sol.
       (a support profile D-dominating a strategy s means that at least
        one strategy in the support profile D-dominates s)
    """
    def check(self, support, concept):
        """
        This method checks by brute force if a given support is a 
        solution according to a given solution concept.
        """
        result = False
        for player in support.restrict().players:
            # First condition
            strategies = player.strategies #[strategy for strategy in support if strategy.player == player]
            for (dom, sub) in itertools.combinations(strategies, 2):
                if concept.dominates(sub, dom) or concept.dominates(dom, sub):
                    return False

            # Second condition
            other_strategies = [strategy for strategy in player.unrestrict().strategies if strategy not in support]
            for (dom, sub) in itertools.product(strategies, other_strategies): 
                if concept.dominates(dom, sub):
                    result = True
        return result