######################################################################
## ThreePersonPoker.txt Save this file as  ThreePersonPoker.txt      #
# to use it stay in the                                              #
## same directory, get into Maple (by typing: maple <Enter> )        #
## and then type:  read  `ThreePersonPoker.txt` <Enter>              #
## Then follow the instructions given there                          #
##                                                                   #
## Written by Tipaluck Krityakierne, Thotsaporn "Aek" Thanatipanonda #
#and Doron Zeilberger, Rutgers University ,                          #
##  DoronZeil at gmail dot com                                       # 
######################################################################


print(`First Written: July 2024: tested for Maple 2020 `):
print(`Version  :  July 18, 2028 `):
print():
print(`This is ThreePersonPoker.txt, one of the Maple packages`):
print(`accompanying   Tipaluck Krityakierne, Thotsaporn "Aek" Thanatipanonda, and Doron Zeilberger's  article: `):
print(` von Neumann and Newman Pokers with Finite Decks`):
print(` http://sites.math.rutgers.edu/~zeilberg/tokhniot/mamarim/mamarimhtml/poker.html `):
print():
print(`The most current version is available on WWW at:`):
print(` http://sites.math.rutgers.edu/~zeilberg/tokhniot/Poker.txt .`):
print(`Please report all bugs to: DoronZeil at gmail dot com .`):
print():
print(`For general help, and a list of the MAIN functions,`):

print(` type "ezra();". For specific help type "ezra(procedure_name);" `):
print(`------------------------------`):


ezraS:=proc()
if args=NULL then

print(`The Story procedures are: `):
print(``):

else
ezra(args):

fi:


end:


ezra:=proc()
if args=NULL then

print(` ThreePersonPoker.txt: A Maple package for  investigating three player von Neumann poker`):

print(`The MAIN procedure is:  FastMNEVerbose `):


print(``):




elif nargs=1 and args[1]= FastMNEVerbose then

print(`FastMNEVerbose(n,b):`):
print(` Input: n cards and bet size b`):
print(` Output: Nothing. But print out the explanation`):
print(` of solution of 3-person poker von Neumann style`):
print(` where player1 raise/check and player2,3 call/fold`):
print(` if player1 raises.`):
print(` Try:`):
print(` FastMNEVerbose(7,2);`):

print(``):
else
 print(`There is no such thing as`, args):

fi:


end:

# First version June 27, 2024
# Solving vonNeumann model with three players
# Player 1: check/raise, player2,3: fold/call



ez:=proc(): 
print(` Main procedures with explanation: FastMNEVerbose(n,b), OptimalVerbose(b),`): 
print(` Main procedures: NE(n,b), MNE(n,b), FastMNE(n,b), Optimal(b),`): 
print(` Supporting procedures:`);
print(` Section 1: En3S1(n,S1,S2,S3,b), En3S2(n,S1,S2,S3,b), En3S3(n,S1,S2,S3,b), BR12(n,S1,S2,b), BR13(n,S1,S3,b), BR23(n,S2,S3,b),`):
print(` Section 2: Stra(n), PayTable(k,n,b), Call2(i,j,k,c), Call1(i,j,c), ListSol(S,n), CF(p), ListCF(L),     `);
print(` Section 3: NLPvn(X,Y,Z), MBR23(n,S2,S3,b), PCheck(i,n), PRaise(i,S2,S3,b), MBR12(n,S1,S2,b), PFold(k,S1,n), PCall(k,S1,S2,b),`);
print(` Section 4: PayOff1(b,A,B,C), PayOff2(b,A,B,C), ConA(b,A,B,C), ConB(b,A,B,C), ConC(b,A,B,C),  `);
end:

Digits:=15:
with(combinat):
with(simplex):
with(Optimization):

#########################
# Section 1: Search for Pure NE
#
# Functions:
# En3S1(n,S1,S2,S3,b), 
# En3S2(n,S1,S2,S3,b), En3S3(n,S1,S2,S3,b),
# BR12(n,S1,S2,b), 
# BR13(n,S1,S3,b), BR23(n,S2,S3,b),
# NE(n,b),
#
#########################

#En3S1(n,S1,S2,S3,b): inputs a positive integer n 
#and subsets S1, S2 and S3 of {1,...,n} 
#outputs the expected gain for player 1 
#if he follows startegy S1 (bet iff his card is in S1)
#and player 2,3 follows strategy S2,S3 (call iff y is in S2,S3) 
#if the bet size is b. 
# Try:
# En3S1(4,{1,2},{1,4},{2,3},2);
# En3S1(5,{1,5},{5},{5},2);
En3S1:=proc(n,S1,S2,S3,b) 

local i,x,y,z,P:

if not (n >= 3 and type(n, integer) and type(S1,set) 
and type(S2,set) and type(S3,set) 
and S1 minus {seq(i,i=1..n)}={} 
and S2 minus {seq(i,i=1..n)}={}
and S3 minus {seq(i,i=1..n)}={} ) then
    print(`bad input`):
    RETURN(FAIL):
fi:

P := 0;

