Download como arquivo ICAL
Seminário LIAMF: Coherence of Probabilistic Constraints on Nash Equilibria
Terça-feira 09 Outubro 2018, 14:30 - 15:30

Palestrante: Sandro Preto

Resumo: Stationary games are games that reached one of possibly many Nash equilibria but, due to uncertainty, the profile of actions of the equilibrium is unknown. We study the decision problem consisting of setting the probabilities of a set of actions and determining if that set of constraints can be jointly achieved, which we call the coherence of Probabilities Constraints on Equilibria, or PCE-Coherence. When only pure Nash equilibrium is considered, we show that PCE-Coherence problem can be reduced in polynomial time to the Probabilistic Satisfiability problem (PSAT); if only NP-games are allowed, that is, games whose equilibrium can be determined in NP, then PCE-Coherence is NP-complete. We also investigate the complexity of this problem when mixed Nash equilibria are allowed. We discuss how the problem of finding maximal and minimal constraints on pure strategies, the PCE-Extension problem, can be reduced to PCE-Coherence.

Sobre o palestrante: É doutorando em Ciência da Computação no IME-USP.

Local Auditório do CCSL