Ethiopian Dinner V1.0
system:sage


{{{id=1|
#\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
#\\ SAGE Class for Ethiopian Dinner Game   v. 1.0                      \\
#\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
#\\ Lionel Levine  and  Katherine E. Stange                            \\
#\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
#\\ This is a class for use in SAGE which implements ethiopian dinner  \\
#\\ games.                                                             \\
#\\                                                                    \\
#\\ For info, see http://math.katestange.net or contact                \\
#\\ <math at katestange dot net> or <levine at math dot mit dot edu>.  \\
#\\                                                                    \\
#\\ An ethiopian dinner (a "game") is a set of tuples (a,b)            \\
#\\ representing morsels, where a is the value of the morsel to Alice  \\
#\\ and b is the value of the morsel to Bob.  We use the convention    \\
#\\ that Bob always goes last, so that the first player depends on the \\
#\\ parity of the number of morsels in the game.                       \\
#\\                                                                    \\
#\\ Feel free to distribute this script.  If you alter it, add a       \\
#\\ description of the alteration.  Acknowledge the original version.  \\
#\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

from sage.sets.set import is_Set

class Dinner:
    """An ethiopian dinner game."""

    my_crossout_score = None;
    my_all_scores = None;
    my_is_pareto = None;
    my_is_weak_pareto = None;
    my_crossout_move = None;
    my_bob_vs_crossout = None;
    my_alice_vs_crossout = None;
    my_is_nash = None;


    ##########################################
    ### The initialisation and representation
    ##########################################

    def __init__(self, *indata):
        if isinstance(indata[0], sage.rings.integer.Integer):
            n = indata[0];
            self.my_size = indata[0];
            p = Permutations(n).random_element();
            G = Set( [] );
            for i in range(1,n+1):
                G = G.union( Set( [ tuple([i,p(i)]) ] ) );
            self.my_morsels = G;
        elif type(indata[0]) == sage.combinat.permutation.Permutation_class:
	    n = len(indata[0]);
            G = Set( [] );
            for i in range(1,n+1):
                G = G.union( Set( [ tuple([i,indata[0](i)]) ] ) );
            self.my_morsels = G;
            self.my_size = n;
        elif is_Set(indata[0]):
            self.my_morsels = indata[0];
            self.my_size = indata[0].cardinality();
        else:
            print "Input an integer (for a random game of that size), a permutation, or a set of tuples."
        if self.my_size % 2 == 0:
            self.my_is_even = True;
            self.my_is_odd = False;
        else:
            self.my_is_even = False;
            self.my_is_odd = True;

    def __repr__(self):
	return "An ethiopian Dinner having %s morsels: %s" % (self.size(), self.morsels())




    ####################################
    ### The following are user functions
    ####################################

    def morsels(self):
	### Returns the morsels of the game as a set of tuples.
	return self.my_morsels

    def size(self):
        ### Returns the size of the game (number of morsels).
        return self.my_size

    def is_even(self):
        ### Returns True if the game is of even size (Alice goes first).
        return self.my_is_even

    def is_odd(self):
        ### Returns True if the game is of odd size (Bob goes first).
        return self.my_is_odd

    def crossout_score(self, verbose=False):
        ### Returns the score of this game played Crossout-vs-Crossout
        if verbose or self.my_crossout_score is None:
            self.my_crossout_score = self.crossout_score_internal(0, 0, verbose);
            return self.my_crossout_score;
        else:
            return self.my_crossout_score;

    def all_scores(self, verbose=False):
        ### Returns all possible scores
        if verbose or (self.my_all_scores is None):
            self.my_all_scores = self.all_scores_internal(verbose);
            return self.my_all_scores;
        else:
            return self.my_all_scores;

    def is_pareto(self):
        ### Returns True if the game is Pareto optimal
        if self.my_is_pareto is None:
            self.is_pareto_internal();
            return self.my_is_pareto;
        else:
            return self.my_is_pareto;

    def is_weak_pareto(self):
        ### Returns True if the game is weakly Pareto optimal
        if self.my_is_pareto is None:
            self.is_pareto_internal();
            return self.my_is_weak_pareto;
        else:
            return self.my_is_weak_pareto;

    def crossout_move(self, verbose=False):
        ### Returns the first player's next move according to crossout
        if verbose or self.my_crossout_move is None:
            self.my_crossout_move = self.crossout_move_internal(verbose);
            return self.my_crossout_move;
        else:
            return self.my_crossout_move;

    def bob_vs_crossout(self, verbose=False):
        ### Returns the set of scores of all games played against Alice's crossout
        if verbose or self.my_bob_vs_crossout is None:
            self.my_bob_vs_crossout = self.bob_vs_crossout_internal(verbose);
            return self.my_bob_vs_crossout;
        else:
            return self.my_bob_vs_crossout;

    def alice_vs_crossout(self, verbose=False):
        ### Returns the set of scores of all games played against Bob's crossout
        if self.my_alice_vs_crossout is None:
            self.my_alice_vs_crossout = self.alice_vs_crossout_internal(verbose);
            return self.my_alice_vs_crossout;
        else:
            return self.my_alice_vs_crossout;

    def is_nash(self):
        ### Returns True if the game is a Nash equilibrium for both players
        if self.my_is_nash is None:
            self.my_is_nash = self.is_nash_internal();
            return self.my_is_nash;
        else:
            return self.my_is_nash;

    def show_all_scores(self):
        print self.morsels();
        return self.set_show(self.all_scores(),"blue");
    
    def show_bob_vs_crossout(self):
        print self.morsels();
        return self.set_show(self.bob_vs_crossout(),"orange");
  
    def show_alice_vs_crossout(self):
        print self.morsels();
        return self.set_show(self.alice_vs_crossout(),"orange");
    
    def show_all(self):
        print self.morsels();
        b = self.bob_vs_crossout();
        a = self.alice_vs_crossout();
        p1 = self.set_show(self.all_scores(),"black");
        p2 = self.set_show(b,"orange");
        p3 = self.set_show(a,Color("green").lighter().lighter());
        p4 = self.set_show(b.intersection(a),Color("green").lighter().lighter().blend(Color("orange"),0.55));
        return(show(p1+p2+p3+p4,aspect_ratio=1));




    ####################################################
    ### The following are meant to be internal functions
    ####################################################
   
    def crossout_score_internal(self, ascore, bscore, verbose=False):
        g = self.morsels();
        if verbose:
            print "The game is: ", g, ", with Alice's score: ", ascore, ", and Bob's score: ", bscore, ".";
        if g.cardinality() == 0:
            return [ascore, bscore];
        m = g.an_element();
        for i in g:
            if i[0] < m[0]:
                m = i;
        minset = Set([m]);
        if verbose:
            print "Alice crosses off: ", m, "and Bob gets ", m[1], "points.";
        bscore = bscore + m[1];
        g = g.symmetric_difference(minset);
        #print "The remaining game is: ", g;
        if g.cardinality() == 0:
            return [ascore, bscore];
        m = g.an_element();
        for i in g:
            if i[1] < m[1]:
                m = i;
        minset = Set([m]);
        if verbose:
            print "Bob crosses off: ", m, "and Alice gets ", m[0], "points.";
        ascore = ascore + m[0];
        g = g.symmetric_difference(minset);
        if verbose:
	    	print "Current score: ", [ascore, bscore];
        return( Dinner(g).crossout_score_internal(ascore, bscore, verbose) );

    def all_scores_internal(self, verbose=False):
        g = self.morsels();
        s = self.size();
        if s%2 == 0:
	    	s = s/2;
        else:
	    	s = (s-1)/2; # the number of morsels Alice eats in a game
        scoreset = Set([]);
        for r in g.subsets(s):
            ascore = 0;
            bscore = 0;
            for m in r:
                ascore = ascore + m[0];
            for m in g.symmetric_difference(r):
                bscore = bscore + m[1];
            if verbose:
                print "Subset ", r, "has score", [ascore, bscore];
            scoreset = scoreset.union(Set([tuple([ascore,bscore])]));
        return(scoreset);

    def is_pareto_internal(self):
        g = self.morsels();
        scores = self.all_scores();
        c = self.crossout_score();
        self.my_is_pareto = True;
        self.my_is_weak_pareto = True;
        for s in scores:
            if s[0] > c[0] and s[1] >= c[1]:
                self.my_is_pareto = False;
            if s[1] > c[1] and s[0] >= c[0]:
                self.my_is_pareto = False;
            if s[0] > c[0] and s[1] > c[1]:
                self.my_is_weak_pareto = False;
        return;

    def crossout_move_internal(self, verbose=False):
        g = self.morsels();
        if verbose:
            print "game is", g;
        m = g.an_element();
        for i in g:
            if i[0] < m[0]:
                m = i;
        minset = Set([m]);
        g = g.symmetric_difference(minset);
        if verbose:
            print "alice crossed", m, "game is", g;
        if g.cardinality() == 0:
            return m;
        m = g.an_element();
        for i in g:
            if i[1] < m[1]:
                m = i;
        minset = Set([m]);
        g = g.symmetric_difference(minset);
        if verbose:
            print "bob crossed", m, "game is", g;
        if g.cardinality() == 0:
            return m;
        return( Dinner(g).crossout_move_internal(verbose) );

    def bob_vs_crossout_internal(self, verbose=False):
        g = self.morsels();
        gsize = self.size();
        if gsize == 0:
            return(Set([tuple([0,0])]));
        ascore = 0;
        if gsize%2 == 0: # if the game is even, take Alice's move
            m = Dinner(g).crossout_move_internal();
            g = g.symmetric_difference(Set([m]));
            if verbose:
                print g;
            ascore = m[0];    
        global_scoreset = Set([]);
        for i in g:
            bscore = i[1];
            local_scoreset = Dinner(g.symmetric_difference(Set([i]))).bob_vs_crossout_internal(verbose);
            for s in local_scoreset:
                newa = s[0]+ascore;
                newb = s[1]+bscore;
                local_scoreset = local_scoreset.symmetric_difference(Set([s]));
                local_scoreset = local_scoreset.union(Set([tuple([newa,newb])]));
            if verbose:
                print "local_scoreset: ", local_scoreset;
            global_scoreset = global_scoreset.union(local_scoreset);
        return(global_scoreset);

    def alice_vs_crossout_internal(self, verbose=False):
        g = self.morsels();
        gsize = self.size();
        if gsize == 0:
            return(Set([tuple([0,0])]));
        bscore = 0;
        if gsize%2 == 1: # if the game is odd, take Bob's move
            m = Dinner(g).crossout_move_internal();
            g = g.symmetric_difference(Set([m]));
            if verbose:
                print g;
            bscore = m[1];    
        global_scoreset = Set([]);
        if g.cardinality() == 0:
            return( Set([tuple([0,bscore])]) );
        for i in g:
            ascore = i[0];
            local_scoreset = Dinner(g.symmetric_difference(Set([i]))).alice_vs_crossout_internal(verbose);
            for s in local_scoreset:
                newa = s[0]+ascore;
                newb = s[1]+bscore;
                local_scoreset = local_scoreset.symmetric_difference(Set([s]));
                local_scoreset = local_scoreset.union(Set([tuple([newa,newb])]));
            if verbose:
                print "local_scoreset: ", local_scoreset;
            global_scoreset = global_scoreset.union(local_scoreset);
        return(global_scoreset);

    def is_nash_internal(self):
        c = self.crossout_score();
        for s in self.bob_vs_crossout():
            if s[1] > c[1]:
                return False;
        for s in self.alice_vs_crossout():
            if s[0] > c[0]:
                return False;
        return True;

    def set_show(self, scores, col="blue"):
        p = sage.plot.plot.Graphics();
        for s in scores:
            p = p + point(s, color=col);
        p = p + point( self.crossout_score(), color="red");
        return(p);


################################################
### FUNCTIONS THAT YOU MIGHT USE WITH THIS CLASS
################################################

### CHECKS OVER ALL GAMES OF A GIVEN SIZE

def check_pareto(n):
    for s in Permutations(n):
        G = Dinner(s);
        if G.is_pareto() == False:
            print G;
    return "Done";

def check_weak_pareto(n):
    for s in Permutations(n):
        G = Dinner(s);
        if G.is_weak_pareto() == False:
            print G;
    return "Done";

def check_nash(n):
    for s in Permutations(n):
        G = Dinner(s);
        if G.is_nash() == False:
            print G;
    return "Done";
///
}}}