for x from 1 to n do
for y in {seq(i,i=1..n)} minus {x} do
for z in {seq(i,i=1..n)} minus {x,y} do
    if member(x,S1) = false then
		P := P+Call2(x,y,z,1);
	elif member(y,S2) = false and member(z,S3) = false then
		P := P+2;
	elif member(y,S2) = true and member(z,S3) = false then
		P := P+Call1(x,y,b+1);
	elif member(y,S2) = false and member(z,S3) = true then
		P := P+Call1(x,z,b+1);
	elif member(y,S2) = true and member(z,S3) = true then
		P := P+Call2(x,y,z,b+1);
	else
		ERROR("NoCase");
	fi:	
od: od: od:						  

P/(n*(n-1)*(n-2));
end:


#En3S2(n,S1,S2,S3,b): inputs a positive integer n 
#and subsets S1,S2 and S3 of {1,...,n} 
#outputs the expected gain for player 2 
#if he follows startegy S1 (bet iff his card is in S1)
#and player 2,3 follows strategy S2,S3 (call iff y is in S2,S3) 
#if the bet size is b. 
# Try:
# En3S2(4,{1,2},{1,4},{2,3},2);
# En3S2(5,{1,5},{5},{5},2);
En3S2:=proc(n,S1,S2,S3,b) 

local i,x,y,z,P:

if not (n >= 3 and type(n, integer) and type(S1,set) 
and type(S2,set) and type(S3,set) 
and S1 minus {seq(i,i=1..n)}={} 
and S2 minus {seq(i,i=1..n)}={}
and S3 minus {seq(i,i=1..n)}={} ) then
    print(`bad input`):
    RETURN(FAIL):
fi:

P := 0;

for x from 1 to n do
for y in {seq(i,i=1..n)} minus {x} do
for z in {seq(i,i=1..n)} minus {x,y} do
    if member(x,S1) = false then
		P := P+Call2(y,x,z,1);
	elif member(y,S2) = false then
		P := P-1;
	elif member(y,S2) = true and member(z,S3) = false then
		P := P+Call1(y,x,b+1);
	elif member(y,S2) = true and member(z,S3) = true then
		P := P+Call2(y,x,z,b+1);
	else
		ERROR("NoCase");
	fi:	
od: od: od:						  

P/(n*(n-1)*(n-2));
end:


#En3S3(n,S1,S2,S3,b): inputs a positive integer n 
#and subsets S1,S2 and S3 of {1,...,n} 
#outputs the expected gain for player 3 
#if he follows startegy S1 (bet iff his card is in S1)
#and player 2,3 follows strategy S2,S3 (call iff y is in S2,S3) 
#if the bet size is b. 
# Try:
# En3S3(4,{1,2},{1,4},{2,3},2);
# En3S3(5,{1,5},{5},{5},2);
# En3S1(5,{1,5},{3,5},{1,5},2);
# En3S2(5,{1,5},{3,5},{1,5},2);
# En3S3(5,{1,5},{3,5},{1,5},2);
En3S3:=proc(n,S1,S2,S3,b) 

local i,x,y,z,P:

if not (n >= 3 and type(n, integer) and type(S1,set) 
and type(S2,set) and type(S3,set) 
and S1 minus {seq(i,i=1..n)}={} 
and S2 minus {seq(i,i=1..n)}={}
and S3 minus {seq(i,i=1..n)}={} ) then
    print(`bad input`):
    RETURN(FAIL):
fi:

P := 0;

for x from 1 to n do
for y in {seq(i,i=1..n)} minus {x} do
for z in {seq(i,i=1..n)} minus {x,y} do
    if member(x,S1) = false then
		P := P+Call2(z,x,y,1);
	elif member(z,S3) = false then
		P := P-1;
	elif member(z,S3) = true and member(y,S2) = false then
		P := P+Call1(z,x,b+1);
	elif member(z,S3) = true and member(y,S2) = true then
		P := P+Call2(z,x,y,b+1);
	else
		ERROR("NoCase");
	fi:	
od: od: od:						  

P/(n*(n-1)*(n-2));
end:


# BR12(n,S1,S2,b): Inputs n, a positive integer, 
# and a subset S1,S2 of {1,..,n} indicating 
# Player 1's,2's strategy 
# (bet if x in S1, check otherwise)
# (call if y in S2, fold otherwise), 
# Output: the set S3
# that are the best response to S1,S2. 
# b is the bet size.
# Try:
# BR12(4,{1,4},{2,4},2);
BR12:=proc(n,S1,S2,b) option remember;
local i,G,S3,Best,Pay;

Pay := -1000;
G := powerset({seq(i,i=1..n)}):

for S3 in G do
    if En3S3(n,S1,S2,S3,b) > Pay then
		Best := {S3};
		Pay := En3S3(n,S1,S2,S3,b);
	elif En3S3(n,S1,S2,S3,b) = Pay then
		Best := Best union {S3};	
	fi:
od:

[Best,Pay];
end:

