Back to search

University of Patras

Αλγοριθμική και εξελικτική θεωρία παιγνίων

Abstract

dc:description

We developed two algorithms for computing an e-approximate Nash equilibrium for the case where e is an absolute constant. The approximations achieved by our algorithms are e=3/4 and e=(2+l)/4 respectively, where $\lambda$ is the minimum, among all Nash equilibria, payoff of either player. Furthermore, we studied a wide class of random two player games, for which we showed how to compute an e-approximate Nash equilibrium, where e tends to zero as the number of strategies of the players tends to infinity. Game theoretic concepts are useful in determining the impact that selfish behavior plays on the global performance of a system involving selfish entities. Towards this direction, we focused on the problem of load balancing. We studied the case where the agents are not necessarily fully informed about the exact values of their loads. We focused on several models of information (e.g. when all agents know nothing about the loads, or when each agents knows her own load) and, for each model, we characterized the set of Nash equilibria and analyzed their properties. Moreover, we bounded the coordination ratio, a measure which captures the impact that selfish behavior has to the global performance of the system, in contrast to the performance achieved by an optimum centralized algorithm. Besides the computational issues related to game theory, it is interesting to investigate whether game theory can help us in developing and analyzing algorithms for computationally difficult combinatorial optimization problems. Towards this direction, we studied from a game theoretic point of view the problem of vertex coloring. In particular, we properly defined the graph coloring game and we proved that every graph coloring game has a pure Nash equilibrium, and each pure Nash equilibrium corresponds to a proper coloring of the graph. We also showed that there exists a pure Nash equilibrium that uses an optimum number of colors, i.e. equal to the chromatic number. Furthermore, we developed and analyzed a polynomial time algorithm that computes a pure Nash equilibrium for any graph coloring game, using a number of colors satisfying most of the known classical bounds on the chromatic number.

Degree

thesis:*
Grantor dc:publisher
University of Patras
Year dc:date
2008

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Panagopoulou, Panagiota
  • Παναγοπούλου, Παναγιώτα

Subjects

dc:subject × 24

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/25731

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Panagopoulou, Panagiota; Παναγοπούλου, Παναγιώτα. Αλγοριθμική και εξελικτική θεωρία παιγνίων. University of Patras, 2008. http://hdl.handle.net/10442/hedi/25731