Description

Experimental Mathematics used to be considered an oxymoron, but the future of mathematics is in that direction. In addition to learning the philosophy and methodology of this budding field, students will become computer-algebra wizards, and that should be very helpful in whatever mathematical specialty they are doing (or will do) research in.

We will first learn Maple, and how to program with it. This semester we will learn, from an experimental mathematics point of view, algorithmic and computational Game Theory. The final projects may lead to published papers. People who already took previous editions of this class are welcome to take it again, since except for the basics, there is very little overlap with previous years.

This class is suitable for graduate students in other departments, and the software development skills learned will be useful for doing any quantitative research. Very smart advanced undergraduates are also welcome. In particular, the methods learned for researching Game theory should be applicable almost everywhere.

Added March 31, PICK A PROJECT

Texts

• The wonderful book: Game Theory for Applied Economics by Robert S. Gibbons.

• Chapter 1 of Karl Sigmund's fascinating book

• Chapter 10 of Notes on Introductory Combinatorics by Polya, Tarjan, and Wood.
  Here is the original Gale-Shapley classic.

• Llyod Shapley's seminal paper about coalitions.
  See also this nice exposition.

• N.N. Yu's short proof of Arrow's theorem

• Ein-Ya Gura and Michael Maschler's exposition of the proof of Arrow's theorem, scanned from pages 82-92 of their wonderful book "Insights into game theory", Cambridge University Press.

• Dr. Z.'s snappy summary of Combinatorial Game Theory.

• Sasa Radomirovic's construction

Optional (but Highly recommended) Getting Started Homework

For more details, see this 2002 masterpiece.

How to submit homework