# BR13(n,S1,S3,b): Inputs n, a positive integer, 
# and a subset S1,S3 of {1,..,n} indicating 
# Player 1's,3's strategy 
# (bet if x in S1, check otherwise)
# (call if z in S3, fold otherwise), 
# Output: the set S2
# that are the best response to S1,S3. 
# b is the bet size.
# Try:
# BR13(4,{1,4},{2,4},2);
BR13:=proc(n,S1,S3,b) option remember;
local i,S2,Best,Pay;

Pay := -1000;

for S2 in powerset({seq(i,i=1..n)}) do
    if En3S2(n,S1,S2,S3,b) > Pay then
        Best := {S2};
       	Pay := En3S2(n,S1,S2,S3,b);
	elif En3S2(n,S1,S2,S3,b) = Pay then
	    Best := Best union {S2};	
	fi:
od:

[Best,Pay];
end:


# BR23(n,S2,S3,b): Inputs n, a positive integer, 
# and a subset S2,S3 of {1,..,n} indicating 
# Player 2's,3's strategy 
# (call if y in S2, fold otherwise)
# (call if z in S3, fold otherwise), 
# Output: the set S1
# that are the best response to S2,S3. 
# b is the bet size.
# Try:
# BR23(4,{1,4},{2,4},2);
BR23:=proc(n,S2,S3,b) option remember;
local i,S1,Best,Pay;

Pay := -1000;

for S1 in powerset({seq(i,i=1..n)}) do
    if En3S1(n,S1,S2,S3,b) > Pay then
        Best := {S1};
       	Pay := En3S1(n,S1,S2,S3,b);
	elif En3S1(n,S1,S2,S3,b) = Pay then
	    Best := Best union {S1};	
	fi:
od:

[Best,Pay];
end:


# NE(n,b): all the "pure" Nash Equilibria [S1,S2,S3] 
# with n cards and bet size b, where S1 
# is Player 1's strategy, S2 is Player 2's strategy
# and S3 is Player 3's strategy
# Try: NE(3,2); 
# NE(4,2);
# NE(5,2);
NE:=proc(n,b)
local S1,S2,S3,G,Nash,i;

G := powerset({seq(i,i=1..n)});

Nash := {};

for S1 in G do
for S2 in G do
for S3 in G do
    if member(S3,BR12(n,S1,S2,b)[1])
	and member(S2,BR13(n,S1,S3,b)[1])
    and member(S1,BR23(n,S2,S3,b)[1]) then
    	Nash := Nash union {[S1,S2,S3,BR12(n,S1,S2,b)[2]]};
	fi:
od: od: od:

Nash;	
end:


############################
# Section 2: Helper functions
#
# Functions:
# Stra(n), PayTable(k,n,b),
# Call2(i,j,k,c), Call1(i,j,c),
# ListSol(S,n), 
# CF(p), ListCF(L),
#
############################

# Stra(n): 
# Input: positive integer n
# Output: Set of strategies of any player with n cards
# Try: Stra(3);
Stra :=proc(n) local i:
option remember;
[op(powerset({seq(i,i=1..n)}))];

end:

# PayOff table
# Input: player k (k=1,2,3), 
# number of card n and amount of bet b
# Output: Payoff table of player k 
# as a 2^n-by-2^n-by-2^n list
# Try:
# PayTable(1,3,2);
PayTable:=proc(player,n,b) option remember;
local i,j,k,A,B,C;

A := Stra(n);
B := Stra(n);
C := Stra(n);

if player =1 then
	[seq([seq([seq( En3S1(n,A[i],B[j],C[k],b)
	,k=1..nops(C))],j=1..nops(B))],i=1..nops(A))];
elif player =2 then
	[seq([seq([seq( En3S2(n,A[i],B[j],C[k],b)
	,k=1..nops(C))],j=1..nops(B))],i=1..nops(A))];
elif player =3 then
	[seq([seq([seq( En3S3(n,A[i],B[j],C[k],b)
	,k=1..nops(C))],j=1..nops(B))],i=1..nops(A))];	
else
	ERROR("NoCase");
fi:
end:

 
# Payoff of the player with card i when the 
# other two opponents make a call.
# Input: card i,j,k of P1,P2,P3 and stake c
# output: 2*c if i>j and i>k and -c if i<j or i<k
# Try: [seq(Call2(i,4,6,2),i in {1,2,3,5,7})];
Call2 := proc(i,j,k,c) option remember;

if i > j and i>k then
	return(2*c);
elif i < j or i<k then
	return(-c);
else
	ERROR("CheckInput");
fi:
end:

# Payoff of the player with card i when the 
# only one opponent makes a call (the other folds).
# Input: card i of P1, card j of P2 and stake c
# output: c+1 if i>j and -c if i<j
# Try: [seq(Call1(i,4,2),i in {1,2,3,5})];
Call1 := proc(i,j,c) option remember;

if i > j then
	return(c+1);
elif i < j then
	return(-c);
else
	ERROR("CheckInput");
fi:
end:

