-
Choose one of the followings:
- Modify the algorithm to handle cases (a) Ax<=b and (b) Ax=b, x>=0. Try to find variants of Farkas' lemma for these cases.
- Try to construct your own cycle.
-
Choose one of the followings:
- (The Fourier Elimination (FE)) In the class, an example of a set of inequalities solved with the Fourier Elimination was given. Similarly, write examples of at least 3 variables for feasible, infeasible and unbounded cases solved with the Fourier Elimination. With regard to your example for the infeasible case, can you find a certificate of infeasibility? (Try to make a general conclusion.)
- (Depth First Search (DFS)) There is a 3-D pyramid whose vertices are at (1,1,1), (0,0,0), (2,0,0), (2,2,0), (0,2,0). First, draw the pyramid and write a set of inequalities which are satisfied by any points on/inside the pyramid. Next, show the depth first algorithm for enumerating all vertices of the pyramid with (1,1,1) as the starting point.
- (The Fourier Elimination (FE) and Enumeration) With regard to the pyramid in the previous problem, show how to enumerate its vertices with the Fourier Elimination.
-
Exercise:
- (Enumeration with the Reverse Search) Using the pyramid in the previous lecture (April 20), show the reverse search algorithm for enumerating all vertices of the pyramid with (1,1,1) as the starting point.
- Exercise 5.1 of the tutorial (this requires you also solve Exercise 4.1)
-
Exercise:
- In the lecture, we have seen the following two types of CHSH inequalities when there are two parties: Alice who has two random variables Q and R, and Bob, who has two random variables S and T.
First, show that (1) and (2) are equivalent. Note that
.
Next, let
and 
be the observables of Alice which correspond to the random variables Q and R, respectively, such that 
and 
. Let also 
and 
be those of Bob which correspond to the random variables S and T, respectively such that 
and 
. Evaluate the following expression:
and show how much it violates the CHSH inequality. Note that
are Pauli matrices.
-
Exercise: Choose one of the followings
- Exercise 1:
- Exercise 2:
Exercise:
The above strategy can be defeated by Charlie if he switches to a=1=b always. Show (in spite of what I said in class) that there is a probabilistic (classical) strategy for Alice and Bob that gives this winning probability, no matter what Charlie does.
This exercise concerns zero sum games (ie. where A= -B for A and B are Alice and Bob's payoff matrix, respectively.)
(a) Find an example of a zero sum game which has several different Nash equilibria pairs (x,y).
(b) For every zero sum game, show there is a unique value r (called the value of the game) such that every equilibrium pair (x,y) yields expected payoff r to the first player.
In class we proved that it is NP-hard to find a Nash equilibrium that guarantees an expected payoff of at least r to each player (if one exists) for a bimatrix game. Using this fact, prove in detail the corollary:
It is NP-hard to find all Nash equilibria for a bimatrix game.
For details on the definition of NP-hard, you can read Section 5.2 and 5.3 of the class note here.