• Every class has a homework assignment. Both Mondays and Thursdays' are due 10:00pm Sunday of the following week.

  It should be sent to the email address

  ShaloshBEkhad at gmail dot com

  Subject: HomeWork#X

  and then attach a .txt file(s) called

  hwXYourFirstNameYourLastName.txt

  where X is the number of the assignment

  Except for the first assignment, you should have two attached .txt files.

  For example, when Yukun Yao submits homework assignments 2 and 3, he should email ShaloshBEkhad at gmail dot com, with

  Subject: HomeWork#2#3

  and attach the text files (the source code plus human comments (such lines must start with #)

  hw2YukunYao.txt and hw3YukunYao.txt

• The very first line of the .txt files should have

  #Please do not post homework
  or
  #OK to post homework

  Followed by
  #Your Name, Date, Assignment X

Lecture 1 ( Thurs., Jan. 20, 2022)

Programs done on Thurs., Jan. 20, 2022

• GameDB(): A list of length 5 consisting of a a "data base" of famous games (and less famous ones): Prisoner's dilemma, Battle of the Sexes, Matching pennies, Figure 1.1.1. in Gibbons, Figure 1.1.4 in Gibbons For example, to see the Prisoner's dilemma, type
  matrix(GameDB()[1])

• [Added after class]

  Rand2PlayerGame(a,b,K): A random 2-player (static) game where the Row player has a strategies (Row 1, .., Row a), the Column player has b strategies (Col. 1, ..., Col. b) and the pay-offs are from 0 to K. For example, to see a random game where Player Row has four strategy choices, and Player Column has five strategy choices and the pay-offs are integers from 0 to 20 type:
  matrix(Rand2PlayerGame(4,5,20));

• [Added after class]

  IsDom(v1,v2): Given two lists of numbers is v1[i]<=v2[i] for all i?. For example
  IsDom([1,3,2],[2,4,3]); should return true but IsDom([1,3,2],[2,4,1]); should return false

• [Added Jan. 23, 2022, thanks to comments by Lucy Martinez, Rebecca Embar, and George Spahn]

  IsStrictDom(v1,v2): Given two lists of numbers is v1[i] IsStrictDom([1,3,2],[2,4,3]); should return true but IsDom([1,3,2],[2,3,2]); should return false

Homework for Thurs., Jan. 20, 2022, class (due Sunday Jan. 23, 10:00pm)

Subject: hw#1

and an attachment

hw1FirstNameLastName.txt

and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

1. [People who took this class before, or already know Maple, are exempt from this] Read and do all the examples, plus make up similar ones, in the first 30 pages of Frank Garvan's awesome Maple booklet ( part 1, part 2)
   Only record a small sample in hw1YourName.txt .

2. [For everybody] For each of the games, GameDB()[4] and GameDB()[5], printout

   matrix(GameDB()[4]);

   matrix(GameDB()[5]);

   and for each of these two games, spell-out (like we did in class), for each choice (i,j), write the pay-off functions u_1(i,j) and u_2(i,j)

3. [For everybody] Read and understand pp. 1-7 (and the start of p. 8, until 1.1.C) of Robert Gibbons' book.

4. [For everyone] After reading section 1.1.B. of Gibbons, generate three random 2-player games with both players with 3 strategy-choices, and pay-offs between 0 and 3, and eliminate, BY HAND, as many strategies as you can, until you are left with a possibly smaller game (i.e. bimatrix). Is it ever a 1 by 1 bimatrix?

5. [Modified Jan. 23, 2022, thanks to comments by Lucy Martinez, Rebecca Embar, and George Spahn]

   [Mandatory for experts, optional for novices] Using procedure IsDom(v1,v2) (that I added after class), Write a Maple procedure

   FindDominatedRowStrategy(G)

   FindDominatedColumnStrategy(G)

   that inputs a 2-player game, G, and outputs either a row or column (respectively) that can be (weakly) eliminated, or returns FAIL.

6. [Added Jan. 23, 2022, thanks to comments by Lucy Martinez, Rebecca Embar, and George Spahn]

   [Mandatory for experts, optional for novices] Using procedure IsStictDom(v1,v2) (that I added Jan. 23), Write a Maple procedure

   FinStrictdDominatedRowStrategy(G)

   FindStrictDominatedColumnStrategy(G)

   that inputs a 2-player game, G, and outputs either a row or column (respectively) that can be (strongly) eliminated, or returns FAIL.

7. [Modified Jan. 23, 2022, thanks to comments by Lucy Martinez, Rebecca Embar, and George Spahn]

   [Mandatory for experts, optional for novices] Using the above, write a procedure

   ShrinkGame(G)

   that tries to shrink a game, if possible, or returns FAIL, then iterate it and write

   ReducedGame(G)

   that keeps shrinking the game until it not shrinkable any more.

Added Jan. 24, 2022: The students' nice solution can be found in this directory

Lecture 2 (Monday , Jan. 24, 2022)

Programs done on Monday Jan. 24, 2022

• GameDB(): A list of length 5 consisting of a a "data base" of famous games (and less famous ones): Prisoner's dilemma, Battle of the Sexes, Matching pennies, Figure 1.1.1. in Gibbons, Figure 1.1.4 in Gibbons and "Scissors, Rock Paper"

  PrintGamec(G): prints the game nicely, like in the book

• Rand2PlayerGame(a,b,K): A random 2-player (static) game where the Row player has a strategies (Row 1, .., Row a), the Column player has b strategies (Col. 1, ..., Col. b) and the pay-offs are from 0 to K. For example, to see a random game where Player Row has four strategy choices, and Player Column has five strategy choices and the pay-offs are integers from 0 to 20 type;

  PrintGame(and2PlayerGame(4,5,20));

• IsStictDom(v1,v2): Given two lists of numbers is v1[i]<=v2[i] for all i. For example IsStrictDom([1,3,2],[2,4,3]); should return true but IsDom([1,3,2],[2,4,1]); should return false

• FindR(G): Finds a strictly dominated row strategy

• FindC(G): Finds a strictly dominated row strategy FindC:=proc(G) local G1,ColS,j1,j2,i,v1,v2:

• ShrinkGame(G): Given a game G, tries to shrink it, if it can't it returns FAIL

• ReducedGame(G): The reduced game of G after all the possible Elimination of dominated strategy. Possibly the same

• MyMaxIndex(L): [Suggested by Victoria Chayes].

  Inputs a list L of numbers, output the SET of places (indices) where it is maximum. For example MyMaxIndex([5,6,7,7,1,7]); should give {3,4,6}

• BR1(G,a2): Inputs a game G and a member a2 of A2 outputs the SUBSET of A1 that consists of the best response

• BR2(G,a1): Inputs a game G and a member a1 of A1 outputs the SUBSET of A2 that consists of the best response

• BR1v(G): The list of size |A2| with all the set of best responses by Player Row to each of Player Column's strategies

• BR2v(G): The list of size |A1| with all the set of best responses by Player Column to each of Player Rows' strategies

• LoadedCoin(p): outputs 1 or 2 with probability p and 1-p respectively. Try:

  add(x[LoadedCon(1/3)],i=1..300);

Homework for Monday Jan. 24, 2022, class (due Sunday Jan. 30, 10:00pm)

Subject: hw#2

and an attachment

hw2FirstNameLastName.txt

and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

1. [People who took this class before, or already know Maple, are exempt from this] Read and do all the examples, plus make up similar ones, in the pages 30-60 of Frank Garvan's awesome Maple booklet ( part 1, part 2)
   Only record a small sample in hw2YourName.txt .

2. [For everyone] Read, understand, and experiment with the Maple code of C2.txt , by generating five random games, and finding the Best-Response lists of the Row and Column Player.

3. [For everyone] Read and understand section 1.1.C. of Robert Gibbons' book

4. [For everyone] Using procedures BR1v(G) and BR2v(G), write a one-line Maple procedure

   IsNash(G,a1,a2)

   That inputs a 2-player game bi-matrix G, and members a1,a2 of A1, A2 respectively (that in our convention are integers from {1, ..., nops(G)} and {1, ..., nops(G[1])}) and outputs true or false according to whether [a1,a2] is a Nash Equilibrium.

5. Write a procedure

   PureNashEqui(G)

   that inputs a bi-matrix G, and outputs the (possibly) empty set of pairs [a1,a2] that are (pure) Nash Equilibria.

   Generate 5 random 2-player games where Player Row has 10 strategies, and Player Column has 12 strategies, and for each find their set of (pure) Nash Equilibria

Added Jan. 30, 2022: The students' nice solution can be found in this directory

Lecture 3 (Thurs. , Jan. 27, 2022)

Programs done on Thurs. Jan. 27, 2022

• RandDisGame(a,b): A random game where Player Row has a strategies R1, R2, ..., Ra; and Player Col. has b strategies: C1, C2, ..., Cb and all pay-offs are DISTINCT and consist of the set {1,2,...,ab}. Try:
  RandDisGame(4,6);

• BR1d(G,a2): Inputs a bimatrix of a game G and a member a2 of A2 outputs the UNIQUE member of A1 that consists of the best response

• BR2d(G,a1): Inputs a bimatrix of a game G and a member a1 of A1 outputs the UNIQUE member of A2 that consists of the best response

• BR1dv(G): Inputs a bimatrix of a game G, outputs The list of size |A2| with all the best responses

• BR2dv(G): Inputs a bimatrix of a game G, outputs The list of size |A1| with all the best responses

• DynRC(G): The outcome of the Dynamical version of the game G if Row goes first and Column goes next

• DynCR(G): The outcome of the Dynamical version of the game G if Column goes first and Row goes next

Homework for Thurs. Jan. 27, 2022, class (due Sunday Jan. 30, 10:00pm)

Subject: hw#3

and an attachment

hw3FirstNameLastName.txt

and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

1. [People who took this class before, or already know Maple, are exempt from this] Read and do all the examples, plus make up similar ones, in the pages 61-90 of Frank Garvan's awesome Maple booklet ( part 1, part 2)
   Only record a small sample in hw3YourName.txt .

2. Read and understand the Maple code of
   C3.txt .
   

3. Using (a) G:=RandDisGame(4,4) ; (b) G:=RandDisGame(5,7); Find (BY HAND!)

   (i) The outcome of the sequential (aka dynamical) version of the game where Player Row goes first

   (ii) The outcome of the sequential (aka dynamical) version of the game where Player Column goes first

   (iii) The set (possibly empty) of (pure) Nash Equilibria

   Check these answers using procedures DynRC, DynCR, and your own PureNashEqui(G) that hopefully you wrote for hw2

4. Using Maple's command permute(n) (once you did "with(combinat):", write a procedure

   AllGames(a,b)

   that inputs positive integers a and b and outputs the set of all (a*b)!² possible games where Player Row has a strategies, Player Column has b strategies, each player's payoffs are distinct and drawn from {1, ..., a*b}

5. Write a procedure

   FullStat(a,b)

   that inputs positive integers a and b (not too big!) and outputs the following list

   [Number of Games with No Nash Equilibria, Number of Games with One Nash Equilibria, Number of Games with Two Nash Equilibria, Number of Games where the Row Player was better off playing second, Number of Games where the Column Player was better off playing second, Number of Games where DynRC(G)=DynCR(G)]

   What are

   (i) FullStat(2,2)

   (ii) FullStat(3,2) [It may take a while]

6. Write a procedure

   SampleStat(a,b,K)

   that inputs positive integers a and b, and a fairly large positive integer K, and generates K random games where Row has a strategies and Col has b strategies and outputs the following list of numbers (in floating-point, i.e. decimals)

   evalf( [(Number of Games with No Nash Equilibria)/K, (Number of Games with One Nash Equilibria)/K, (Number of Games with Two Nash Equilibria)/K, (Number of Games where the Row Player was better off playing second)/K, (Number of Games where the Column Player was better off playing second)/K, (Number of Games where DynRC(G)=DynCR(G))/K]):

   Run the following five times

   (i) SampleStat(10,10,10000)

   and see if the answers are similar.

Added Jan. 30, 2022: The students' nice solution can be found in this directory

Lecture 4 (Monday , Jan. 31, 2022)

Programs done on Monday, Jan. 31, 2022

• FP(L): inputs a list L of integers, outputs the SET of integers such that L[i]=i. For example
  FP([5,2,1,4,1]); should be {2,4}

• BR12(G): Given a game G outputs the discrete function f: A1->A1 such that f(a1)= Best Response of Player 1 to the Best Response of Player 2 to Player 1's strategy a1.

• BR21(G): Given a game G outputs the discrete function g: A2->A2 such that g(a2)= Best Response of Player 2 to the Best Response of Player 1 to Player 2's strategy a2.

Homework for Monday Jan. 31, 2022, class (due Sunday Feb. 6, 10:00pm)

Subject: hw#4

and an attachment

hw4FirstNameLastName.txt

and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

1. [People who took this class before, or already know Maple, are exempt from this] Read and do all the examples, plus make up similar ones, in the pages 91 to the end of Frank Garvan's awesome Maple booklet ( part 1, part 2)
   Only record a small sample in hw4YourName.txt .

2. Read and understand the Maple code of C4.txt , and with three choices of G:=RandDisGame(30,30), confirm that the outputs BR12(G), BR21(G) agree with your own PureNashEqui(G) that hopefully you wrote for hw2

3. Read and understand section 2.1B of Gibbons' book

4. Read and understand section 1.2A of Gibbons' book.

5. Suppose that you want to make the TOTAL profit (i.e. the sum of the profits of both companies) as large as possible Would you choose
   (i) Monopoly (i.e. they both agree to produce quantity A/4, totaling A/2 like in a monopoly)
   (ii) The Stackelberg model where one company goes first
   (iii) The Cournot model where they decide simultaneously, and each strategy choice is a best response to the other one.

6. Suppose that the natural price that one can charge if the quantity in the market is q, is not A-q, like in the Stackleberg and Cournot models, but rather

   (A-q)^d

   For some positive number d. What are

   (i) The best quantity choice for a MONOPOLY (make sure that you get A/2 when d=1)

   (ii) The best quantity choice for Company 1 and Company 2 in the Stackelberg model (make sure that you get A/2 and A/4 when d=1)

   (iii) The Nash Equilibrium choice where each is a best response of the other (make sure that you get A/3 and A/3 when d=1)

Added Feb. 7, 2022: The students' nice solution can be found in this directory

Lecture 5 (Thurs. , Feb. 3, 2022)

Programs done on Feb. 3, 2022

contains, in addition to previous codes (use Help2();, Help3();, Help4(); to see the corresponding list), the following procedures

• BetterForBoth(G,a1,a2): Given a game G and a strategy choice (a1,a2) finds all the set of strategy choices that are better for BOTH players then [a1,a2] (usually applied to a Nash Equilibrium (or to an outcome of a sequential game)

• BestTot(G): Given a 2-player game G, outputs the places where the total pay-off is the best, together with the pay-off

• IsNE(G,a1,a2): Is [a1,a2] a Nash Equilibrium of the game G?

• RG(a,b,K): A random 2-player (static) game where the Row player has a strategies (Row 1, .., Row a), the Column player has b strategies (Col. 1, ..., Crol. b) and the pay-offs are from 0 to K.

• Homework for Thurs. Feb. 3, 2022, class (due Sunday Feb. 6, 10:00pm)

  Please email ShaloshBEkhad at gmail dot com an email with

  Subject: hw#5

  and an attachment

  hw5FirstNameLastName.txt

  and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

  1. Read and understand section 1.2.B in the book. Write Maple code for the pay-offs for both players in term of the variables p1, and p2 (hoe much price to decide) and the parameters a,b,c for the profit function of both players. Either by hand, or using Maple, find the Best Response Functions, and the Nash Equilibrium. Confirm it graphically (for specific, numeric, a,b,c) by using Maple's implicitplot. (You may need to enter: with(plots);, first)

  2. Read and understand the Maple code of C5.txt , and with three choices of G:=RG(30,30,10000), find the set of Nash Equilibria, the pair (a1,a2) such that the total welfare is maximal, and for each of the Nash Equilibria (if they exist) whether there exists a strategy choice that makes it better.

  3. Using procedure AllGames(a,b) that you hopefully wrote for hw3, write a procedure

     BeatNE(a,b)

     that inputs positive integers a and b and outputs the set of all games (given as bi-matrices) for which there is a unique Nash Equilibrium, AND there exist a strategy choice that is better for BOTH players.

     What are the sets

     BeatNE(2,2)

     BeatNE(2,3) [If it does not take too long]

  4. Using RG(a,b,K), write a procedure

     EstBeatNE(a,b,K,M)

     that inputs a,b,K (as for RG(a,b,K) and a large integer M, generates M random games, and counts, out of these M games, how many have the property that they have exactly one Nash Equilibria, followed by the number of those, among the former, that have the property that the total pay-offs is better than the total pay-off of the Nash Equilibria, followed by the number of those (games with exactly one NE) that have the property that there exists a strategy choice that is NOT a NE but nevertheless is better for both of them (like (Silent, Silent) in the Prisoner's Dilemma). Divide these numbers by M, and take evalf

     What did you get for

     EstBeatNE(10,10,1000,1000)?

     (Run it five times and see whether you get similar answers)

  5. Suppose that the utility functions for Players 1 and 2 are

     u1:=q1*(1-q1-q2)^(d1);

     u2:=q2*(1-q1-q2)^(d2);

     Assume that d1 and d2 are numbers between 0 and 1. Using Maple's built-in functions `diff` and `solve', find an explicit expression, in terms of the parameters d1,d2 for the Nash Equilibrium. (Make sure that when d1=1, d2=1 you get (1/3,1/3)).

  6. Optional challenge (I don't know the answer). We know that for d1=1 and d2=1 the NE is NOT "efficient", i.e. does not maximize the total pay-off. Find conditions on d1 and d2 for which this is still the case. You are welcome to experiment with specific d1,d2.

  Added Feb. 7, 2022: The students' nice solution can be found in this directory

  ---

  (In-person) Lecture 6, Monday, Feb. 7, 2022

  Programs done on Feb. 7, 2022

  C6.txt , contains (in addition to the old procedures) the following new procedures

• SimulateG(G,p1,p2): Simulates ONE 2-person game with 2 strategies given by a bimatrix G each game where the stochastic Strategy of Player is to play Odd with Pron. p1 and Player 2 with prob. p2

• SimulateMG(G,p1,p2,K): Plays the game G with mixed strategy (p1,p2) K times and outputs the pair of average payoffs

• PayOffG(G,p1,p2): Inputs a 2-player game with two strategies for each player, given in terms of its bi-matrix, and rational numbers p1 and p2 between 0 and 1 (inclusive) (of left as symbols), outputs the pair [PayOffOfPlayer1,PayOffOfPlayer2] for the expected pay-off if Player 1 adopts strategy R1 with prob. p1 (and hence Strategy R2 with prob. 1-p1) and Player 2 adopts strategy C1 with prob. p2 (and hence Strategy C2 with prob. 1-p2)

Homework for Monday Feb. 7, 2022, class (due Sunday Feb. 13, 10:00pm)

Subject: hw#6

and an attachment

hw6FirstNameLastName.txt

and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

1. Using procedure RG(a,b,K) of Lecture 5 (also contained in C6.txt ), Create five random games with a=2, b=2, K=1000, and for each of these games, pick three random choices of p1 and p2 and run SimulateMG(G,p1,p2,K) with K=10000, each five times. Make sure that you get similar-looking answers, and compare them to the output of

   evalf(PayOffG(G,p1,p2))

2. Read and understand Section 1.2.D (pp. 27-28) of Gibbons' book

3. [A little bit challenging] Confirm the "Tragedy of the commons by confirming that the solution of Eq. (1.2.6) for n >1 is larger than the solution of Eq. (1.2.7) (which is the former equation with n=1), and hence that too many goats are grazed in the Nash equilibrium when more than one farmer shares the common pasture.

   Write a procedure

   TagedyOfTheCommons(v,G,c,n)

   that inputs

   (i) An expression,v, for a function that is positive in the variable G, in 0 ≤ G ≤ 1, but whose first and second derivatives are negative there (like in Fig. 1.2.4 in the book with G_max=1);

   (ii) a number c, the cost of buying and caring for the goat, (between 0 and 1);

   (iii) a positive integer n, the number of farmers;

   and outputs the Nash Equilibrium G*.

   Hint: use Maple's "diff" command, and "fsolve" command to solve the equation

   What did you get for

   seq(TagedyOfTheCommons(sqrt(1-G),G,0.5,n),n=1..10);

   seq(TagedyOfTheCommons((1-G)^(1/4),G,0.5,n),n=1..10);

   seq(TagedyOfTheCommons((1-G)^(3/4),G,0.5,n),n=1..10);

   Confirm that as the number of farmers get larger, the total number of goats, in the Nash equilibrium, gets farther and farther away from the social optimum.

Added Feb. 14, 2022: The students' nice solution can be found in this directory

Lecture 7 (Thurs. , Feb. 10, 2022)

Programs done on Feb. 10, 2022

contains, in addition to previous codes (use Help2();, Help3();, Help4(); Help5(); and Help6(); to see the corresponding list), the following procedures

• BRL(f,x): inputs an affine linear expression in x outputs the x for which f is maximal, according to conditions. try:

• MNE22(G): The set of mixed Nash equilibria for a 2-person game with each player having two strategies, where G is given as a 2 by 2 bimatrix. It gives all the pairs (p1,p2) such that if Player Row plays strategy R1 with prob. p1 (and hence strategy R2 with prob. 1-p1) and Player Col plays strategy C1 with prob. p2 (and hence strategy C2 with prob. 1-p2) these stochastic strategies are Best responses to each other, in the sense that for either player deviating from them (while the other player keeps his or her strategy) will make her or his EXPECTED payoff worse.

Homework for Thurs. Feb. 10, 2022, class (due Sunday Feb. 13, 10:00pm)

Subject: hw#7

and an attachment

hw7FirstNameLastName.txt

and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

1. Use Maple's graphics draw a nice Valentine, if possible a cardiodid (or other Valentine-like shape) with the iside a text

   I LOVE ...

   where ... is either a favorite number (Pi, e, sqrt(2), Golden Ratio) where the decimal digits are wrapped around the Valentine, or ... is a favorite sequence (Fibonacci, Catalan, Thue-Morse cube-free word (that only has 0's and 1..), or square-free word (that only has 0,1,2), etc.

   Submit (in addition to hw7FirstLast.txt, two files ValentineFirstLast.txt (for the Maple code) and ValentineFirstLast.jpg (for the picture).

   The students will vote for the best valentine, and the winner will win a chocolate box.

   Added Feb. 14, 2022: The students' beautiful Valentines (and Maple source code) can be found here

2. Write a procedure

   TypeCounts22(K1,K2)

   that inputs a very large positive integer (at least ten million, otherwise there may be some Maple issues, the current code for MNE22(G) does not address some pathological cases, but if you make K1 large enough it should not be a problem), and fairly large positive integer K2 (say, around 10000), uses RG(2,2,K1) K2 times and outputs the following list of length 4 of floating-point numbers

   evalf([Number of Games with Exactly One Pure Nash Equilibrium, Number of Games with Exactly Two Pure Nash Equilibrium and No Mixed one, Number of Games with No Pure Nash Equilibrium and one Mixed , Number of Games with Two Pure and One Mixed]/K2)

   Run it five times with K1=10^8, and K2=10000 and observe whether you get similar-looking answers (of course, not exactly the same)

3. [Human challenge] I hope that the second component above was always 0. Explain why, i.e. why it is impossible that there are two pure Nash Equilibria, and no mixed one, in other words like in the Opera/Fight game, if there are two pure Nash Equilibria, there is always also a mixed one.
   Hint: You can give a graphical proof, using diagrams similar to Fig. 1.3.3, 1.3.4, 1.3.5, 1.3.6 in Gibbons' book. There four possibilities for the graph of the Best Response "correspondence" for each of the player (for Player 1,
   (i) the line segment from [0,0] to [0,1] (indicating the pure strategy p1=0)
   (ii) the line segment from [1,0] to [1,1] (indicating the pure strategy p1=1)
   (iii) a broken line of the form [0,0]->[0,a]->[1,a]->[1,1]

   (iv) a broken line of the form [0,1]->[0,a]->[1,a]->[1,0]

   Similary for Player Column. Altogether there are 16 possibilities. A NE (mixed or pure) is an intersection point of these two Best Response "correspondences"

4. [Human optional challenge, I don't know the answer] Can you guess the limiting values of the above experiments? Can you prove it?

5. Generalize procedure

   PayOffG(G,p1,p2)

   To write a procedure

   PayOffGG(G,p1,p2)

   where G is an arbitrary 2-person game, with say, m (=nops(G)) strategies for Player Row, and n (=nops(G[1]) strategies for Player Column, and p1, p2, are probability vectors (i.e. they add up to 1) and outputs a list of length 2 with the payoffs of Player Row and Player Col.

   [Note: You should check that they add-up to 1, and return FAIL if they don't, but do not check that they are all posiitive, since we may need it for symbolic probability vectors like [x1,x2,1-x1-x2]]

Added Feb. 14, 2022: The students' beautiful homework is in this directory

(In-person) Lecture 8, Monday, Feb. 14, 2022

Today we admired the beautiful valentines. The data for the contest is here, and here are the oucomes. Congratulations to Yuxuan Yang, Lucy Martinez, and Robert Dougherty-Bliss for being voted the best entries. However, I believe that they were all very good!.

Homework for Monday Feb. 14, 2022, class (officially due Sunday Feb. 20, 10:00pm, but you are encouraged to do it by Feb. 17)

Subject: hw#8

and an attachment

hw8FirstNameLastName.txt

and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

1. Read and unerstand (IF POSSIBLE BY THURS., Feb. 17) Chapter 1 of Karl Sigmund's fascinating book

2. Prove that (Defect,Defect) is always the unique Nash Equilbria, (including mixed one) of the version of Prisoner's dillema (called the "donation game" in Sigmund's book) Show that if T=R+0.01, R=10000P, S=P-0.01, In (1.1)) how tragic it is.

3. Prove that in the version of the Snwodrift game in section 1.4, with T>R>S>P, (Refuse,Pay) and (Pay,Refuse) are two pure Nash equilibria. Either by hand, or using Maple, prove that in addition there is a mixed Nash equilibrium. Find an explicit expression for that additional Nash equilibrium, in terms of the parameters T,R,S,P, and check it for random numerical values using MNE(G).

Added Feb. 21, 2022: The students' beautiful homework is in this directory

Lecture 9 (Thurs. , Feb. 17, 2022)

Programs done on Feb. 17, 2022

contains, in addition to previous codes (use Help2();, Help3();, Help4();, Help5();, Help6();, Help7();, to see the corresponding list), the following procedures

• PayOffGG(G,p1,p2): Inputs a 2-player game with m:=nops(G) strategies for player Row, and n:=nops(G[1]) strategies for Player Col given in terms of its bi-matrix, and probability vectors [p1[1],...p1[m]] and probabilty vectors [p2[1],...p2[m]]

• BRLG(f,var): Given a linear expression f in x[1],..., x[nops(x)] finds the best response conditions as a set of sets of condtions

• [Finished after class]

  MNE2(G): The set of mixed Nash equilibria for a 2-person game with each player having two strategies, where G is given as a 2 by 2 bimatrix. It gives all the pairs (p1,p2) such that if Player Row plays stragety R1 with prob. p1 (and hence strategy R2 with prob. 1-p1) and Player Col plays stragety C1 with prob. p2 (and hence strategy C2 with prob. 1-p2) these stochastic stragies are Best responses to each other, in the sense that for either player deviating from them (while the other player keeps his or her strategy) will make her or his EXPETED payoff worse. Try:

  G:=RG(3,3,100); MNE2(G):

• [added after class]
  RGs(n,K): A random symmetric 2-player symmetric game with n strategies for each play with symmetric pay-oofs

• [added after class]
  SolOpt2(G): Given a 2-player game G, given by its bi-matrix, outputs the socially optimal outcome. It outputs the pair [champ,record]

Homework for Thurs. Feb. 17, 2022, class, due Sunday Feb. 20, 10:00pm

Subject: hw#9

and an attachment

hw9FirstNameLastName.txt

and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

1. Read and understand the Maple code in C9.txt , including procedure MNE2 (finished after class, with an efficiency tip by Blair Seidler), and procedurs RGs(n,K) (to generate a random SYMMETRIC 2-person game), and SolOpt2(G) to find the social optimum (that sadly is often not a NE), along with its correponding payoff.

2. Write a procedure

   StatSymGames(n,K1,K2)

   that inputs a positive integer n (the number of players), and positive integers K1 and K2 (where K1 is very big, say 10000000, and K2 is between 1000 and 2000) , and generates K2 random SYMMETRIC n-player games (with payoffs between 0 and K1), and outputs the following list <> evalf([Number of Games with Only Pure Nash Equlibria, Number of Games with Only Mixed Nash Equlibria,Number of Games with both pure and mixed Nash Equlibria,Number of Games where the Social Optium is NOT one of the NE]/K2)

   Run

   StatSymGames(3,10^10,1000);

   several times, and make sure that you get similar answers. Then, computing-time permitting (I did not try it out!)

   Do the same things for

   StatSymGames(4,10^10,1000);

   and

   StatSymGames(5,10^10,1000);

3. [A little bit of a challenge] For the Snowdrift (aka Ballet/Fight) symmetric 2-person

   [[[R,R],[S,T]],[[T,S],[P,P]]

   with the assumption

   T > R > S > P

   Find a closed-form expression, in terms of the parameters T,R,S,P for the sum of tha payoffs in the MIXED Nash equilibrium, that always exists.

   [Hint: use the answer to ex. 3 in hw8]

4. Using "assume", use MNE2, to find all the Nash Equilbria (pure and mixed) for all symmetric 2-plyaer games with 2 strategies each, symbolically in terms of T,R,S,P

   For all 24 orderings of T,R,S,P. How many of these permutations yield a mixed NE?

5. [Optional challenge, I don't know the answer, or whether it is feasible, 10 dollars]

   For all possible 9!=362880 permutations of ordering a11,a12,a13,a21,a22,a23,a31,a32,a33, find the mixed Nash equibria for the symmetric game

   [a11,a11],[a12,a21],[a13,a31]
   [a21,a12],[a22,a22],[a23,a32]
   [a31,a13],[a32,a23],[a33,a33]

   and find how many have only mixed starategies.

6. Get ready for the next class by doing a preliminary reading of
   Chapter 10 of Notes on Introductory Combinatorics by Polya, Tarjan, and Wood.

Added Feb. 21, 2022: The students' beautiful homework is in this directory

(In-person) Lecture 10, Monday, Feb. 21, 2022

Programs done on Feb. 21, 2022

• RT(n): Generates a pair of random preferance M,W, two lists-of-lists

• IsStable1(M,W,pi,i1,i2): inputs ranking tables M,W, a current matching pi and two men i1,i2, returns false if the current Mrs. i2 prefers i1 to i2 and Mr. i1 prefers Mrs. i2 to the current Mrs. i1. Otherwise true

• IsStable(M,W,pi) : inputs preferance tables M and W and a matching pi decides whether it is stable. It also also returns a pair of men i1 < i2, if it is not stable

• FindStable(M,W,K): Given the Men's and Women's preferance tables,M and W, starts with a random matching and keeps "fixing it" until hopefully you get a stable matching, we limit the number of iterations to K, if none found it will return FAIL. Otherwise it will return a stable

Homework for Monday Feb. 21, 2022, class, due Sunday Feb. 27, 10:00pm

Subject: hw#10

and an attachment

hw10FirstNameLastName.txt

and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

1. Write a procedure

   CountInstablities(M,W,pi)

   That enters ranking tables M,W, and a current matching pi, and counts how many of the n*(n-1) ordered pairs of husbands 1 ≤ i1, i2 ≤ n are such that i1 is married to j1, i2 is married to j2, but i1 would rather be married to j2 (instead of his current wife j1) and j2 would rather be married to i1 (rather than her current husband i2)

2. Write a procedure

   GFstab(n,K,x)

   That inputs positive integers n and a large positive integer K, generates K times, random ranking tables using RT(n), and a random matching, pi, and outputs the polynomial in x (of degree ≤ n(n-1)), whose coeff. of xⁱ is the number of those random choices that lead to exactly i instablities. By taking the first and second derivatives w.r.t. to x, estimate the expectation and variance of the "number of instabilities".

Added Feb. 28, 2022: The students' beautiful homework is in this directory

Lecture 11 (Thurs. , Feb. 24, 2022)

Programs done on Feb. 24, 2022

• inv(pi): The inverse of the permutation pi

• GaleSh(M,W) : inputs two reanking-tables, M,W, where assuming that there are n men and n women (nops(M)=n and nops(W)=n), M[i][j] is the rank of Ms. j in the eyes of Mr. i and W[j][i] is the rank of Mr. i in the eyes of Ms. j, outputs a stable matching, where men do the proposing. It tells the whole story and outputs the ultimate stable matching, followed by the number of proposals

• GaleShT(M,W) : a terse version of GaleSh(M,W), returns the stable matching followed by the number of proposals.

Homework for Thurs. Feb. 24, 2022, class, due Wed. Feb. 27, 10:00pm

Subject: hw#11

and an attachment

hw11FirstNameLastName.txt

and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

1. Add appropriate error messages to procedures GaleSh(M,W) and GaleShT(M,W) that makes sure it is EXACTLY the way we want it

2. By using GaleShT(M,W), write a short programs, GaleShTw(M,W) , where Women do the proposing and men respond. Hint: it should be a one-liner. Make sure to invert the first output of GaleShTw(W,M).

3. Write a program

   CheckOpt(M,W)

   that inputs M and W, finds the matchings where the men do the proposing and the one where the women do it, and verify that each man got a better (or equal) wife (in his eyes) and each woman get a worse (or equal) husband in the first case.

4. Implement the case described on p. 82 of
   Notes on Introductory Combinatorics by Polya, Tarjan, and Wood.
   where some people rather be single then marry someone they can't stand. In other words, where the M[i] and W[j] are not always (necessarily) of length n.

5. Compare the "stupid" way, FindStable(M,W,K), with K=10000, with GaleShT(M,W) for many random choices given by RT(n). For small n, does the stupid way fare better sometimes? What is the "cutoff" of n where FindStable(M,W,K) starts to be useless?

6. Write a procedure

   EstStat(n,K)

   That inputs a positive integer n , and a large positive integer K (at least 1000), generates K exaples of M,W (using RT(n)) and outputs the average number of proposals, followed by the standard-deviation.

   Run

   EstStat(n,10000)

   for n=10..., 150, (with increments of 10)

   Can you conjecture an approximate "trend"?

7. Let the "neighbors" of a permutation pi of length n be the n-1 permutations obtained by swapping ADJACENT entries. For example, the three neighbors of [3,1,2,4] are

   [1,3,2,4], [3,2,1,4], [3,1,4,2]

   By using

   CountInstablities(M,W,pi)

   that you wrote for hw10, write a procedure

   MayBeNotSoStupidFindStable(M,W)

   that starts out with a random permutation, looks at all its n-1 neighbors, and moves to the one with the least number of instablities. It keeps doing it until you either get a stable matching, or get into a "valley", where there are still instabilities, but none of the neighbors has less instabilities (then return FAIL). It should also record the number of iterations. How often does it give you a stable matching? Is it sometimes better than Gale-Shapley?

8. Get ready for the next class, by skimming Llyod Shapley's seminal paper about coalitions, and reading the first few pages of this nice exposition.

Added Feb. 28, 2022: The students' beautiful homework is in this directory

(In-person) Lecture 12, Monday, Feb. 28, 2022

Programs done on Feb. 28, 2022

• RG(n,K): inputs a positive integer n and nother positive integer K ,K outputs a random "n-person game" (not necessarilty super-additive) with entries in [0,K]

• FM(f,n): inputs a function from 2^{1,...n} (given as a "table") to pos. real numbres outputs g(T)= Sum of g(S) over all subsets S of T

  The data strunctre is a "table"

• BM(f,n): inputs a function from 2^{1,...n} to pos. real numbers outputs the function g(T)= Sum of (-1)^(|T|-|S|)*g(S) over all subsets S of T. It is the inverse of FM(f,n), i.e.

  FM(BM(g,n),n)=g and BM(FM(f,n),n)=f

Homework for Monday Feb. 28, 2022, class, due Sunday March 6, 10:00pm

Subject: hw#12

and an attachment

hw12FirstNameLastName.txt

1. [Due before next class, March 3] Carefully read the first part of Llyod Shapley's seminal paper and the wikipedia article

2. Write procedures

   CheckBMFM(n,K) and CheckFMBM(n,K)

   that inputs a random function, call it f, defined on subests of {1,...,n} and chackes that FM(BM(f,n),n)=f and BM(FM(f,n))=f, viewed as tables, by checking that you always get the same value if you evaluate it at any subset of {1,...n}

3. [5 dollars, I don't know the answer]

   Why doing, for a given set-valued table generated by RG(n,K), for specific n and K, e.g. n=3, K=10,
   evalb(f=BM(FM(f,n),n)) gives you, in Maple, "false"?
   while it should be "true" (and if you evaluate it at specific sets they always agree)

4. Write a procedure

   CheckSuperAdditivity(f,n)

   that inputs a function on the set of subsets of {1, ...,n} and outputs true iff for every two disjoint subsets S and T of {1,...,n}, you have

   f[S union T] ≥ f[S] + f[T]

   Check for a few random choices of FM(RG(5,20),5), it is indeed super-additive

5. Prove humanly that indeed FM(f,n) and BM(f,n) are inverses of each other.

6. [Added March 1, 2022: Typo corrected thanks to George Tsoukalas, who won a dollar]

   After loading C12.txt , to a Maple session,
   Enter the following one-line Maple code

   A:=proc(n) local f,S,PN,i1:PN:=powerset(n):for S in PN do f[S]:=nops(S)!:od: BM(f,n)[{seq(i1,i1=1..n)}];end:

   What OEIS (if any) is this sequence? Can you explain why?

Added March 7, 2022: The students' beautiful homework is in this directory

Lecture 13 (Thurs. , March 3, 2022)

Programs done on March 3, 2022

• RSG(n,K): A random SUPER-ADDITIVE n-person cooperative game, obtained by applying FM(f,n) to f gotten by RG(n,K)

• SV(f,n): Inputs a Coalition function (a function defined on powerset(n)) and outputs the list of length n, call it L, such that L[i] is the Shapley value of Player i.

• SVp(f,n): Same input and output as SV(f,n) but using the permutation approach (Warning, it starts getting slow for n=10)

• [Added after class]
  SVi(f,n,i): The Shapley value of Player i in the n-person game, where f is the "coalition function" defined on the set of subsets of {1,...,n}. This uses Eq. (13) (and (12)) in Llyod Shapley's seminal paper about coalitions.
  [Note the typo in Eq. (12): n should be n!, i.e. γ_n(s)=(s-1)!*(n-s)!/n!, where s=|S|) ]

• [Added after class]
  SVpF(f,n): Yet another version of SV(f,n), using the above SVi, the most efficient way.

Homework for Thurs. March 3, 2022, class, due Sunday March 6, 10:00pm

Subject: hw#13

and an attachment

hw13FirstNameLastName.txt

1. [Human problem] Read the Maple code (added after class) for procedure SVi(f,n,i) and (the accompanying SVpF(f,n)) and explain why we always have SVpF(f,n)=SVp(f,n). Why is it faster (for n starting at n=7)?

2. [Human Challenge] Prove that the approach embodied in SV(f,n) (that uses the axioms) also lead to the formula given by SVi (and hence that it gives the same as SVp(f,n)

3. Implement the more general formula given in the the wikipedia article to get what they call φ_C(v), i.e. the Generalized Shapley value. Call it SVC(f,n,C). Make sure that SVC(f,n,{i}) is the same as SVi(f,n,i). Use the first formula given there (analogous to SVi)

4. Added March 5, 2022: Natasha Ter-Saakov noticed that the formulas in wikipedia are not quite right as stated. So it is now an optional challenge (5 dollars) to get them right.

   Same as above, but using the second formula there. Call it SVC1(f,n,C). Make sure that SVC1(f,n,{i}) is the same as SVi(f,n,i). It is analogous to SV(f,n)
   Hint: what the article calls "synnergy" is our own BM(f,n). What they call v(S) is our f[S]. What they call φ_i(v) is our SVi(f,n,i).

5. Added March 5, 2022: Following Natasha Ter-Saakov's email, I tried it myself and also this one seems to not be right as stated. So it is now an optional challenge (5 dollars) to get them right.

   Implement the formulas for φ_i,j(v) Given there, using both formulas, call them SVij1(n,f,i,j) and SVij2(n,f,i,j)
   Make sure that

   add(SVij1(n,f,i,j),j=1..n)=SVi(n,f,i)   ,

   add(SVij2(n,f,i,j),j=1..n)=SVi(n,f,i)   ,

   for randomly chosen functions f, gotten from RSG(8,1000), and all i from 1 to 8.

Added March 7, 2022: The students' beautiful homework is in this directory

(In-person) Lecture 14, Monday, March 7, 2022

Programs done on March 7, 2022

• WMG(L,q): INPUTS a WIEGHTED-MAJORITY GAME L,q outputs the TABLE of PAYOFFS FOR ALL SUBESTS OF {1,..,n}, where n:=nops(L);

• SSV(L,q): The Shapley-Shubik vector of values of the Weighted Majority game L,q , where L is the list of weights and q is the cut-off. The stupid way.

• SSVc(L,q): The Shapley-Shubik vector of values of the Weighted Majority game L,q .THE CLEVER WAY

Homework for Monday March 7, 2022, class, due Sunday March 13, 10:00pm

Subject: hw#14

and an attachment

hw14FirstNameLastName.txt

1. Look at the wikipedia article Legislative elections in Israel, that has links to all the elections from 1949 to 2021.

   Pick three elections at random, write down the weights [number of seats] (that add up to 120) for each of them, call it L, and use SSVc(L,61) to find their Shapley-Shubik values.

   Added March 13, Vikrant Ashvinkumar and Robert Doughery-Bliss wrote nice Python code that enabled the systematic computation for all the elections. See here and here .

2. [Challenge, do your best. I don't know the answer]

   Let f(n,i) be the Shapley-Shubik value of player i (i goes from 1 to 2n) if the weights are [1,2,....2*n] and the cut-off is n(2n+1)+1. Can you find a formula, or at least an estimate, or an asymptotic formula, for f(n,i)?

Added March 13, 2022: The students' beautiful homework is in this directory.

Lecture 15 (Thurs. , March 10, 2022)

Programs done on March 10, 2022

• A(n) The integral of (x*(1-x))^n/(1+x^2) from x=0 to x=1. Outputs a linear combination of 1, log(2), and Pi that happens not to have log(2) if n is divisible by 4

• PiAp(n): The approximation of Pi by a rational number obtained by pretending that A(4*n) above is 0

• [Added after class]

  Ac(n): Same as A(n) above but much cleverer and faster, using the third-order recurrence gotten from the amazing Almkvist-Zeilberger algoirthm.

• [Added after class]

  PiApc(n): Same as PiAp(n) but using Ac(n) rather than A(n), hence much faster for larger n.

• ArcTanT(x,k): The truncation of the Taylor series of arctan(x) after k terms, followed by the rigorous error bound

• ATAN(L): Inputs a list of numbers (or symbols) L finds the quantity A such that
  arctan(A)= arctan(L[1])+...+arctan(L[k])

  Added March 21, 2022: Read Vikrant Ashvinkumar's insightful comment.

• FindMachin(a,k): finds the unique b such that ATAN([a$k,b])=1

• NorthM(N): The truncated Gregory-Leibnitz formula at N, giving most correct digits of π when N=10^k/2, e.g. NorthM(500000); It was discovered emprically, in 1988, by at the time undergraudate R.D. North

Homework for Thurs. March 10, 2022, class, due Sunday March 13, 10:00pm

Subject: hw#15

and an attachment

hw15FirstNameLastName.txt

1. Write a procedure

   DecDigits(a,K)

   that inputs a number a and outputs the LIST of its first K digits. For example,

   DecDigits(Pi,6);

   should be [3,1,4,1,5,9]

2. [Corrected March 13, 2022, 2:00 pm ET, thanks to Natasha Ter-Saakov]

   Read the excellent article by the late (amazing) Borwein brothers (Jonathan and Peter) and the equally amazing Carl Dilcher (may he live a long life), and after settings Digits to at least 1000, check out this phenomena by using the abobe procedure DecDigits to write a procedure

   WrongDigits(a,b,K)

   that inputs two numbers a and b and a positive integer K and outputs the list of places where their decimal digits differ up to the K-th place. Try:

   Digits:=1000: WrongDigits(Pi,NorthM(500000),100):

   [If it does not take too long, try:
   Digits:=1000: WrongDigits(Pi,NorthM(5000000),200): ]

   Is that sequence in the OEIS.

3. [Optional challenge, I don't know thw answer, 10 dollars] According to the Borwein-Borwein-Dilcher above-mentioned paper the discovery that the truncated version (where you truncate at half of a power of 10) gives most of the digits of Pi correctly, even though it is a terrible way to compute π) is due to (at the time) undergraduate student R.D. North. Where is he now?

4. [Corrected March 13, 2022, 2:00 pm ET, thanks to Natasha Ter-Saakov]

   Read the excellent paper by G. M. Phillips, and implement Archimedes's method (adapted to your day) by writing a procedure

   Archimedes(k,N)

   that inputs a small positive integer k, and a positive integer N and outputs what Phillips calls p_n and P_n, i.e. HALF the perimeter of an inscribed and circumscribed polygon with k*2^N sides. Note that Archimeder(k,1) is [2*k*sin(Pi/k),2*k*tan(Pi/k)]. Confirm Archimides' calculation by typing

   Archimedes(3,5)

5. Write a procedure

   BestMachin(a)

   That finds the (hopefully) unique k such that FindMachin(a,k) is as small as possible

   Is [seq(BestMachin(a),a=2..10)] in the OEIS? If not, should it be?

6. After class I added the procedures Ac(n) and PiApc(n). These use the third-order recurrence gotten by the amazing Almkvist-Zeilberger algorithm.

   by using the Maple command "time" show why, starting at a certain n, PiApc(n) is so much faster than PiAp(n). For what values of n does

   PiApc(n) ;

   returns something in less than 5 seconds, while

   PiAp(n);

   is hopeless?

7. Write a procedure

   Jesus(n)

   that finds the sum of the first n terms of Jesus Guillera's beautiful series for 128/π² given in his homepage (in a Ramanujan-style notation, that must be deciphered). What is the error in Jesus(20)?

8. [Optionsl challenge, I have no clue, 10 dollars]

   What's nice about Machin's formula is that FindMachin(1/5,4) has numerator 1 (or rather -1). Do there exist integres a and k ≥ 2 such that FindMachin(a,k) has this property that its numerator is -1 or 1?

9. [Optional challenge, I have no clue, 10 dollars]

   Is there a k and integers 6 ≤ a[1] ≤ a[2] ≤ a[k], b such that

   ATAN([1/a[1], ...,1/a[k],1/b])=1 OR ATAN([1/a[1], ...,1/a[k],-1/b])=1

   Note that, thanks to Machin

   ATAN([1/5, 1/5,1/5,1/5,-1/239])=1

Added March 13, 2022: The students' beautiful homework is in this directory.

(In-person) Lecture 16, Monday, March 21, 2022

Programs done on March 21, 2022

• inv(pi): the inverse of the permutation pi

• RandP(n,v) A random voting profile with n candidates and v voters

• RP(n,v): all the possible voting profiles with n candidates {1,...n} and v voters
• Cij(P,i,j): inputs a voting profile P and candidates i and j how many voters pefer i to j?

• Tour(P): inputs a voting profile and outputs the torunament such that M[i,j]=1 if i beat j otherwise -1, M[i,i]=0 and M[i,j]=0 if it is a tie

• SV(T): inputs a tournament (as a list of lists) with n players (n=nops(T)), and outputs the vector V[i]: how many other candiates did candidate i beat?

Homework for Monday March 21, 2022, class, due Sunday March 27, 10:00pm

Subject: hw#16

and an attachment

hw16FirstNameLastName.txt

1. Read and understand N.N. Yu's short proof of Arrow's theorem

2. Write a one-line procedure

   IsCondorcet(P)

   that inputs a voting profile P with v:=nops(P) voters and n:=nops(P[1]) candidates, and outputs true iff you have an instance of the Condorcet paradox. For example

   IsCondorect([[1,2,3],[2,3,1],[3,1,2]]); should be "true" but IsCondorect([[1,2,3],[1,2,3],[1,3,2]]); should be "false"

   (Hint, a voting profile P is Condorcet iff SV(Tour(P)) is NOT a permutation of [0,1,..., n-1])

3. Write a procedure

   ExactCond(n,v)

   that inputs positive integres n and v and outputs the EXACT ratio of voting profiles that are Condorcet.

4. Write a procedure

   EstCond(n,v,K)

   that inputs a large positive integer K, and integers n and v , and generates K random voting profiles with v voters and n candidates, and oututs the ratio (in floatig points) of those that happen to be Condorcet.

   Check it against ExactCond(n,v) for n=3 and v=3,4,5.

   for each of n=3,4,5, and v=20,30,40, run

   EstCond(n,v,10000)

   several times, make sure that you get close answers. Do you see a trend?

5. Look up "Borda count" and write a procedure

   Borda(P)

   that inputs a voting profile P and outputs the Borda score of the n candidates.

6. Write a procedure

   CondorcetRank(P)

   that inputs a voting profile P and outputs the ranking according to the Condorcet criterion. For example,

   CondorcetRank([[1,2,3],[1,2,3],[1,2,3]]);

   should output [{1},{2},{3}]

   while

   CondorcetRank([[1,2,3],[2,3,1],[3,1,2]]);

   should output [{1,2,3}]

7. Write a procedure

   BordaRank(P)

   that inputs a voting profile P and outputs the ranking according to the Borda criterion. For example,

   BordaRank([[1,2,3],[1,2,3],[1,2,3]]);

   should output [{1},{2},{3}]

   while

   BordaRank([[1,2,3],[2,3,1],[3,1,2]]);

   should output [{1,2,3}]

Added March 27, 2022: The students' beautiful homework is in this directory.

Lecture 17 (Thurs. , March 24, 2022)

Programs done on March 24, 2022

• Comps(n,k): The set of all compositions of n into exactly k parts (with non-negative entrties)

• GP1(L,n,d): Inputs a list of numbers L and a variable n and a non-neg. d outputs the polynomial of degree d P(n), such that P(i)=L[i], for all i from 1 to nops(L). OR FAIL

• GP(L,n): Inputs a list of numbers L and a variable n and outputs the polynomial of degree <=nops(L)-2 P(n), such that P(i)=L[i], for all i from 1 to nops(L). OR FAIL

• IsCond3(C): inputs a vote-count profile outputs true iff 1->2->3->1,

There is no hw17 (lucky you!)

(In-person) Lecture 18, Monday, March 28, 2022

Programs done on March 28, 2022

• IsCond3G(C,G): inputs a vote-count profile C and a cut-off matrix 2 by 3 matrix that for 1 ≤ i &;lt j ≤ 3, i beats j iff the number of voters that pefer i to j minus the voters that prefer j to is is ≥ G[i][j] outputs true iff 1->2->3->1

• Cond3G(v,G): The set of vote-count profiles with v voters that give 1->2->3->1

• NuC(v,G): The total number of voter-profiles (not to be confused with vote-count profiles) with 1->2->3->1 with v voters and handicap matrix G (the default is, G=[[0,1,1],[0,0,1]]).

• SeqCo(N,G): The first N terms of the sequence

  Number of G-Condorcet vote-count-profiles with 2*n-1 voters

• SeqCe(N,G): The first N terms of the sequence Number of G-Condorcet vote-count-profiles with 2*n voters

• SeqC(N,G): The first N terms of the sequence Number of G-Condorcet vote-count-profiles with n voters

Homework for Monday March 28, 2022, class, due Sunday April 3, 10:00pm

Subject: hw#18

and an attachment

hw18FirstNameLastName.txt

1. Read and understand Ein-Ya Gura and Michael Maschler's exposition of the proof of Arrow's theorem

2. Using procedure NuC(v,G) with G=[[0,1,1],[0,0,1]] write a one-line procedure

   SeqCoStupid(N)

   that inputs a positive integer N and outputs the first N terms of the sequence

   "Number of voting-profiles (NOT vote-count profiles) with 2*n-1 voters that lead to 1->2->3->1"

3. [A little bit challenging, do your best]

   Read this gem and implement Theorem 1 to write a procedure

   SeqCoSmart(N)

   that does the same thing as SeqCoStupid(N), but hopefully faster.

   [Hint, use the taylor command to exapand the rational function in t to N+1 terms, extract the first N coefficients of t, getting polynomials in the 6 variables, x123, ..., x321, and then apply the "umbra" as described in the paper.

   How much faster is SeqCoSmart(20) than SeqCoStupid(20)?

4. Try to estimate the limiting probability of the Codorcet scenari, by cranking out as many terms as you can and dividing by 6^(2*n-1) (and at the end mulitplying by 2)

5. [Optional challenge, I don't know the answer, 10 dollars, and possibly a paper]

   Find a nice combinatorial proof (if possible a bijective one) of the fact that we conjectured in class (and that can be made into an ugly proof) that the number of vote-count-Conrorcet scenariors with 2*v-1 voters is binomial(v+3,5) (recall that the total number of vote-count scenarios is binomial(2*v+4,5)

   Added March 31, 2022: It seems that Rebecca Embar solved it! She won the 10 dollars, but you are welcome to do it for fun.

   Added April 4, 2022: Read Rebecca Embar's beautiful bijective proof and accompanying Maple code here ,

6. A sequence of integers is a quasi-polynomial of degree d and period p if for i=1, ..,p the subsequence {L[p*n+i]},

   is a polynomial of degree d in n.

   Using GP(L,n), as a subroutine, first write a procedure

   GQP1(L,p,n)

   that inputs a list L and tries to guess a quasi-polynomial of period p that fits the data, and then write

   GQP(L,n)

   that tries out p=1, p=2, until either a success or failure. the output should be a list of polynomials in n,let's call it P, such that if n mod p=i (but we take i=1,...p, rather than the usual i=0,..,p-1) then L[n]=P[i][n]. For example

   GQP([1,-2,3,-4,5,-6,7,-8,9,-10,11,-12,13,-14])

   should output [n,-n]

   Added April 4, 2022: The students' beautiful homework is in this directory.

   ---

   Lecture 19 (Thurs. , March 31, 2022)

   Programs done on March 31, 2022

   C19.txt , contains
   • Umb1(M,var): inputs a MONOMIAL M in the list of variables var and applies the "umbra" c*var[1]^a1*...*var[k]^ak->c*(a1+...+ak)!/(a1!*..*ak!)

   • Umb(P,var): applying the above umbra to the polynomial P

   • Zs(N): The alleged(!) first N terms of the sequence: number of vote-profiles with the Condorcet scenario with v voters.

     It does not agree with NuC of C18.txt with G=[[0,1,1],[0,0,1]] (see homework below for a reward for fixing this discrepancy)

   Homework for Thurs. March 31, 2022, class, due Sunday April 3, 10:00pm

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: hw#19

   and an attachment

   hw19FirstNameLastName.txt

   1. (i) Write a procedure, UmbT(P,var,N), that inputs a polynomial P in a list of variables, var, say [x1,x2,x3, ..xk], and outputs the first N terms of the sequence that is the "umbral transform" under the umbra P^n under the umbra

      x1^a1 .... xk^ak -> (a1+...+ak)!/(a1!*...*ak!)

      (ii) What are the A-mumbers (if they exist) of the following sequences

      (a) UmbT(x+y,[x,y],20);

      (b) UmbT(x+y+z,[x,y,z],20);

      (c) UmbT(x1+x2+x3+x4,[x1,x2,x3,x4],20);

      (d) UmbT(1+2*x+3*y,[x,y],20);

      (e) UmbT((1+x)*(1+y)*(1+z),[x,y,z],20);

   2. [Optional challenge, 10 dollars to be divided among the solvers]

      To my dismay, procedure Zs does not agree with procedure NuC(v,G) of C18.txt . In other words, for example

      Zs(10) is NOT [seq(NuC(v,[[0,1,1],[0,0,1]]),v=1..10)]

      I don't have any clue why. At least one of them is wrong (possibly both!). Please fix it.

      Added April 4, 2022: quite a few people indicated the problem, but only Blair Seidler wrote the corrected code that is now part of C18.txt . Blair won the ten dollars.

   3. Carefully look at suggested projects and email me (to DoronZeil at gmail dot com) as soon as you decide on project, also indicate whether you are willing to be the team leader. The decision is due April 10.

   Added April 4, 2022: The students' beautiful homework is in this directory.

   ---

   (In-person) Lecture 20, Monday, April 4, 2022

   Programs done on April 4, 2022

   C20.txt , contains
   • P12(n):Regards a very simple children's game (suitable for ages 3 and up) where one starts with n pennies and the two players take turns removing either one or two pennies each time, and the player who is left with an empty pile is the loser. The input is the the current number of pennies and the the output is 1,S if it is a winning position and S is the set of legal moves or 0,{} if it is a losing positiion

   • PR(n,R):A more general version of the above where {1,2} is replaced by an arbitrary finite set of positive integers

   • LP(N,R): Inputs a pos. integer N and a removal set R outputs the list of losing positions ≤ N

   Homework for Monday April 4, 2022, class, due Sunday April 10, 10:00pm

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: hw#20

   and an attachment

   hw20FirstNameLastName.txt

   1. Write a procedure

      ConjLP(R)

      that inputs a finite set of positive integers R, and outputs the pair

      [M,C]

      where M is a positive integer ≥ 2 and C is a subset of {0,1,...,M-1} such that PR(n,R)[1]=0 if and only if n mod M belongs to C. For exmaple,

      ConjLP({1,2})

      should output

      [3,{0}]

      [Hint, first output LP(10000,R), call it, L, say, then look for the smallest M such that

      convert(L mod M,set)

      has less than M elements. This is your conjectured M. Then, for that M, convert(L mod M,set) is your conjectured C.

   2. [A little bit challenging, but do your best] Write a procedure

      ProveLP(R,M,C)

      that proves automatically the conjecture that indeed n is a losing position for the R-game iff n mod M belongs to C, or returns FAIL.

      Hint: the defining propery of the set of losing positions of a game is that every legal move (in this game, subtracting an element of R), is NOT in that set, and for every element, n, NOT in that set, there exists an element r, in R, such that n-r is in the set.

   3. The classical game of k-file Nim consists of k piles having n[1],..., n[k] pennies respectively, and a legal move consists of taking as many pennies as one wishes (from 1 to the whole pile) from ONE pile. For exmaple from the position [3,2,2] one can reach, in one move

      [2,2,2],[1,2,2],[0,2,2];[3,1,2],[3,0,2];[3,2,1],[3,2,0];

      Write a procedure

      Nim(N)

      that inputs a list of non-negative integers of length k:=nops(N) and outputs 0,{} if it is a losing position, and 1,S, if it is a winning positiion where S is a list of pairs {[a,b]} meaning: remove b pennies from the a-th pile. For example

      Nim([3,3]) should output "0,{}{ while Nim([7,3]) should output 1,{[1,4]}

      [Modified April 7, 2022: By symmety, the winning vs. losing status is invariant under permutation, so it would be more efficient just to output the list of weakly-increasing (or if you wish, weakly-decreasing) losing positions.

   4. Write a procedure

      NimL(k,N)

      that inputs a positive integer k, another positive integer N and outputs the set of lists of length k with entries ≤ N that are losing positions for k-pile Nim. For example

      NimL(2,3);

      should output {[0,0],[1,1],[2,2],[3,3]}

   5. [Optional challenge, please do it all by yourself] Without looking it up, find a quick way to decide whether a triple of non-negative integers [a,b,c] is a losing position in 3-pile Nim.

   6. Conisder a variant of 2-pile Nim where in addition to the Nim moves of removing any number of pennies in one of the piles, a player is also allowed to remove the SAME number of pennies from both piles. Write a procedure

      Nim2V(a,b)

      that inputs non-negative integers a and b and outputs 0,{} or 1,S where the members of S are either of the form [i,0],[0,i],[i,i]. For example,

      Nim2V(2,1)

      should output 0,{}

      Nim2V(3,2)

      should output

      1,{[1,1],[2,0]}

      [Added April 7, 2022: thanks to Natasha Ter-Saakov for correcting a previous error. She won a dollar]

   7. write a procedure

      Nim2VL(N)

      that inputs a positive integer N and outputs the LIST of pairs [a,b], 0 ≤ a ≤ b ≤ N, that are losing positions for the above game. with increasing order of the first component.

   8. [Optional challenge, please no peeking in the literature]

      Characterize such losing pairs.

   Added April 11, 2022: The students' beautiful homework is in this directory.

   [Also see Lucy Martinez's interesting observatiobs.]

   ---

   Lecture 21 (Thurs. , April 7, 2022)

   THIS LECTURE IS IN FOND MEMORY OF Jerrold B. Tunnell (Sept. 16, 1950- April 1, 2022).

   [Added April 13, 2022: See the bottom of this sad link .

   Programs done on April 7, 2022

   C21.txt , contains

   • aSeq(N): The first N terms of the sequence of a(n) defined by Jerrold Tunnell in Inv. Math. 72 (1983), 323-334

   • bSeq(N): The first N terms of the sequence of b(n) defined by Jerrold Tunnell in Inv. Math. 72 (1983), 323-334

   • JTseq(N): The terms of the sequence of congruent numbers ≤ N, those that are areas of right-angled triangle with rational sides. Shuold be called the Tunnell numbers. According to the version in Tunnell's paper

     [Needs more work!]

   • Tn(n,A,B,C): the set of triples [x,y,z] in Z^3 such that n=A*x^2+B*y^2+C*z^2

   • IsCon(n): Is n such that (mod. Birch-Swinterton-Dyer) is the area of right-angled triangle with RATIONAL sides

   • JTseqW(N): All the terms ≤ N of the sequence of congruent numbers, those that are areas of right-angled triangle with rational sides. Shuold be called the Tunnell numbers; Using the Wikipedia version

     [Needs more work!]

   Homework for Thurs. April 7, 2022, class, due Sunday April 10, 10:00pm

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: hw#21

   and an attachment

   hw21FirstNameLastName.txt

   1. Get procedure JTseq(N) of C21.txt to work properly. It is based on Jerrold Tunnell's seminal paper (Inv. Math. 72 (1983), 323-334.)

   2. Write a procedure

      IsSquareFree(n)

      that inputs a positive integer n and outputs true or false according to whether n is a product of DISTINCT primes or not, respectively. Use it to get procedure JTseqW(N) of C21.txt to work properly. It is based on the the wikipedia article on Tunnell's theorem

   3. [Optional challenge] Prove that the approaches of JTseq(N) and JTseqW(N) are equivalent.

   4. [Optional challenge, I have no idea how hard it is. $100 donation to the OEIS in memory of Jerry Tunnell (credited to the solvers). I will email Neil Sloane telling him to credit the donation to the solvers, rather than to myself]

      Implement (correctly!) the clever construction of Jerrold Tunnell's brilliant academic son Sasa Radomirovic.

      [Added April 11, 2022: Dr. Yuxuan Yang met this challenge! (and also found a typo!). See his brilliant implementation

   Added April 11, 2022: The students' beautiful homework is in this directory.

   ---

   (In-person) Lecture 22, Monday, April 11, 2022

   Programs done on April 11, 2022

   C22.txt , contains
   • mex(S): inputs a set of NON-NEGATIVE integers and outputs the smallest non-neg. intger NOT in the set S, i.e. min({0,1,2,3,...} minus S)

   • ai(i): the a-component in the losing position for Wythoff's game [a_i,i+a_i], using the Blair-Vikrant-Natahsa (and possibly other people)'s recurrence

   • aiC(i) : a much Faster way to compute ai(i) using Wythof's formula trunc(phi*i):

   • RDG(n,p): inputs a pos. integer n and a RATIONAL number p=a/b between 0 and 1 and outputs a random directed graph w/o cycles such tha the prob. of an edge is p

     ---

     [The procedures below were added after class]

   • Parents(G): inputs a directed graph on {1,...,n} where n:=nops(G) such that G[i] is the set of children of i (the set of outgoing neihbors) outputs the list whose i-th component is the set of "parents" of i, i.e. those j such that i belongs to G[j]. For example Parents([{2,3},{3},{}]); should be [{},{1},{1,2}]

   • OneStep0(G,AL,T): Given a graph G, with a set of already labelled vertices AL and a list T of lables performs one step in the labelling algorithm, the implication that if a vertex is labeled 0 then all its parents are labeled 1 (since there exists is a legal move that will make the opponent lose)

   • OneStep1(G,AL,T): Given a graph G, with a set of already labelled vertices AL and a list T of lables performs one step in the labelling algorithm, that if all the children of a vertex are already labeld 1 then it is labeled 0 (since whatever the player can do it would be winning for the opponent)

   • OneStep(G,AL,T): Given a graph G, with a set of already labelled vertices AL and a table T of lables performs one step in the labelling algorithm, either OneStep0 or OneStep1

   • LaG(G): inputs a directed graph G without cycles outputs the list of length n:=nops(G) giving the labels (0 if the vertex is a losing position, 1 if it is a winning position)

   Homework for Monday April 11, 2022, class, due Sunday April 17, 10:00pm

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: hw#22

   and an attachment

   hw22FirstNameLastName.txt

   1. By the definition of ai(i), the sets {ai(i),i=1..infinity} and {ai(i)+i,i=1..infinity} are disjoint and completey cover the set of positive integers (exactly!, i.e. no overlap). Assuming that ai(i)=trunc(i*alpha) for some real number alpha (this assumption is not obvious, and once the only eligible alpha is found needs a rigorous proof). Indeed there is only one thing alpha can be. Prove that if such an alpha exists, it must be the famous Golden Ratio.

   2. [Optional challenge] Try to reprove Wythoff's theorem that ai(i)=aiC(i). If you give up, look it up and try to understand the proof.

   3. Read and understand the Maple code for LaG(G) (and all its subroutines), added after class.

   4. Using LaG(G), write a procedure

      LP(G)

      that inputs a directed graph w/o cycles, G (let n:=nops(G)) and outputs the subest of {1,...,n} of its losing positions.

   5. Write a procedure

      AvNuLP(n,p,K)

      that inputs a positive integer n, a rational number p between 0 and 1 and a large integer K and outputs an approximation to the average size of the set of losing positions, for a random directed graph (w/o cycles) with n vertices, by averaging over K random graphs gotten from RDG(n,p).

      What did you get for

      AvNuLP(n,p,10000)

      for 3*4=12 cases

      n=10,50, 100; p=1/5,2/5,3/5,4/5

   Added April 18, 2022: The students' beautiful homework is in this directory.

   ---

   Lecture 23 (Thurs. , April 14, 2022)

   Programs done on April 14, 2022

   C23.txt , contains (in addition to C22.txt) the following new procedures
   • GenS(G): Inputs a directed graph (w/o cycles) and outputs a list of "generations" L[1] : the set of vertices that are sinks (no children), and L[i] the set of vertices all whose children are in L[1] ... union ...L[i-1]

   • LaGn(G): Same as LaG(G) from C22.txt, but hopefully better (at least more adaptable for the Centipede games, coming up next)

   • Els(): The Elster Centipede game taken from this brilliant opinion, using our data strcuturee for genearlized Centipede game G,[[Sink1, [Reward1a,Reward1b]], [[Sink2, [Reward2a,Reward2b]], ...

   Homework for Thurs. April 14, 2022, class, due Sunday April 17, 10:00pm

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: hw#23

   and an attachment

   hw23FirstNameLastName.txt

   1. Work on your class project with your teammates.

   2. Read the wikipedia article on the Centipede game and write a procedure

      WikiCent(n)

      That generalizes the four-stage game given there with payoffs (1,0),(0,2),(3,1),(2,4) at the bottom and to the extereme right (3,3)
      but please change the (3,3) to (3.1,3.1)
      to a 2n-stage game with payoffs, at the bottom

      (1,0),(0,2),(3,1),(2,4),(5,3),(4,6) ...., (2n-2,2n)
      and to the extereme right (2n-1+ 0.1,2n-1+0.1)

      It should be expressed in our data-structure like in Els() above. Name the n non-leaves on the top row in order, followed by the leaf at the extreme right, followed by the leaves at the bottom.

      The second part should be the reward table (but with our convention that the pair of rewards is [a,b], where a is the reward of the player currently at that vertex and b the reward of the other player. Regardless whether they happen to be Player I or Player II.

   3. By going back to at least your four grandparents (but the further back the better!) describe your own family "tree" (it is not really a tree, but a directed graph). Express it in our notation as a directed graph, followed by the "dictionary" the list of names such that L[i] is the name in real life of the vertex named i. For example for Dr. Z.'s immediate family it is

      [{3,4,5},{3,4,5},{6},{},{},{}], [DoronZeilberger,JaneLegrange,CeliaZeilberger,TamarZeilberger,HadasZeilberger,AlexandraAhmed]

      Another example

      [{3,4,5},{3,4,5},{},{},{6},{}],[Adam,Eve,Cain,Abel, Seth, Enos]

      (Of course, Enos had children, or else we would not be here, but this is the directed graph when Enos was a child)

      Apply GenS(G), and LaGn(G) to your family graph. For the most ancient generation in GenS(G) (the last in the list), find whether they are winning or losing if you use it to play the game. For example in Dr. Z.'s graph, Alexandra,Tamar, and Hadas are "losers", while Doron, Jane, and Celia are "winners".

      TEN DOLLAR PRIZE FOR THE LARGEST NUMBER OF GENERATIONS!

   4. [Human problem] Above I claimed that a family "tree" is not really a tree. For example, while I have eight distinct great-grandparents, my father only had six different great-grandparents, since his parents were first-cosuins (so he was his own second-cousin). Prove that we are each other's cousins!

   Added April 18, 2022: The students' beautiful homework is in this directory.

   ---

   (In-person) Lecture 24, Monday, April 18, 2022

   Programs done on April 18, 2022

   C24.txt , contains (in addition to C22.txt and C23.txt) the following new procedures
   • LabelP(L): inputs a list of pairs [[a_i,b_i]], outputs [b_j,a_j] where b_j is is the largest b_i
     [Corected after class]

   • LaC(G,R): Inputs a directed graph G, and R, a set of pairs [sink, [a,b]] outputs the list of labels of all the vertices
     [Done after class]

   • WikiCent(n): The centipede game 2*n non-leaf vertices and 2*n+1 leaves wich that 1 goes 2 and 2*n+2, 2 goes to 3 and 2*n+3, ..., 2*n goes to 2*n+1 and 4*n+1, and the reward pairs for vertex 2*n+1 is [2*n-1+0.1,2*n-1+0.1], the reward pair of vertex 2*n+2 is [0,1], and the reward pair for vertex [2*n+3+i] (i=0..2*n-2) is [i,i+2]

     WikiCent1(n): Same as WikiCent(n) but with ONE edge removed, making it beter for BOTH players

   • Els(): The original Elster graph

   • Els1(): The modified Elster graph that makes is better for both of them

   Homework for Thurs. April 14, 2022, class, due Sunday April 17, 10:00pm

   • Read and understand the corrected code for LabelP(L) (it was right the first time, before you made me change it) and LaC(G,R)
   • Work on your project
   There is no hw24 submission.

   ---

   Lecture 25 (Thurs. , April 21, 2022)

   Programs done on April 21, 2022

   C25.txt, contains (in addition to C22.txt, C23.txt, and C24.txt) the following new procedures
   • CP(G1,G2): the Cartesian product of the games G1 and G2 given in our data-structure, followed by the "dictionary" n1:=nops(G1): n2:=nops(G2): G1xG2 would have n1*n2 vertices

   • [Added after class]
     SG(G): The Sprague-Grundy function of a combinatorial game G, given as a directed graph (w/o cycles) in our convention where the vertices are called 1,...,n, (n=nops(G)) and G[i] is the set of vertices reachable from i in one legal move.

   Homework for Thurs. April 21, 2022, class, due Sunday April 24, 10:00pm

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: hw#25

   and an attachment

   hw25FirstNameLastName.txt

   1. Work on your class project with your teammates.

   2. Write a procedure

      BestPrune(G,R)

      that inputs a directed graph G followed by the set of Rewards {[i,[a,b]], i is a sink} and tries to see whether there exists an edge whose deletion will make the label of vertex 1 (the pay-offs) better for BOTH players. It should output the edge or FAIL. Test it with

      BestPrune(Els());

      BestPrune(WikiCent(20));

   3. Write a procedure

      RandCent(n,p,K)

      that generates a random centipded pair G,R, where G is RDG(n,p) and the payoffs for the sinks of G are random integers from 0 to K

   4. Write a procedure

      FindParadox(n,p,K,K1)

      That tries K1 times to generate RandCent(n,p,K) and stops as soon as it finds something that is not FAIL. If it can't find anything, it should return FAIL. What did you get for

      FindParadox(30,1/2,100,1000)?

   5. Read and understand the Maple code for procedure SG(G) added after class, and prove that a position (i.e. vertex), i, is a losing position (i.e. LaGn(G)[i]=0) if and only if SG(G)[i]=0.

   Added April 25, 2022: The students' beautiful homework is in this directory.

   ---

   (In-person) Lecture 26, Monday, April 25, 2022

   Programs done on April 25, 2022

   C26.txt , contains (in addition to C22.txt, C23.txt, C24.txt, and C25.txt) the following new procedures
   • SGnim(L): inputs a Nim position with k=nops(L) piles with L[i] pennies in pile i finds its Sprague-Grundy value

   • FindPer(L): finds the smallest period or return FAIL

   • NimSum(a,b): A better recursive description of the S-G value of 2-Nim position [a,b]
     [completed after class to enter the initial condition NimSum(0,0)=0]

   ---

   Homework for Monday April 25, 2022, class, due Sunday May 1, 10:00pm

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: hw#26

   and an attachment

   hw26FirstNameLastName.txt

   1. Work on your class project with your teammates.

   2. [Human challenging exercise, 10 dollars to be divided among all correct answers, no cheating please] Prove (by induction or otherwise) that

      NimSum(a,b)=SGnim([a,b])

      for all non-negative integers a and b

   3. Write a procedure

      SGwyt(a,b)

      that finds the Sprague-Grundy value of the position [a,b] in Wythoff's game whose rules are the same as 2-pile Nim, except that one can also remove the SAME number of pennies from both piles.

   4. Write a procedure

      FindUP(L)

      that inputs a list L and outputs a pair of lists L1,L2 such that (conjecturally)

      L=[op(L1),op(L2)^infinity]

      i.e., after an initial segment L1, it starts being periodic of period nops(L2)

   5. By using FindUP(L) and SGwyt(a,b), find(if possible) conjectured ultimate periodic descriptions of

      [seq(SGwyt(i,b)-b,b=0..infinity)]

      for i=0,1,2,3 (the further the better!)

   6. [Optional challenge, 10 dollars to be divided between all correct solutions] What is

      SGwyt(5,10¹⁰⁰)

   7. [Optional challenge, 100 dollars donation to the OEIS, I have no clue]

      While it is very fast to compute SGnim([10¹⁰⁰, 2*10¹⁰⁰]), do it! Find

      SGwyt([10¹⁰⁰, 2*10¹⁰⁰])

      More generally, find a fast algorithm (similar to NimSum), to compute SGwyt(a,b)

   Added May 2, 2022: The students' beautiful homework is in this directory.

   ---

   Lecture 27, Guest Lecture by Dr. Neil Sloane (Thurs. , April 28, 2022)

   Today we were lucky to have a guest-lecture by guru Neil Sloane. Here are his slides,

   Optional Homework due whenever

   Investigate some of the fascinating open problems, and if possible solve them.

   ---

   (In-person) Lecture 28, Monday, May 2, 2022

   There is no Maple code for today. We first proved Ariel Rubinstein's seminal result that if two players take turns proposing to share a dollar, and the other player can accept the proposal, and end the game immediately, or refuse, in which case it is his turn to propose, and they do it indefinitely. Due to inflation the current value shrinks by a factor of δ each time period, so it is to both players' interest to end the game as soon as possible, since the total amount keeps shrinking. Assuming that there is an equilibrium offer of the first player, let's call it R, i.e. to offer 1-R to the second player, if the second player refuses, now he is in the identicail position that the first person (since infinity-1=infinity), hence in equilibrium

   1-R=Rδ

   Solving for R, we get the following theorem:

   Ariel Rubinstein's theorem: The first player should offer δ/(1+δ) to the other player, and keep 1/(1+δ) for himself.

   We than discussed the repeated Prisoner's dillemma with discount factor δ and proved that if the payoff matrix is

   [[P,P],[T,S]]
   [[S,T],[C,C]]

   with

   T > C > P > S

   [T is the temptation payoff, C is the cooporation payoff, P is the punishment payoff (for defecting), and S is the sucker's payoff.]

   If you apply the trigger stragegy: Cooporate as long as your opponent does, but as soon as he defects, play Nash equilbrium. If

   δ ≥ (T-C)/(T-P)

   It is a so-called subgame perfect Nash Equilibrium for both opponents to apply the above trigger strategy, and they both will live happily ever after.

   Homework for Monday May 2, 2022, class, due Monday May 9, 8:00pm

   Work on your project and submit.

   Added May 10, 2022: Read the students' FASCINATING PROJECTS

   ---

   FIELD TRIP May 10, 2022

   On May 10, 2022, 8 out of the 12 students were able to come to the annual field trip to the Princeton cemetery (and this year also to St. Paul cemetery not far from it). We first visited Kurt Gödel, and John von Neumann (co-founder of Game Theory), then visited the graves of my good friend Herb Wilf's advisor Herbert Robbins, then the great "solver of problems", Dave Robbins (no relation), that has a beautiful engraving of 3D Ferrers diagrams of plane partitions, then the grave of Rutgers RUTCOR founder, Peter Hammer, then (since we had some extra time) the grave of Aaron Burr, and finally that of John Tukey (of Fast Fourier Transform fame).

   Then we went to St. Paul's cemetery and tried to find the grave of John Nash. I promised to give the book "The Essential John Nash" to the person who would find it. The lucky winner was Vikrant Ashvinkumar.

   GROUP PICTURE IN FRONT OF THE GRAVE OF JOHN AND ALICIA NASH

   After that we had a tasty dinner at the nearby Amazing Thai restaurant, also attended by my beloved wife, Dr. Jane D. LeGrange.

   ---

   Dr. Z.'s teaching page