<p>You can make a dinner by passing a permutation to Dinner(). &nbsp;You won't use this one, so don't worry about it.</p>

{{{id=27|
f = Dinner(Permutations(4).random_element()); f
///
An ethiopian Dinner having 4 morsels: {(3, 2), (4, 4), (2, 3), (1, 1)}
}}}

<p>You can make a dinner by passing a set of pairs to Dinner().</p>

{{{id=19|
g = Dinner(Set([(1, 5), (6, 7), (4, 6), (7, 3), (3, 4), (5, 2), (2, 1)])); g
///
An ethiopian Dinner having 7 morsels: {(7, 3), (6, 7), (4, 6), (1, 5), (3, 4), (5, 2), (2, 1)}
}}}

<p>You can make a random dinner by inputting just the number of morsels you desire.</p>

{{{id=20|
h = Dinner(5); h
///
An ethiopian Dinner having 5 morsels: {(2, 3), (1, 5), (3, 1), (5, 2), (4, 4)}
}}}

<p>You can check on the size of the dinner and its morsels.</p>

{{{id=22|
g.is_even()
///
False
}}}

{{{id=23|
f.is_even()
///
True
}}}

{{{id=35|
g.morsels()
///
{(7, 3), (6, 7), (4, 6), (1, 5), (3, 4), (5, 2), (2, 1)}
}}}