# For MNE
# Convert the set of Strategy solutions 
# to a list of prob. solution 
# Input: Set of Strategies S and number of cards n
# Output: 
# For Player 1: A list of n probabilities, P1 
# meaning if he gets card  x he should bet with prob. P1[x] 
# and call with prob. 1-P1[x].
# For Player 2: A list of prob. P2, meaning if he gets card y
# he should call with prob. P2[y] and fold with prob. 1-P2[y].
ListSol := proc(S,n) option remember;
local i,j,T;

# Simplify output
T := [0$n];
for i from 1 to n do
for j from 1 to nops(Stra(n)) do
	if member(i,Stra(n)[j]) then
		T[i]:=T[i]+S[j];
	fi:
od: od:

T;
end: 


# Convert to fraction
# Input: decimal numbers 
# (i.e. solutions from optimization )
# Output: convert this number to a 
# nice fraction
# Try: CF(0.06666662);
CF := proc(p) option remember;
if abs(p) < 10^(-11) then
	return(0);
fi;
convert(p,fraction,8);	
end:


# CF the whole list
# Input: List of decimal numbers
#  (i.e. solutions from optimization )
# Output: List of fractions from these 
# decimal numbers
ListCF := proc(L) option remember;
local i;
[seq(CF(L[i]),i=1..nops(L))];
end:


############################
# Section 3: Solve the discrete version
# of von Neumann 3-person game
#
# Functions:
# NLPvn(X,Y,Z), MNE(n,b),
#
# Check MNE:
# MBR23(n,S2,S3,b),
# PCheck(i,n), PRaise(i,S2,S3,b),
# MBR12(n,S1,S2,b),
# PFold(k,S1,n), PCall(k,S1,S2,b), 
#
# Fast (non-)Linear programming 
# for discrete number of cards:
# FastMNE(n,b),
#
############################

# Non-linear programming for mixed NE 
# from pay-off tables
# This is an implementation of the result 
# from the paper "A Computational Method 
# for Solving N-Person Game"
# Input: A payoff tables X,Y,Z of player1,2,3
# Output: The list of 
# 1.sum of payoffs of 3 players
# 2.list of payoffs of each player
# 3.list of strategies of each player, 
# as the list of prob. to play each set of strategy.
NLPvn := proc(X,Y,Z) option remember;
local i,j,k,n1,n2,n3,p,q,r,V,P,con1,con2,M;

if nops(X)<>nops(Y) or nops(X)<> nops(Z)
or nops(X[1])<>nops(Y[1]) or nops(X[1])<> nops(Z[1])
or nops(X[1][1])<>nops(Y[1][1]) 
or nops(X[1][1])<> nops(Z[1][1]) then
	ERROR("BadInput");
fi:	

n1 := nops(X);
n2 := nops(X[1]);
n3 := nops(X[1][1]);

P := add(V[i],i=1..3);

con1 := 
{seq(add(add( X[i][j][k]*q[j]*r[k]
,j=1..n2),k=1..n3)<=V[1],i=1..n1)} union
{seq(add(add( Y[i][j][k]*p[i]*r[k]
,i=1..n1),k=1..n3)<=V[2],j=1..n2)} union
{seq(add(add( Z[i][j][k]*p[i]*q[j]
,i=1..n1),j=1..n2)<=V[3],k=1..n3)};

con2 := {V[1]>=0,V[2]<=0,V[3]<=0
,seq(p[i]>=0,i=1..n1),seq(q[j]>=0,j=1..n2)
,seq(r[k]>=0,k=1..n3)
,add(p[i],i=1..n1)=1,add(q[j],j=1..n2)=1
,add(r[k],k=1..n3)=1};

M := Minimize(P,con1 union con2);

[M[1],subs(M[2],[V[1],V[2],V[3]])
,subs(M[2],[seq(p[i],i=1..n1)])
,subs(M[2],[seq(q[j],j=1..n2)])
,subs(M[2],[seq(r[k],k=1..n3)])];
end:

# For 3-person Poker, 
# solving for mixed Nash equilibrium 
# MNE(n,b): one "mized" Nash Equilibria [S1,S2,S3] 
# with n cards and bet size b, where S1 
# is Player 1's strategy, S2 is Player 2's strategy
# and S3 is Player 3's strategy
# Output: The list of 
# 1.sum of payoffs of 3 players
# 2.list of payoffs of each player
# 3.list of strategies of each player, i.e.
# For Player 1: A list of n probabilities, P1 
# meaning if he gets card  x he should bet with prob. P1[x] 
# and call with prob. 1-P1[x].
# For Player 2,3: A list of prob. P2,P3 meaning if he gets 
# card y,z, he should call with prob. P2[y], P3[z]
# and fold with prob. 1-P2[y], 1-P3[z].
# Try: MNE(4,1); 
MNE := proc(n,b) option remember;
local i,j,k,X,Y,Z,T,S;

X:=PayTable(1,n,b):
Y:=PayTable(2,n,b):
Z:=PayTable(3,n,b):

T := NLPvn(X,Y,Z); 
S := [T[1],T[2],ListSol(T[3],n)
,ListSol(T[4],n),ListSol(T[5],n)];

[CF(S[1]),ListCF(S[2]),S[3]
,ListCF(S[4]),ListCF(S[5])];
end: 


