In the past days, Maria Florina Balcan has talked about machine learning in connection

with game theory. So one can imagine iterated games, played in turns, in which every

player learns from the outcome of his moves and the moves of his adversary.

The extension of some machine learning techniques to game theory is quite natural.

Think at the problem of making choices when aided by a group of experts (but we should

call them good chaps instead, since they may know nothing about the topic they are

giving advices…). One is willing to listen to the various advices, but would be happy

to be able to follow only the best possible advisor’s suggestions (the one who makes

the smallest number of errors). *Ex ante* it is not known who is the most reliable

advisor, so a way of letting the least expert among the experts is needed. This can

be achieved, for example, reducing progressively the weight of those experts who

make errors, so that their advice influences less the decision we will take.

Today Deng Xiaotie has told us about a new, for me, complexity class: PPAD

(guess who has introduced this class?).

Caught as usual by the argument, I harassed the poor Deng with many questions…

The PPAD class contains many problems that are also hard for the class. In

particular it contains the problem, as well as

, which graciously reduces to

(and viceversa). The reduction from AEL to passes through

the planar version of AEL. AEL is defined on a large DAG ( for a given n),

whose nodes have outdegree and indegree at most 1. A source node 1 is given,

having indegree 0 and outdegree 1. The objective is to find a node such that the

sum of his indegree and outdegree is equal to 1. Other problems in the class and

hard for it are , and . The nifty

thing is that all this reduction rely on parity arguments. From this fact the name

PPAD: P? Parity Argument Directed. I guess in two days we will now what the

first P stands for! By the way, now I should be working on some reductions from

the listed problems, so see you in a while…

## 0 Responses to “GAME 2010 (part 2)”