{{{id=24|
g.size()
///
7
}}}

<p>You can ask for the next move according to crossout.</p>

{{{id=70|
g.crossout_move()
///
(6, 7)
}}}

<p>You can obtain a list of all attainable scores for the dinner. &nbsp;This is cached so it only takes a long time the first time you call it for a given dinner.</p>

{{{id=28|
g.all_scores()
///
{(11, 16), (15, 13), (8, 13), (12, 14), (10, 19), (14, 13), (10, 15), (10, 21), (6, 18), (14, 15), (12, 16), (15, 19), (11, 19), (14, 22), (16, 17), (11, 10), (12, 20), (9, 15), (16, 14), (10, 12), (8, 20), (18, 16), (13, 18), (9, 17), (17, 12), (7, 16), (15, 17), (13, 11)}
}}}

<p>You can debug and see what it's doing for the more complicated functions by adding in "verbose=True".</p>

{{{id=71|
g.crossout_move(verbose=True)
///
game is {(7, 3), (6, 7), (4, 6), (1, 5), (3, 4), (5, 2), (2, 1)}
alice crossed (1, 5) game is {(7, 3), (6, 7), (4, 6), (3, 4), (5, 2), (2, 1)}
bob crossed (2, 1) game is {(3, 4), (7, 3), (5, 2), (6, 7), (4, 6)}
game is {(3, 4), (7, 3), (5, 2), (6, 7), (4, 6)}
alice crossed (3, 4) game is {(7, 3), (5, 2), (4, 6), (6, 7)}
bob crossed (5, 2) game is {(7, 3), (6, 7), (4, 6)}
game is {(7, 3), (6, 7), (4, 6)}
alice crossed (4, 6) game is {(7, 3), (6, 7)}
bob crossed (7, 3) game is {(6, 7)}
game is {(6, 7)}
alice crossed (6, 7) game is {}
(6, 7)
}}}