###################################################
# MBR23(n,S2,S3,b): Inputs n, a positive integer, 
# and a list S2,S3 of prob. indicating 
# Player 2's,3's strategy 
# (call with prob. p[y], fold otherwise)
# (call with prob. p[z], fold otherwise), 
# Output: the list S1
# that are the best response to S2,S3. 
# b is the bet size.
# (i.e. test for Mixed Nash Equilibrium)
# Try: 
# S2 := [0,0,1/4,1]:
# MBR23(4,S2,S2,1);
# S2 := [0,0,0,3/4,1]:
# MBR23(5,S2,S2,1);
# S2 := [0,0,0,3/10,1]:
# MBR23(5,S2,S2,2);
MBR23 := proc(n,S2,S3,b) option remember;
local i,S1,P;

P := 0;

if nops(S2) <> n or nops(S3) <> n then
	ERROR("BadInput");
fi:

S1 := [0$n];
for i from 1 to n do
	if abs(PRaise(i,S2,S3,b)-PCheck(i,n))< 10^(-10) then
		S1[i] := "rORc";
	elif PRaise(i,S2,S3,b) > PCheck(i,n) then
		S1[i] := "r";
	elif PRaise(i,S2,S3,b) < PCheck(i,n) then
		S1[i] := "c";
	else
		ERROR("Surprise");
	fi:	
	P := P+max(PRaise(i,S2,S3,b),PCheck(i,n));
od:

[P/n,S1];
end:


# Payoff if check 
# Input: card i and number of cards n
# Output: the payoff of player 1 if check from this card i
# Try: [seq(PCheck(i,6),i=1..6)];
PCheck := proc(i,n) option remember;
local j,k,S;

S := {seq(j,j=1..n)};

add(add(Call2(i,j,k,1),k in S minus {i,j})
,j in S minus {i})/(n-1)/(n-2);
end:

# Payoff if raise
# Input: card i, Strategy S2,S3 of player2 and 3 
# and number of cards n
# Output: the payoff of player 1 if raise from this card i
# Try: [seq(PRaise(i,S2,S3,b),i=1..5)];
PRaise := proc(i,S2,S3,b) option remember;
local n,j,k,S;

n := nops(S2);
S := {seq(j,j=1..n)};

add(add(
Call2(i,j,k,b+1)*S2[j]*S3[k]
+Call1(i,j,b+1)*S2[j]*(1-S3[k])
+Call1(i,k,b+1)*(1-S2[j])*S3[k]
+2*(1-S2[j])*(1-S3[k])
,k in S minus {i,j}),j in S minus {i})/(n-1)/(n-2);
end:


# MBR12(n,S1,S2,b): Inputs n, a positive integer, 
# and a list S1,S2 of prob. indicating 
# Player 1's,2's strategy 
# (raise with prob. p[x], call otherwise)
# (call with prob. p[y], fold otherwise), 
# Output: the list S3
# that are the best response to S1,S2. 
# b is the bet size.
# (i.e. test for Mixed Nash Equilibrium)
# Try:
# S1 := [1,0,0,0,1]: S2 := [0,0,0,6/7,1]:
# MBR12(5,S1,S2,1);
# S1 := [3/7,0,0,0,1]: S2 := [0,0,0,3/4,1]:
# MBR12(5,S1,S2,1);
# S1 := [3/4,0,0,0,1]: S2 := [0,0,0,3/10,1]:
# MBR12(5,S1,S2,2);
MBR12 := proc(n,S1,S2,b) option remember;
local k,S3,P;

P := 0;

if nops(S1) <> n or nops(S2) <> n then
	ERROR("BadInput");
fi:

S3 := [0$n];
for k from 1 to n do
	if abs(PCall(k,S1,S2,b)-PFold(k,S1,n))< 10^(-10) then
		S3[k] := "cORf";
	elif PCall(k,S1,S2,b) > PFold(k,S1,n) then
		S3[k] := "c";
	elif PCall(k,S1,S2,b) < PFold(k,S1,n) then	
		S3[k] := "f";
	else
		ERROR("NotExpect");
	fi:	
	P := P+max(PCall(k,S1,S2,b),PFold(k,S1,n));
od:

[P/n,S3];
end:

# Payoff if fold
# Input: card k, Strategy S1 of player1 
# and number of cards n
# Output: the payoff of player 3 if fold from this card k
# Try: [seq(PFold(k,[1,1,0,0,1],5),k=1..5)];
PFold := proc(k,S1,n) option remember;
local i,j,S;

S := {seq(i,i=1..n)};

add(add(
-S1[i]+Call2(k,i,j,1)*(1-S1[i])
,i in S minus {j,k}),j in S minus {k})
/(n-1)/(n-2);
end:


# Payoff if call
# Input: card k, Strategy S1,S2 of player1 and player2 
# and number of cards n
# Output: the payoff of player 3 if call from this card k
# Try: [seq(PCall(k,[1,1,0,0,1],[0,0,0,3/10,1],2),k=1..5)];
PCall := proc(k,S1,S2,b) option remember;
local i,j,n,S;

