M. Mavronicolas, A. Philippou, Ch. Georgiou

As its name suggests, Algorithmic Game Theory illuminates the properties of algorithmic complexity that are inherent to Game Theory. Algorithmic Game Theory is currently an area of intensive activity by the research community of the Theory of Computing. In this area, we explore the following three specific targets:

• Computation of Nash Equilibria: In our study, we consider specific strategic games, and we pursue extension of techniques from Combinational Optimization and Network Flows to design and analyze efficient (polynomial) algorithms to compute Nash equilibria. We also study the complexity of computing Nash equilibria for the special case of Congestion Games (and several variants of them).
• The Price of Anarchy: This is a measure of the efficiency loss in a computer system due to the selfish behavior of its users. We prove lower and upper bounds on the Price of Anarchy for several computer systems that are modeled as strategic games.
• The Conjecture of the Fully Mixed Nash Equilibrium: This conjecture asserts that the fully mixed Nash equilibrium, a special type of a mixed Nash equilibrium, maximizes the Social Cost of a computer system. Our study identifies cases of strategic games (and corresponding conditions on them) where the Conjecture applies or not. This activity is financially supported by the European Union via the Basic Research Projects DELIS (Dynamically Evolving, Large Scale Information Systems) and AEOLUS (Algorithmic Principles for Building Efficient Overlay Computers).