{{{id=67|
f.all_scores(verbose=True)
///
Subset  {(3, 2), (4, 4)} has score [7, 4]
Subset  {(3, 2), (2, 3)} has score [5, 5]
Subset  {(3, 2), (1, 1)} has score [4, 7]
Subset  {(4, 4), (2, 3)} has score [6, 3]
Subset  {(4, 4), (1, 1)} has score [5, 5]
Subset  {(2, 3), (1, 1)} has score [3, 6]
{(7, 4), (6, 3), (4, 7), (5, 5), (3, 6)}
}}}

<p>This will show a pretty picture of the attainable scores.</p>

{{{id=29|
g.show_all_scores()
///
{(7, 3), (6, 7), (4, 6), (1, 5), (3, 4), (5, 2), (2, 1)}
<html><font color='black'><img src='cell://sage0.png'></font></html>
}}}

<p>You can compute the scores attainable in matchups against Crossout.</p>

{{{id=2|
g.bob_vs_crossout()
///
{(16, 17), (15, 13), (12, 14), (13, 18), (18, 16), (14, 15), (13, 11), (17, 12), (15, 19), (16, 14), (14, 22), (15, 17)}
}}}

{{{id=8|
g.alice_vs_crossout()
///
{(11, 16), (12, 20), (8, 13), (10, 19), (8, 20), (10, 15), (10, 21), (6, 18), (13, 18), (9, 17), (7, 16), (11, 19), (14, 22)}
}}}