n := nops(S1);
S := {seq(i,i=1..n)};

add(add(
Call2(k,i,j,b+1)*S1[i]*S2[j]
+Call1(k,i,b+1)*S1[i]*(1-S2[j])
+Call2(k,i,j,1)*(1-S1[i])
,i in S minus {j,k}),j in S minus {k})
/(n-1)/(n-2);
end:


##################################################
# Fast (non-)Linear programming 
# for discrete number of cards
# For 3-person Poker, 
# solving for mixed Nash equilibrium 
# MNE(n,b): one "mixed" Nash Equilibria [S1,S2,S3] 
# with n cards and bet size b, where S1 
# is Player 1's strategy, S2 is Player 2's strategy
# and S3 is Player 3's strategy
# Output: The list of 
# 1.sum of payoffs of 3 players
# 2.list of payoffs of each player
# 3.list of strategies of each player.
# Please check these solutions with MNE(n,b) .
# Try: FastMNE(4,1); MNE(4,1);
#
# n:=20:b:=3: M:=FastMNE(n,b);
# MBR23(n,M[3],M[4],b);
# MBR12(n,M[2],M[3],b);
# [ListCF(M[1]),ListCF(M[2]),ListCF(M[3]),ListCF(M[4])];
FastMNE := proc(n,b) option remember;
local i,j,k,S,p,q,r,V1,V2,V3,P
,con1,con2,con3,con4,con5,A,S1,S2,S3,ep;

# Use epsi to shift the value of V1[i],V2[i],V3[i]
# when do optimization
ep := 2:

# p= raise, 1-p=check
# q= call, 1-q=fold
# r= call, 1-r=fold
S := {seq(i,i=1..n)};

# con1 = Player 1 checks or Player1 raises 
con1 := {seq(add(add(
Call2(i,j,k,1)
,k in S minus {i,j}),j in S minus {i})
/(n-1)/(n-2)<=V1[i]-ep,i=1..n)} union
{seq(add(add(
Call2(i,j,k,b+1)*q[j]*r[k]
+Call1(i,j,b+1)*q[j]*(1-r[k])
+Call1(i,k,b+1)*(1-q[j])*r[k]
+2*(1-q[j])*(1-r[k])
,k in S minus {i,j}),j in S minus {i})
/(n-1)/(n-2)<=V1[i]-ep,i=1..n)};

# con2 = Player 2 folds or Player2 calls
con2 := {seq(add(add(
-p[i]+Call2(j,i,k,1)*(1-p[i])
,k in S minus {i,j}),i in S minus {j})
/(n-1)/(n-2)<=V2[j]-ep,j=1..n)} union
{seq(add(add(
Call2(j,i,k,b+1)*p[i]*r[k]
+Call1(j,i,b+1)*p[i]*(1-r[k])
+Call2(j,i,k,1)*(1-p[i])
,k in S minus {i,j}),i in S minus {j})
/(n-1)/(n-2)<=V2[j]-ep,j=1..n)};

# con3 = Player 3 folds or Player3 calls
con3 := {seq(add(add(
-p[i]+Call2(k,i,j,1)*(1-p[i])
,j in S minus {i,k}),i in S minus {k})
/(n-1)/(n-2)<=V3[k]-ep,k=1..n)} union
{seq(add(add(
Call2(k,i,j,b+1)*p[i]*q[j]
+Call1(k,i,b+1)*p[i]*(1-q[j])
+Call2(k,i,j,1)*(1-p[i])
,j in S minus {i,k}),i in S minus {k})
/(n-1)/(n-2)<=V3[k]-ep,k=1..n)};

con4 := {seq(p[i]>=0,i=1..n),seq(p[i]<=1,i=1..n)
,seq(q[j]>=0,j=1..n),seq(q[j]<=1,j=1..n)
,seq(r[k]>=0,k=1..n),seq(r[k]<=1,k=1..n)};

con5 := {seq(q[i]=r[i],i=1..n)};

S1 := add(V1[i],i=1..n)/n;
S2 := add(V2[j],j=1..n)/n;
S3 := add(V3[k],k=1..n)/n;

P := S1+S2+S3;
A := Minimize(P
# Manipulate the outputs to make them look nice.
+10^(-6)*add(i*p[i],i=1..n)
-10^(-13)*add(j*q[j],j=1..n)
-10^(-13)*add(k*r[k],k=1..n)
,con1 union con2 union con3 union con4 union con5); 

subs(A[2],[[P-3*ep,S1-ep,S2-ep,S3-ep],[seq(p[i],i=1..n)]
,[seq(q[j],j=1..n)],[seq(r[k],k=1..n)]]);

end: 

# Important remark:
# FastMNE(n,b) did not give the correct answers
# for some (n,b). For examples those with
# (n,b) = (7,5),(8,7),(10,9), (11,10),(12,12),
# (13,14),(14,15),... .
# I tend to think that there is a bug on 
# the built in command Minimize.

