Abstract:

The talk will survey recent developments in the theory of repeated games with bounded complexity. (No prior knowledge of game theory is assumed.) Two instances of problems will be addressed (complete solution of A and a partial solution of B, as well as their relevance to the theory of repeated games with bounded complexity) are:

A) A problem of information transmission:

Consider a team of two players (P1 and P2) facing a (long or infinite) random sequence X=(x_1,x_2,...) of 0,1 bits. At stage t=1,2,... P1 outputs a 0,1 bit y_t and P2 outputs a 0,1 bit z_t. At each stage t the payoff to the team is 1 if y_t=z_t=x_t, and 0 otherwise. Player 1 is informed of the entire realization of the sequence X and Player 2 is not. Following the play at stage t, P2 observes x_t and y_t. The objective of the team is to maximize the number of stages t with y_t=x_t=z_t.

Before P1 gets the information of the realization of the entire sequence X, P1 and P2 can communicate and coordinate. Thereafter, all communication is via the observed output. Thus, a strategy of P1 specifies its sequence of actions Y=(y_1,y_2,...) as a function of X. The action of player 3 is to specify a sequence Z=(z_1,z_2,...) where z_{t+1} is a function of x_1,y_1,...,x_t,y_t.

The question that arises: is there a value v such that

1) P1 and P2 can secure against any sequence X a payoff of at least (v-o(1))n in the first n-stages, and

2) there is a distribution over the sequences X such that for every n and for every strategy pair of P1 and P2, the expectation of the score is no more then (v+o(1))n in the first n-stages.

B) A problem of concealed correlation:

Consider a finite set of factors N={1,...,n} and a stochastic process X(1),X(2),... where X(t)=(X_1(t),...,X_n(t)) is in the Cartesian product A of the finite sets A_1,...,A_n. The distribution of the process is induced by n independent random rules that govern the distinct factors. A deterministic rule that specifies the i-th factor is a function r_i that specifies, for each t, the coordinate X_i(t) as a function of X(1),...,X(t-1). A deterministic rule r_i has recall k if X_i(t) is only a function of X(t-k),...,X(t-1). A random rule mu_i is a probability distribution over deterministic rules. A list of independent random rules mu=(mu_1,...,mu_n) induces a probability distribution P(mu) on the sequences X(1),X(2),... (and the conditional distribution of X(t) given X(1),...,X(t-1) is a product distribution).

A question that arises: what is the asymptotic relation between k and m s.t. for a list of independent k-recall rules the (average over t) distribution of X(t) given X(t-m),...,X(t-1) is close to a product distribution.