<p>The command show_all() will compute all the scores, and show them, colour-coded by whether they can be attained by matchups against Crossout. &nbsp;The crossout-crossout matchup is always in red. &nbsp;Black is not attainable by any matchup against Crossout. &nbsp;Orange is attainable if Bob plays Alice's crossout. &nbsp;Blue-green is attainable if Alice plays Bob's crossout. &nbsp;And the brownish ones (a blend of orange and blue-green) are attainable in both these ways.</p>

{{{id=11|
g.show_all()
///
{(7, 3), (6, 7), (4, 6), (1, 5), (3, 4), (5, 2), (2, 1)}
<html><font color='black'><img src='cell://sage0.png'></font></html>
}}}

<p>You can check if Crossout for a given game is Pareto optimal, weakly Pareto optimal, or a Nash equilibrium.</p>

{{{id=42|
g.is_pareto()
///
True
}}}

{{{id=44|
g.is_weak_pareto()
///
True
}}}

{{{id=43|
g.is_nash()
///
True
}}}

<p>Here are some bigger examples of games.</p>

{{{id=37|
e = Dinner(16); e.show_all_scores()
///
{(7, 3), (15, 13), (12, 14), (1, 15), (16, 16), (13, 10), (11, 7), (8, 5), (6, 1), (4, 4), (2, 11), (9, 12), (3, 6), (5, 2), (14, 8), (10, 9)}
<html><font color='black'><img src='cell://sage0.png'></font></html>
}}}

{{{id=40|
p = Dinner(8); p.show_all()
///
{(3, 2), (5, 5), (7, 1), (4, 3), (1, 7), (8, 6), (2, 4), (6, 8)}
<html><font color='black'><img src='cell://sage0.png'></font></html>
}}}

{{{id=41|
q = Dinner(9); q.show_all()
///
{(6, 4), (1, 3), (4, 9), (5, 7), (2, 1), (8, 8), (9, 6), (7, 2), (3, 5)}
<html><font color='black'><img src='cell://sage0.png'></font></html>
}}}

{{{id=15|
m = Dinner(10); m.show_all()
///
{(10, 5), (5, 7), (3, 3), (7, 6), (6, 10), (2, 1), (8, 8), (1, 9), (9, 4), (4, 2)}
<html><font color='black'><img src='cell://sage0.png'></font></html>
}}}

{{{id=38|
n = Dinner(Set([(4, 10), (5, 4), (6, 11), (12, 12), (7, 7), (11, 3), (8, 8), (2, 2),
(9, 6), (1, 1), (10, 9), (3, 5)])); n.show_all()
///
{(4, 10), (5, 4), (6, 11), (12, 12), (7, 7), (11, 3), (8, 8), (2, 2), (9, 6), (1, 1), (10, 9), (3, 5)}
<html><font color='black'><img src='cell://sage0.png'></font></html>
}}}

<p>There are a few global functions for checking various things over all games of a given size.</p>

{{{id=39|
for i in range(1,6): #excludes 6, i.e. 1...5
    check_pareto(i)
///
'Done'
'Done'
'Done'
'Done'
'Done'
}}}

{{{id=46|
for i in range(1,6): #excludes 6, i.e. 1...5
    check_weak_pareto(i)
///
'Done'
'Done'
'Done'
'Done'
'Done'
}}}

{{{id=47|
for i in range(1,6): #excludes 6, i.e. 1...5
    check_nash(i)
///
'Done'
'Done'
'Done'
'Done'
'Done'
}}}

{{{id=48|
check_pareto(6)
///
An ethiopian Dinner having 6 morsels: {(1, 5), (5, 4), (4, 3), (6, 6), (3, 2), (2, 1)}
An ethiopian Dinner having 6 morsels: {(6, 3), (1, 5), (3, 2), (5, 6), (4, 4), (2, 1)}
'Done'
}}}

{{{id=49|
check_weak_pareto(6)
///
'Done'
}}}

{{{id=50|
check_nash(6)
///
'Done'
}}}

<p>Now you can play around yourself. &nbsp;Please find bugs!</p>

{{{id=51|

///
}}}