# Explain version of solution of FastMNE
# Input: n cards and bet size b
# Output: Nothing. But print out the explanation
# of solution of 3-person poker von Neumann style
# where player1 raise/check and player2,3 call/fold
# if player1 raises.
# Try:
# FastMNEVerbose(7,2);
FastMNEVerbose :=proc(n,b) option remember;
local M,S;

M := FastMNE(n,b);
S := [ListCF(M[1]),ListCF(M[2]),ListCF(M[3]),ListCF(M[4])];

print(`The solution for von Neumann poker: Three-person version`);
print(`Each player put 1 token to the pot. Player 1 can check or raise.`);
print(`In case of raise, player 2 and player 3 can choose to call or fold.`);
print(`We will present ONE Nash Equilibrium of this game.`);
print(`The game is played with`, n, `cards and player1 raises (in case if he wants to) with the amount`, b,` tokens `);
print(``);

if S[1][1] <> 0 then
	print(`Unfortunately, the program does not manage to find the optimal value`);
	print(`Please try to write the same program in MathLab or Python.`);
	return();
elif S[1][2] = 0 then
	print(`The strategy is trivial. Player 1 will always check no matter what card he recieves. And it does not matter what strategies of player2 or 3 are. Everybody's payoffs are 0.`);
	return();	
else
print(`First of all, the pay off for player 1 is`, S[1][2]);
print(`the pay off for player 2 is`, S[1][3]);
print(`and the pay off for player 3 is`, S[1][4]);
print(``);
print(`The strategies for player 1 is a list of n probabilities P1 meaning if he gets card  x he should bet with prob. P1[x] and check with prob. 1-P1[x].`);
print(`The list is`, S[2]);
print(`The strategies for player 2,3 are lists of prob. P2,P3 meaning if he gets card y,z, he should call with prob. P2[y], P3[z] and fold with prob. 1-P2[y], 1-P3[z].`);
print(`The lists are`, S[3], `for player 2. And`, S[4], `for player 3.`);
fi:

return();
end:


############################
# Section 4: Solve NE of the cont. version 
# (0,1) of von Neumann 3-person game
#
# Functions:
# PayOff1(b,A,B,C), PayOff2(b,A,B,C),
# ConA(b,A,B,C), ConB(b,A,B,C),
# ConC(b,A,B,C), Optimal(b), 
#
############################

# Payoff of Player1
# Assume the intervals are in the same form
# as in 2-person. 
# Input: numeric or symbolic bet amount b, 
# the usual cutoffs A,B,C
# Output: payoff for player1
# Try:
# PayOff1(2,A,B,C);

PayOff1 := proc(b,A,B,C) option remember;
local x,y,z,P;

P := int(int(int(2,z=0..C),y=0..C),x=0..A)
+int(int(int(-(b+1),z=C..1),y=0..C),x=0..A)
+int(int(int(-(b+1),z=0..C),y=C..1),x=0..A)
+int(int(int(-(b+1),z=C..1),y=C..1),x=0..A)
+int(int(int(2,y=0..x),z=0..x),x=A..B)
+int(int(int(-1,z=x..1),y=0..x),x=A..B)
+int(int(int(-1,z=0..x),y=x..1),x=A..B)
+int(int(int(-1,z=x..1),y=x..1),x=A..B)
+int(int(int(2,z=0..C),y=0..C),x=B..1)
+int(int(int(b+2,z=0..C),y=C..x),x=B..1)
+int(int(int(b+2,z=C..x),y=0..C),x=B..1)
+int(int(int(2*(b+1),z=C..x),y=C..x),x=B..1)
+int(int(int(-(b+1),z=0..C),y=x..1),x=B..1)
+int(int(int(-(b+1),z=x..1),y=0..C),x=B..1)
+int(int(int(-(b+1),z=x..1),y=C..x),x=B..1)
+int(int(int(-(b+1),z=C..x),y=x..1),x=B..1)
+int(int(int(-(b+1),z=x..1),y=x..1),x=B..1)
;
factor(P);
end:


# Payoff of Player2
# Assume the intervals are in the same form
# as in 2-person. 
# Input: numeric or symbolic bet amount b, 
# the usual cutoffs A,B,C
# Output: payoff for player1
# Try:
# PayOff2(2,A,B,C);
# simplify(PayOff1(b,A,B,C)/PayOff2(b,A,B,C));
PayOff2 := proc(b,A,B,C) option remember;
local x,y,z,P;

P := int(int(int(-1,z=0..1),y=0..x),x=A..B)
+int(int(int(2,z=0..y),y=x..1),x=A..B)
+int(int(int(-1,z=y..1),y=x..1),x=A..B)
+int(int(int(-1,z=0..1),y=0..C),x=0..A)
+int(int(int(b+2,z=0..C),y=C..1),x=0..A)
+int(int(int(2*(b+1),z=C..y),y=C..1),x=0..A)
+int(int(int(-(b+1),z=y..1),y=C..1),x=0..A)
+int(int(int(-1,z=0..1),y=0..C),x=B..1)
+int(int(int(-(b+1),z=0..1),y=C..x),x=B..1)
+int(int(int(b+2,z=0..C),y=x..1),x=B..1)
+int(int(int(2*(b+1),z=C..y),y=x..1),x=B..1)
+int(int(int(-(b+1),z=y..1),y=x..1),x=B..1)
;
factor(P);
end:


