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)
Thodoris Lykouris (Cornell University, USA)
Guido Schaefer (CWI & Vrije Universiteit, Netherlands)
Dimitris Tsipras (NTUA)
Alexandros Voudouris (University of Patras)

#### Organization

Stathis Zachos
Dimitris Fotakis
Vangelis Markakis

#### Local Arrangements

Antonis Antonopoulos
Dimitris Tsipras

# Program

(*Click on the icon to view talk details.)
 9:00 - 9:30 Registration - Coffee 9:30 - 10:30 Efficient Equilibria in Polymatrix Coordination GamesGuido Schaefer, CWI & Vrije Universiteit (VU) 10:30 - 11:00 Break 11:00 - 11:35 Learning and Efficiency in Games with Dynamic PopulationThodoris Lykouris, Cornell University 11:35 - 12:10 Efficient Money-Burning in General DomainsDimitris Tsipras, NTUA 12:10 - 12:45 Near-optimal asymmetric binary matrix partitions Alexandros Voudouris, University of Patras 12:45 - 14:30 Lunch Break 14:30 - 15:30 Robot EvacuationEvangelos Kranakis, Carleton University 15:30 - 16:00 Break 16:00 - 16:35 Efficiency and complexity of price competition among single-product vendorsPanagiotis Kanellopoulos, University of Patras 16:35 - 17:10 Multiple Referenda and Multi-winner Elections Using Hamming Distances: Complexity and ManipulabilityGiorgios 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.

Abstract:
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

Abstract:
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.

Abstract:
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.

Abstract:
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

Abstract:
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

Abstract:
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.

Abstract:
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

Register here for attendance:
Registration is closed

Hello

# Participants

First Name Last Name Affiliation
SpyridoulaAlmpaniNTUA
OrestisAlposECE NTUA
EvangelosAnagnostopoulosUoA
AntoniosAngelakisECE NTUA
AlexandrosAngelopoulosNTUA
StavropoulosAngelosNTUA
EiriniAngeloudiECE NTUA
StamatisAnoustisNTUA
AntonisAntonopoulosNTUA
MakisArsenisNTUA
CharalamposAsimakopoulosECE NTUA
GeorgiaAvarikiotiNTUA
AikateriniBaousiNTUA
AndreasBarosNTUA
EleniBatziouNTUA
GeorgiosBirmpasAUEB
PaschalisBizopoulosNTUA
GiannisBorektsioglouDIT UoA
EvangelosBousiosCS AUEB
AngelikiChalkiNTUA
RafaelCharalambousNTUA
AlexandraCharatsiAthens University Of Economics And Business
EvangelosChatziafratisNtua Student
ManolisChristoforouAUEB
ManolisChronakisECE
NikosChrysanthopoulosECE NTUA
StavrosChryselisUOA
AikateriniDagrentua
SmaragdaDallaAthens University of Econ and Bus
SotiriosDimosNTUA
PyliaEleniNTUA
EleniEvangelatouECE NTUA
VasilisEvangelou
IoannisFilippasECE NTUA
Maria FostiniNTUA
DimitrisFotakisNTUA
EvangelosFotopoulosStudent
MyrtoGalenianouUniversity of Athens
KonstantinosGavriilDI UoA
MariosGeorgiouCity University of New York
NikolaosGiannarosECE NTUA
GeorgiaGkiokaECE NTUA
DionisisGrigoropoulosAUEB
LulezimHamzaAthens University of Economics and Business
DimitriosKalimerisUniversity of Athens
ChrysostomosKaniourasECE NTUA
Grigoris KaragiorgosTEI of Peloponnese
IoannisKaramanolakisECE Student
ErtvalKarametaUoA
AnnaKarasoulouDI, UoA
PanagiotisKatrakazasBiomedical Engineering Laboratory, NTUA
KonstantinosKatsanosDepartment of Informatics and Telecommunications
AggelosKiayiasNational and Kapodistrian University of Athens
YiannisKonstantinouUOA
VasilikiKontouraNational Technical University of Athens
ChristosKoukoumialosAthens University of Economics and Business
KonstantinaKouriUniversity of Patras
Alexis Orfeas Kourkakis NTUA
VlasisKoutsosNTUA
EleniKouvelaNTUA
Chaido Kriki AUEB
GeorgeKrimpasUniversity of Patras
NickKrimpasUniversity of Patras
NikosKrisiliasaueb student
GiwrgosLabrinosNational and Kapodistrian University of Athens
KonstantinosLekkasEce ntua
VasilisLivanosNTUA
ThodorisLykourisCornell University
ChristianaLymouriNTUA
Polydoros AngelosManimanakisNtua
IoannisMantasDIT UoA
VasilisMargonisUniversity of Patras
VasilikiMarkaki-
VangelisMarkakisAthens University of Economics and Business
GeorgiosMatikasNational Technical University of Athens
DimitrisMatsisNTUA
DimitrisMegremis
AntoniosMeimarisUniversiy of Athens
OrestisMelkonianUOA
AlexandrosMetaxasNTUA
VasilisMilias
VelisariosMiloulisCompSci
Faidra GeorgiaMonachouNTUA
MariaMpampaAthens University of Econ and Bus
KonstantinosMpitsakosECE NTUA
DimitriosMyrisiotisNTUA
IoannisNemparisMPLA UoA
KaterinaNikolidakiNTUA
Aristotelis Ntelopoulos AUEB
KonstantinosNtemosDIT, UOA
VasileiosNtokosAthens university of economics and business
MarthaOikonomouStudent
ArisPagourtzisNTUA
GiorgosPanagiotakosUoA-DI
IoannisPapaioannouMPLA
ThemistoklisPapameletiouNTUA
DespoinaPapatheodorouNTUA
KonstantinosPatsourakosDIT UOA
MariaPetrouuniversity of patras
StavrosPetsalakisDIT UoA
NikosPhiliopoulosT.E.I of Epirus
OrestisPlevrakisECE NTUA
ChristophorosPliakosAUEB
CharaPodimataNTUA
AlexandrosPolichronopoulosComputer Science Student
PetrosPotikasNTUA
GeorgeProimakisECE NTUA
DionysisRigopoulosNTUA
AgapiRissakiECE NTUA
GeorgiosRoutisNTUA
DimitrisSakavalasNTUA
KaterinaSamariNational and Kapodistrian University of Athens
AlexiosSaougkosDepartment of psysics and maths, NTUA
LydiaSimantirakisUOA
ConstantineSioumalasNTUA
AnnaSpyropoulouUoA
KonstantinosStratisShmmy
ZoisTasoulas
GrigoriosThanasoulasECE NTuA
VassileiosTsalavoutisNTUA
YiannisTselekounisUoA
LeonidasTsepenekasNTUA
AlexandrosTsilirisSemfe
GeorgiosTsimosAUEB
DimitrisTsiprasNTUA
AlexiosTsitsimpisNTUA
IoannaTziallaECE NTUA
NikosTziavelisECE NTUA
SofiaTzimaECE NTUA
IsidorosTziotisMPLA
NikolaosVasileiouECE NTUA
GeorgiosVlassopoulosSEMFE NTUA
Emmanouil VasileiosVlatakis GkaragkounisECE NTUA
EleftheriaVolianakiUniversity of Patras
Alexandros VoudourisUniversity of Patras
IoannaVoulkoudiSEMFE,NTUA
Panayiotis YiannisVrionisNtua
ConstantinosVrionisNTUA
AlexandrosZacharakis NTUA
ThomasZachariasNational and Kapodistrian University of Athens
StathisZachosNTUA
LydiaZakynthinouNTUA
BingshengZhangUOA
GiorgosZirdelisNTUA
ΛεωνίδαςΜπέηςΟΠΑ
ΑσπασίαΣτρούβαληAthens University of Economics and Business

# Venue

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.