Defesa de Proposta de Tese de Doutorado de Marcos Felipe Medeiros de Souza, em 06/09/2024, às 10:00 horas, por videoconferência
Link para defesa: https://meet.google.com/epy-myna-ntc
Algoritmos e Caracterizações para Estratégias Vencedoras em Jogos Combinatórios em Grafos
Resumo:
A Teoria dos Jogos tem como objetivo analisar situações onde o resultado da ação de indivíduos, grupos ou instituições depende das decisões dos demais indivíduos envolvidos, isto é, nenhum agente pode tomar decisões de forma inteiramente desvinculada das possíveis decisões dos outros agentes, se não quiser incorrer em prejuízos e perdas. As principais motivações para o desenvolvimento da Teoria dos Jogos vêm do interesse em caracterizar o comportamento de agentes econômicos, levando à formulação de teorias econômicas, análise de processos competitivos e definição de estratégias de mercado. Muitas ferramentas matemáticas importantes surgiram para fundamentar os conceitos e avanços em Teoria dos Jogos, com notáveis contribuições de Zermelo, Sprague, Grundy, Von Neumann e Nash, entre outros lógicos e matemáticos. Neste trabalho estudamos jogos imparciais em grafos, que possuem as seguintes características: há dois jogadores que fazem as suas jogadas alternadamente sobre um tabuleiro que consiste em um grafo; o número de jogadas disponíveis é finito; o jogo é de informação completa, ou seja, os dois jogadores conhecem todos os movimentos possíveis e sabem identificar a situação atual do jogo; não existe acaso envolvido na determinação das jogadas; existe um critério que determina o fim de jogo, previamente acordado; o resultado final será de vitória para um dos jogadores, não havendo empate; e, finalmente, o jogo é imparcial, isto é, dada uma configuração do jogo, qualquer um dos dois jogadores poderia fazer exatamente as mesmas jogadas, caso fosse a sua vez de jogar. O Teorema de Zermelo afirma que, dadas as condições acima, um dos dois jogadores (Alice ou Bob) tem uma estratégia vencedora, isto é, uma sequência de decisões para suas jogadas que o levam à vitória, independentemente das jogadas realizadas pelo adversário. Apresentamos nessa Proposta de Tese estudos sobre o seguinte problema: fixado um jogo imparcial e dado um grafo $G$, determine qual dos dois jogadores tem uma estratégia vencedora para $G$, e qual é essa estratégia. Apresentamos algoritmos e caracterizações para alguns jogos e classes de grafos. As caracterizações se resumem na seguinte questão: Determine os grafos em que Alice (Bob) vence o jogo escolhido.
Abstract:
The aim of Game Theory is to analyze situations where the outcome of the actions of individuals, groups or institutions depends on the decisions of the other individuals involved, i.e. no agent can make decisions entirely disconnected from the possible decisions of other agents, if they don’t want to incur losses. The main motivations for the development of Game Theory come from the interest in characterizing the behavior of economic agents, leading to the formulation of economic theories, the analysis of competitive processes, and the definition of market strategies. Many important mathematical tools have emerged to underpin the concepts and advances in Game Theory, with notable contributions from Zermelo, Sprague, Grundy, Von Neumann, and Nash, among other logicians and mathematicians. In this paper we study impartial games on graphs, which have the following characteristics: there are two players who make their moves alternately on a board consisting of a graph; the number of moves available is finite; the game provides complete information, i.e. the two players know all the possi*ble moves and can identify the current situation of the game; there is no chance involved in determining the moves; there is a criterion that determines the end of the game, previously agreed; the result will be victory for one of the players, there being no draw; and finally, the game is impartial, that is, given a game configuration, either of the two players could make exactly the same moves if it were their turn to play. Zermelo’s Theorem states that, given the above conditions, one of the two players (Alice or Bob) has a winning strategy, i.e. a sequence of decisions for her/his moves that lead to victory, regardless of the moves made by their opponent. In this Thesis Proposal, we present studies on the following problem: given an impartial game and a graph $G$, determine which of the two players has a winning strategy for $G$, and determine that strategy. We present algorithms and characterizations for some games and classes of graphs. The characterizations are summarized in the following question: Determine the graphs in which Alice (Bob) wins the chosen game.
Banca examinadora:
Prof. Fábio Protti, UFF – Presidente
Prof. Luiz Satoru Ochi, UFF
Prof. Átila Arueira Jones, IF SUDESTE MG
Prof. Luerbio Faria, UERJ