# Setup the relation of A,B,C before
# solving for NE

# Condition at A to be NE for Player1
# Input: symbolic b,A,B,C
# Output: Condition for NE at A
# Try: ConA(b,A,B,C);
ConA := proc(b,A,B,C) option remember;
local x,y,z,L1,L2;

# consider at x=A
# if check then 
L1 := int(int( 2,z=0..x),y=0..x)
+int(int( -1,z=x..1),y=0..x)
+int(int( -1,z=0..1),y=x..1);
L1 := subs(x=A,L1);

# if raise then
L2 := int(int( 2,z=0..C),y=0..C)
+int(int( -(b+1),z=C..1),y=0..C)
+int(int( -(b+1),z=0..1),y=C..1);

[L1,factor(L2)];
end:

# Condition at B to be NE for Player1
# Input: symbolic b,A,B,C
# Output: Condition for NE at B
# Try: ConB(b,A,B,C);
ConB := proc(b,A,B,C) option remember;
local x,y,z,L1,L2;

# consider at x=B
# if check then 
L1 := int(int( 2,z=0..x),y=0..x)
+int(int( -1,z=x..1),y=0..x)
+int(int( -1,z=0..1),y=x..1);
L1 := subs(x=B,L1);

# if raise then
L2 := int(int( 2,z=0..C),y=0..C)
+int(int( b+2,z=C..x),y=0..C)
+int(int( b+2,z=0..C),y=C..x)
+int(int( 2*(b+1),z=C..x),y=C..x)
+int(int( -(b+1),z=0..x),y=x..1)
+int(int( -(b+1),z=x..1),y=0..x)
+int(int( -(b+1),z=x..1),y=x..1);
L2 := subs(x=B,L2);

[L1,factor(L2)];
end:

# Condition at C to be NE for Player2 (and 3)
# Input: symbolic b,A,B,C
# Output: Condition for NE at C
# Try: ConC(b,A,B,C);
ConC := proc(b,A,B,C) option remember;
local x,z,L1,L2;

# if fold then 
L1 := int(int( -1,z=0..1),x=0..A)
+int(int( -1,z=0..1),x=B..1);

# if call then
L2 := int(int( b+2,z=0..C),x=0..A)
+int(int( -(b+1),z=C..1),x=0..A)
+int(int( -(b+1),z=0..1),x=B..1);

[L1,factor(L2)];
end:


# Solve for NE for a given bet size b
# Input: bet size b
# Output: list of payoff, values of A,B,C
# which give NE to the bet size b
# Try: Optimal(2);
# Remark: Optimal at b is about 2.07
# So try: Optimal(2.07);

Optimal := proc(b) option remember;
local A,B,C,L,R1,R2,R3,A1,B1,C1;

L:=ConA(b,A,B,C);
R1:=simplify(L[1]-L[2]);
L:=ConB(b,A,B,C);
R2:=simplify(L[1]-L[2]);
L:=ConC(b,A,B,C);
R3:=simplify(L[1]-L[2]);

C1:=solve(R2,C);   
A1 := solve(subs({C=C1},R3),A);

B1 := evalf(solve(subs({C=C1,A=A1},R1),B))[2];

C1 := subs(B=B1,C1);
A1 := subs({C=C1,B=B1},A1);

[PayOff1(b,A1,B1,C1),A1,B1,C1];
end:



# Explain version of solution of Optimal(b)
# Input: bet size b
# Output: Nothing. But print out the explanation
# of solution of 3-person poker von Neumann style 
# (on (0,1)) where player1 raise/check and 
# player2,3 call/fold if player1 raises.
# Try:
# OptimalVerbose(2);
OptimalVerbose := proc(b) option remember;
local M;

M := Optimal(b);

print(`The solution for (0,1) von Neumann poker: Three-person version`);
print(`Each player put 1 token to the pot. Player 1 can check or raise.`);
print(`In case of raise, player 2 and player 3 can choose to call or fold.`);
print(`We will present ONE Nash Equilibrium of this game.`);
print(`The game is played on (0,1) and player1 raises (in case if he wants to) with the amount`, b,` tokens `);
print(``);
print(`According to the program, the optimal payoff with the bet size`, b, `is approximately`);
print(M[1], `for player 1 and`, -M[1]/2, `for each of player 2 and player 3.`  );
print(``);
print(`Strategy of player 1, he raises if his card is in the interval`, [0,M[2]], `or in the interval`, [M[3],1], `On the other hand, he checks if his card is in the interval`, [M[2],M[3]] );
print(``);
print(`Strategy of player 2 and player 3, he folds if his card is in the interval`, [0,M[4]], `On the other hand, he calls if his card is in the interval`, [M[4],1] );
print(``);
print(`We also want to note that, experimentally, the best payoff for player 1 occurs when the bet size b is about 2.07.`);
print(``);
end: