ATTENTION:   May 27th, 2015, Athens
National Technical University of Athens
Room: Multimedia Amphitheater of the Central Library of N.T.U.A.

Algorithmic Game Theory Athens occurs this year for the first time.
Its purpose is to give the opportunity to graduate students in Greece to observe
talks of researchers from all areas of Algorithmic Game Theory.

Invited Speakers:
Giorgios Amanatidis (AUEB)
Panagiotis Kanellopoulos (University of Patras)
Evangelos Kranakis (Carleton University, Canada)
Thodoris Lykouris (Cornell University, USA)
Guido Schaefer (CWI & Vrije Universiteit, Netherlands)
Dimitris Tsipras (NTUA)
Alexandros Voudouris (University of Patras)


Stathis Zachos
Dimitris Fotakis
Vangelis Markakis

Local Arrangements

Antonis Antonopoulos
Dimitris Tsipras


PDF Version    (expand ↓)

(*Click on the icon to view talk details.)
9:00 - 9:30 Registration - Coffee
9:30 - 10:30 Go to Abstract Efficient Equilibria in Polymatrix Coordination Games
Guido Schaefer, CWI & Vrije Universiteit (VU)
10:30 - 11:00 Break
11:00 - 11:35 Go to Abstract Learning and Efficiency in Games with Dynamic Population
Thodoris Lykouris, Cornell University
11:35 - 12:10 Go to Abstract Efficient Money-Burning in General Domains
Dimitris Tsipras, NTUA
12:10 - 12:45 Go to Abstract Near-optimal asymmetric binary matrix partitions
Alexandros Voudouris, University of Patras
12:45 - 14:30 Lunch Break
14:30 - 15:30 Go to Abstract Robot Evacuation
Evangelos Kranakis, Carleton University
15:30 - 16:00 Break
16:00 - 16:35 Go to Abstract Efficiency and complexity of price competition among single-product vendors
Panagiotis Kanellopoulos, University of Patras
16:35 - 17:10 Go to Abstract Multiple Referenda and Multi-winner Elections Using Hamming Distances: Complexity and Manipulability
Giorgios Amanatidis, Athens University of Economics and Business

x Efficient Equilibria in Polymatrix Coordination Games
Guido Schaefer, CWI & Vrije Universiteit (VU)

Joint work with Krzysztof Apt, Mona Rahn and Sunil Simon.

We consider coordination games on graphs where every player corresponds to a node in a graph who benefits from coordinating with her neighbors. We study the existence of equilibria in these games both with respect to unilateral and group deviations. Further, we derive tight bounds on the inefficiency of these equilibria and settle the complexity of several computational questions related to these games. Finally, we investigate natural means to reduce the inefficiency of Nash equilibria.
x Efficient Money-Burning in General Domains
Dimitris Tsipras, NTUA

Joint work with Dimitris Fotakis, Christos Tzamos and Emmanouil Zampetakis

We study mechanism design where the payments charged to the agents are not in the form of monetary transfers, but effectively burned. In this setting, the objective shifts from maximizing social welfare, to maximizing social utility, i.e. the social welfare minus the payments charged. We consider the general setting with m discrete outcomes and n multidimensional agents. We present mechanisms that provide optimal worst case guarantees with respect to maximizing social utility, while simultaneously approximating the optimal social welfare within a constant factor. Such mechanisms are obtained by defining a maximization problem on a suitably chosen smooth surface of probability distributions. This approach leads to a closed-form, smooth mechanism and we believe to be of independent interest.
x Learning and Efficiency in Games with Dynamic Population
Thodoris Lykouris, NTUA

Joint work with Vasilis Syrgkanis and Eva Tardos.

We study the quality of outcomes in games when the population of players is dynamically changing, and where participants have to adapt to the dynamic environment. Price of Anarchy has originally been introduced to study the Nash equilibria of one-shot games, but has been extended since to repeated setting, assuming all players use learning strategies, and the environment, as well as the player population is stable. We show that in large classes of games (including congestion games), if players use a form of learning that helps them to adapt to the changing environment, this guarantees high social welfare, even under very frequent changes.
x Near-optimal asymmetric binary matrix partitions
Alexandros Voudouris, University of Patras

Joint work with Fidaa Abed and Ioannis Caragiannis.

We study the asymmetric binary matrix partition problem that was recently introduced by Alon et al. (WINE 2013) to model the impact of asymmetric information on the revenue of the seller in take-it-or-leave-it sales. Instances of the problem consist of an n x m binary matrix A and a probability distribution over its columns. A partition scheme B=(B_1,...,B_n) consists of a partition B_i for each row i of A. The partition B_i acts as a smoothing operator on row i that distributes the expected value of each partition subset proportionally to all its entries. Given a scheme B that induces a smooth matrix A^B, the partition value is the expected maximum column entry of A^B. The objective is to find a partition scheme such that the resulting partition value is maximized. We present a 9/10-approximation algorithm for the case where the probability distribution is uniform and a $(1-1/e)$-approximation algorithm for non-uniform distributions, significantly improving results of Alon et al. Although our first algorithm is combinatorial (and very simple), the analysis is based on linear programming and duality arguments. In our second result we exploit a nice relation of the problem to submodular welfare maximization.
x Robot Evacuation
Evangelos Kranakis, Carleton University

Consider $k$ mobile robots inside a circular disk of unit radius. The robots are required to evacuate the disk through an unknown exit point situated on its boundary. We assume all robots having the same (unit) maximal speed and starting at the centre of the disk. The robots may communicate in order to inform themselves about the presence (and its position) or the absence of an exit. The goal is for all the robots to evacuate through the exit in minimum time. We consider two models of communication between the robots: in {\em non-wireless} (or {\em local}) {\em communication} model robots exchange information only when simultaneously located at the same point, and {\em wireless communication} in which robots can communicate one another at any time. We study the following question for different values of $k$: what is the optimal evacuation time for $k$ robots? We provide algorithms and show lower bounds in both communication models for $k=2$ and $k=3$ thus indicating a difference in evacuation time between the two models. We also obtain almost-tight bounds on the asymptotic relation between evacuation time and team size, for large $k$. We show that in the local communication model, a team of $k$ robots can always evacuate in time $3 + \frac{2\pi}{k}$, whereas at least $3 + \frac{2\pi}{k} - O(k^{-2})$ time is sometimes required. In the wireless communication model, time $3 + \frac{\pi}{k} + O(k^{-4/3})$ always suffices to complete evacuation, and at least $3+ \frac{\pi}{k}$ is sometimes required. This shows a clear separation between the local and the wireless communication models.
x Efficiency and complexity of price competition among single-product vendors
Panagiotis Kanellopoulos, University of Patras

We study marketplaces that contain multiple vendors offering identical or similar products and unit-demand buyers with different valuations on these vendors. The objective of each vendor is to set the price of its product to a fixed value so that its profit is maximized. The profit depends on the vendor’s price itself and the total volume of buyers that find the particular price more attractive than the price of the vendor’s competitors. We model the behaviour of buyers and vendors as a two-stage full-information game and study a series of questions related to the existence, efficiency (price of anarchy) and computational complexity of equilibria in this game. To overcome situations where equilibria do not exist or exist but are highly inefficient, we consider the scenario where some of the vendors are subsidized in order to keep prices low and buyers highly satisfied.
x Multiple Referenda and Multi-winner Elections Using Hamming Distances: Complexity and Manipulability
Giorgios Amanatidis, Athens University of Economics and Business

Joint work with Nathanael Barrot, Jerome Lang, Evangelos Markakis, and Bernard Ries.

We study multiple referenda and committee elections, when the ballot of each voter is simply a set of approved binary issues (or candidates). Two well-known rules under this model are the commonly used candidate-wise majority, also called the minisum rule, as well as the minimax rule. In the former, the elected committee consists of the candidates approved by a majority of voters, whereas the latter picks a committee minimizing the maximum Hamming distance to all ballots. As these rules are in some ways extreme points in the whole spectrum of solutions, we consider a general family of rules, using the Ordered Weighted Averaging (OWA) operators. Each rule is parameterized by a weight vector, showing the importance of the i-th highest Hamming distance of the outcome to the voters. The objective then is to minimize the weighted sum of the (ordered) distances. We study mostly computational, but also manipulability properties for this family. We first exhibit that for many rules, it is NP-hard to find a winning committee. We then proceed to identify cases where the problem is either efficiently solvable, or approximable with a small approximation factor. Finally, we investigate the issue of manipulating such rules and provide conditions that make this possible.


Register here for attendance:
(please use English characters)
  Registration is closed



First Name Last Name Affiliation
OrestisAlposECE NTUA
AntoniosAngelakisECE NTUA
EiriniAngeloudiECE NTUA
CharalamposAsimakopoulosECE NTUA
GiannisBorektsioglouDIT UoA
EvangelosBousiosCS AUEB
AlexandraCharatsiAthens University Of Economics And Business
EvangelosChatziafratisNtua Student
NikosChrysanthopoulosECE NTUA
SmaragdaDallaAthens University of Econ and Bus
EleniEvangelatouECE NTUA
IoannisFilippasECE NTUA
Maria FostiniNTUA
MyrtoGalenianouUniversity of Athens
KonstantinosGavriilDI UoA
MariosGeorgiouCity University of New York
Agisilaos Georgouliasundergraduate
NikolaosGiannarosECE NTUA
GeorgiaGkiokaECE NTUA
GeorgiosHadjiharalambousNTUA ECE
LulezimHamzaAthens University of Economics and Business
DimitriosKalimerisUniversity of Athens
ChrysostomosKaniourasECE NTUA
Grigoris KaragiorgosTEI of Peloponnese
IoannisKaramanolakisECE Student
AnnaKarasoulouDI, UoA
PanagiotisKatrakazasBiomedical Engineering Laboratory, NTUA
KonstantinosKatsanosDepartment of Informatics and Telecommunications
AggelosKiayiasNational and Kapodistrian University of Athens
VasilikiKontouraNational Technical University of Athens
ChristosKoukoumialosAthens University of Economics and Business
KonstantinaKouriUniversity of Patras
Alexis Orfeas Kourkakis NTUA
Chaido Kriki AUEB
GeorgeKrimpasUniversity of Patras
NickKrimpasUniversity of Patras
NikosKrisiliasaueb student
GiwrgosLabrinosNational and Kapodistrian University of Athens
KonstantinosLekkasEce ntua
ThodorisLykourisCornell University
MariosMagioladitisIonian University
Polydoros AngelosManimanakisNtua
IoannisMantasDIT UoA
VasilisMargonisUniversity of Patras
VangelisMarkakisAthens University of Economics and Business
GeorgiosMatikasNational Technical University of Athens
AntoniosMeimarisUniversiy of Athens
Faidra GeorgiaMonachouNTUA
MariaMpampaAthens University of Econ and Bus
KonstantinosMpitsakosECE NTUA
IoannisNemparisMPLA UoA
Aristotelis Ntelopoulos AUEB
KonstantinosNtemosDIT, UOA
VasileiosNtokosAthens university of economics and business
MichalisPapadopoullosECE NTUA
KonstantinosPatsourakosDIT UOA
MariaPetrouuniversity of patras
StavrosPetsalakisDIT UoA
NikosPhiliopoulosT.E.I of Epirus
Evdokia ChristinaPierrouSEMFE (graduate)
OrestisPlevrakisECE NTUA
AlexandrosPolichronopoulosComputer Science Student
GeorgeProimakisECE NTUA
AgapiRissakiECE NTUA
KaterinaSamariNational and Kapodistrian University of Athens
AlexiosSaougkosDepartment of psysics and maths, NTUA
SelmanSerif-DamadoglouECE NTUA
GrigoriosThanasoulasECE NTuA
IoannaTziallaECE NTUA
NikosTziavelisECE NTUA
SofiaTzimaECE NTUA
NikolaosVasileiouECE NTUA
GeorgiosVlassopoulosSEMFE NTUA
Emmanouil VasileiosVlatakis GkaragkounisECE NTUA
EleftheriaVolianakiUniversity of Patras
Alexandros VoudourisUniversity of Patras
Panayiotis YiannisVrionisNtua
AlexandrosZacharakis NTUA
ThomasZachariasNational and Kapodistrian University of Athens
ΑσπασίαΣτρούβαληAthens University of Economics and Business


AGaThA 2015 will take place in the Multimedia Amphitheater of the National Technical University of Athens, located in the basement of the building of NTUA's Central Library. See the map below:

You can arrive at the Central Library by various ways:

By public transport:

The easiest way is by taking the Blue Metro line and getting off at the "ΚΑΤΕΧΑΚΗ" station. Then take the bus 242, get off at stop "ΘΥΡΩΡΕΙΟ" and walk 5 minutes towards the Central Library.
Another option is to take the bus 140 from the "ΚΑΤΕΧΑΚΗ" metro station and get off at stop "ΠΟΛΥΤΕΧΝΕΙΟΥΠΟΛΗ". Then get into the campus and walk 10 minutes towards the Central Library.

By car:

You can use this google map to get directions from Alimou-Katechaki Avenue.