My research interests lie primarily in 2 fields:

Theoretical Computer Science. This mainly includes design and analysis of algorithms, approximation/randomized algorithms, combinatorial optimization, complexity theory.

Game Theory. Especially algorithmic game theory, design of mechanisms for auctions or voting systems, complexity of computing game theoretic solution concepts.

For Undergraduate Students:
As you see, I am more interested in theoretical approaches and in using mathematics to analyze the complexity of algorithms, or to analyze stable outcomes in game theoretic environments.

Among the courses you attend in our department, the most relevant ones to my interests are: Discrete mathematics, Data structures, Algorithms, Automata theory and complexity, Special topics on algorithms, Game theory and decision theory. If you are interested in carrying out your Bachelor's thesis with me, I expect that you have done well in these courses. I have supervised experimental theses as well, so it is not always the case that you will have to do only theoretical work, but I do want you to have a good understanding of the content of the above courses.

In order for you to have an idea about possible topics that we could work on, please take a look also at my publication list , and especially papers that have been written within the last 5-6 years. Please also feel free to contact me to discuss this further.

Below is a list of Bachelor's theses I have supervised in the last years.

Lefteris Mpetsos (Spring 2011). Lefteris' thesis focused on studying algorithms for computing approximate Nash equilibria in normal form games. Among the algorithms he studied, he performed an experimental evaluation of an algorithm by H. Bosse, J. Byrka and myself that achieves a 0.36-approximation guarantee for 2-player games. His experiments reveal that on average the algorithm performs much better than the theoretical guarantee.

Christos-Alexandros Psomas (Fall 2010 and Spring 2011). Alexandros worked on a fair division problem. Usually in fair division (also referred to as cake-cutting), we have a set of resources that we need to allocate to a set of players, each of which has his own utility function. Following up on the work of T. Hill (1987), we came up with a polynomial time algorithm that produces an allocation of indivisible goods to the players so that every player is guaranteed to receive a certain quantity that depends on the input of each instance in a certain way (identified by T. Hill). We furthermore studied game theoretic aspects of this problem and had some positive and (mainly) negative theoretical results. The results of Alexandros' thesis led to a publication in the conference Workshop of Internet and Network Economics (WINE), 2011.

Yannos Sorokos (Fall 2010). Yannos studied various issues regarding voting systems and especially the topic of manipulating elections. He implemented an algorithm that has been recently proposed by M. Zuckerman, O. Lev and J. Rosenschein (published in AAMAS 2011) for computing coalitions of voters that can manipulate an election. He investigated how much better the algorithm performs on average compared to the theoretical worst-case guarantee.

Alexandra Papoutsaki (Fall 2010). Alexandra implemented one of the so-called "no-regret" algorithms in the context of sponsored search auctions. She studied questions regarding convergence of these bidding strategies to an equilibrium and convergence of the produced revenue.

For Master's Students:
If you are coming from our M.Sc. program in Computer Science, I expect that you have done well in the courses "Algorithms and data structures" and "Special topics in theoretical computer science". Read also the information above for undergraduate students as parts of that applies to you as well.

If you are coming from our M.Sc. program in Information Systems, then (since there are no courses on algorithms there) I would expect that you have some familiarity with theoretical analysis of algorithms and/or with game theory and in general you have a solid mathematical background.

Below is a list of M.Sc. theses I have supervised in the last years.

Christos Alatzidis (M.Sc.-CS, 2011-2012). Combinatorial Auctions, ongoing work.

Christina Aretha (M.Sc.-CS, 2010-2011). An Introduction to Rational Cryptography. This is a topic that combines game theory and cryptography. It consists of contributions of game theory to cryptography by moving away from the traditional obedient/malicious model and taking into account rationality properties of the agents. It also consists of contributions of cryptography to game theory in terms of implementing certain equilibrium concepts.

Angelos Asimakopoulos (M.Sc.-CS, 2010-2011). On the Minimax Approval Voting Rule. The complexity of a certain voting rule is onvestigated. This is a problem that arises in voting systems that use so-called "approval" ballots, i.e., each voter either approves or disapproves of a certain candidate. Unfortunately the problem of computing the minimax outcome is NP-hard and the design of approximation algorithms was investigated.

Maria Sotiri (M.Sc.-IS, Fall 2010). Data Analysis and Bidding Strategies in Sponsored Search Auctions. The thesis contains an experimental analysis of a dataset on real sponsored search auctions made available by Yahoo. The main focus of the thesis was the behavior of the Click-Through-Rates, i.e. the probability that each of the available slots in a sponsored search auction receives a click.

Ioanna Anastasopoulou (M.Sc.-CS, 2009-2010). Analysis of Path Coloring Games. This thesis studied game theoretic approaches regarding optical networks and specifically routing problems in optical networks.

For (prospective) PhD Students:

Please read first the information above about B.Sc. and M.Sc. students as some parts apply to you as well. Most importantly, take a look at my publication list , as this is the best way to see the set of topics I have been working on. If any of these problems seem interesting to you, get in touch with me.