#\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
#\\ 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";
|
|
You can make a dinner by passing a permutation to Dinner(). You won't use this one, so don't worry about it.
f = Dinner(Permutations(4).random_element()); f
An ethiopian Dinner having 4 morsels: {(4, 2), (1, 3), (3, 1), (2, 4)}
An ethiopian Dinner having 4 morsels: {(4, 2), (1, 3), (3, 1), (2, 4)}
|
You can make a dinner by passing a set of pairs to Dinner().
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)}
An ethiopian Dinner having 7 morsels: {(7, 3), (6, 7), (4, 6), (1, 5), (3, 4), (5, 2), (2, 1)}
|
You can make a random dinner by inputting just the number of morsels you desire.
h = Dinner(5); h
An ethiopian Dinner having 5 morsels: {(4, 5), (5, 1), (3, 3), (1, 4),
(2, 2)}
An ethiopian Dinner having 5 morsels: {(4, 5), (5, 1), (3, 3), (1, 4), (2, 2)}
|
You can check on the size of the dinner and its morsels.
g.is_even()
False False |
f.is_even()
True True |
g.morsels()
{(7, 3), (6, 7), (4, 6), (1, 5), (3, 4), (5, 2), (2, 1)}
{(7, 3), (6, 7), (4, 6), (1, 5), (3, 4), (5, 2), (2, 1)}
|
g.size()
7 7 |
You can ask for the next move according to crossout.
g.crossout_move()
(6, 7) (6, 7) |
You can obtain a list of all attainable scores for the dinner. This is cached so it only takes a long time the first time you call it for a given dinner.
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)}
{(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)}
|
You can debug and see what it's doing for the more complicated functions by adding in "verbose=True".
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)
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)
|
f.all_scores(verbose=True)
Subset {(4, 2), (1, 3)} has score [5, 5]
Subset {(4, 2), (3, 1)} has score [7, 7]
Subset {(4, 2), (2, 4)} has score [6, 4]
Subset {(1, 3), (3, 1)} has score [4, 6]
Subset {(1, 3), (2, 4)} has score [3, 3]
Subset {(3, 1), (2, 4)} has score [5, 5]
{(7, 7), (6, 4), (3, 3), (4, 6), (5, 5)}
Subset {(4, 2), (1, 3)} has score [5, 5]
Subset {(4, 2), (3, 1)} has score [7, 7]
Subset {(4, 2), (2, 4)} has score [6, 4]
Subset {(1, 3), (3, 1)} has score [4, 6]
Subset {(1, 3), (2, 4)} has score [3, 3]
Subset {(3, 1), (2, 4)} has score [5, 5]
{(7, 7), (6, 4), (3, 3), (4, 6), (5, 5)}
|
This will show a pretty picture of the attainable scores.
g.show_all_scores()
{(7, 3), (6, 7), (4, 6), (1, 5), (3, 4), (5, 2), (2, 1)}
{(7, 3), (6, 7), (4, 6), (1, 5), (3, 4), (5, 2), (2, 1)}
|
You can compute the scores attainable in matchups against Crossout.
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)}
{(16, 17), (15, 13), (12, 14), (13, 18), (18, 16), (14, 15), (13, 11), (17, 12), (15, 19), (16, 14), (14, 22), (15, 17)}
|
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)}
{(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)}
|
The command show_all() will compute all the scores, and show them, colour-coded by whether they can be attained by matchups against Crossout. The crossout-crossout matchup is always in red. Black is not attainable by any matchup against Crossout. Orange is attainable if Bob plays Alice's crossout. Blue-green is attainable if Alice plays Bob's crossout. And the brownish ones (a blend of orange and blue-green) are attainable in both these ways.
g.show_all()
{(7, 3), (6, 7), (4, 6), (1, 5), (3, 4), (5, 2), (2, 1)}
{(7, 3), (6, 7), (4, 6), (1, 5), (3, 4), (5, 2), (2, 1)}
|
You can check if Crossout for a given game is Pareto optimal, weakly Pareto optimal, or a Nash equilibrium.
g.is_pareto()
True True |
g.is_weak_pareto()
True True |
g.is_nash()
True True |
Here are some bigger examples of games.
e = Dinner(16); e.show_all_scores()
{(2, 16), (10, 11), (14, 13), (6, 2), (1, 6), (11, 4), (15, 14), (8, 5),
(3, 3), (4, 15), (5, 7), (16, 1), (7, 10), (13, 9), (9, 12), (12, 8)}
{(2, 16), (10, 11), (14, 13), (6, 2), (1, 6), (11, 4), (15, 14), (8, 5), (3, 3), (4, 15), (5, 7), (16, 1), (7, 10), (13, 9), (9, 12), (12, 8)}
|
p = Dinner(8); p.show_all()
{(6, 4), (7, 1), (5, 7), (1, 8), (2, 3), (4, 2), (8, 6), (3, 5)}
{(6, 4), (7, 1), (5, 7), (1, 8), (2, 3), (4, 2), (8, 6), (3, 5)}
|
q = Dinner(9); q.show_all()
{(6, 4), (1, 3), (4, 9), (5, 7), (2, 1), (8, 8), (9, 6), (7, 2), (3, 5)}
{(6, 4), (1, 3), (4, 9), (5, 7), (2, 1), (8, 8), (9, 6), (7, 2), (3, 5)}
|
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)}
{(10, 5), (5, 7), (3, 3), (7, 6), (6, 10), (2, 1), (8, 8), (1, 9), (9, 4), (4, 2)}
|
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)}
{(4, 10), (5, 4), (6, 11), (12, 12), (7, 7), (11, 3), (8, 8), (2, 2), (9, 6), (1, 1), (10, 9), (3, 5)}
|
There are a few global functions for checking various things over all games of a given size.
for i in range(1,6): #excludes 6, i.e. 1...5
check_pareto(i)
'Done' 'Done' 'Done' 'Done' 'Done' 'Done' 'Done' 'Done' 'Done' 'Done' |
for i in range(1,6): #excludes 6, i.e. 1...5
check_weak_pareto(i)
'Done' 'Done' 'Done' 'Done' 'Done' 'Done' 'Done' 'Done' 'Done' 'Done' |
for i in range(1,6): #excludes 6, i.e. 1...5
check_nash(i)
'Done' 'Done' 'Done' 'Done' 'Done' 'Done' 'Done' 'Done' 'Done' 'Done' |
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'
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'
|
check_weak_pareto(6)
'Done' 'Done' |
check_nash(6)
'Done' 'Done' |
Now you can play around yourself. Please find bugs!
|
|