GAME 2010 (part 2)

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 \textsc{Nash Equilibrium} problem, as well as
\textsc{Another End of Lines}, which graciously reduces to \textsc{Sperner}
(and viceversa). The reduction from AEL to \textsc{Sperner} passes through
the planar version of AEL. AEL is defined on a large DAG (|V| =  2^n 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 \textsc{Brouwer}, \textsc{Tuck} and \textsc{Fixed Point}. 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)”


  1. No Comments

Leave a Reply

You must login to post a comment.