Game Theory

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.

Giorgios Amanatidis (AUEB)

Panagiotis Kanellopoulos (

Evangelos Kranakis (

Thodoris Lykouris (

Guido Schaefer (

Dimitris Tsipras (

Alexandros Voudouris (

Dimitris Fotakis

Vangelis Markakis

Dimitris Tsipras

(*

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.

Guido Schaefer,

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.

Dimitris Tsipras,

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.

Thodoris Lykouris,

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.

Alexandros Voudouris,

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.

Evangelos Kranakis,

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.

Panagiotis Kanellopoulos,

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.

Giorgios Amanatidis,

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.

Hello

First Name | Last Name | Affiliation |
---|---|---|

Spyridoula | Almpani | NTUA |

Orestis | Alpos | ECE NTUA |

Evangelos | Anagnostopoulos | UoA |

Antonios | Angelakis | ECE NTUA |

Alexandros | Angelopoulos | NTUA |

Stavropoulos | Angelos | NTUA |

Eirini | Angeloudi | ECE NTUA |

Stamatis | Anoustis | NTUA |

Antonis | Antonopoulos | NTUA |

Makis | Arsenis | NTUA |

Charalampos | Asimakopoulos | ECE NTUA |

Georgia | Avarikioti | NTUA |

Aikaterini | Baousi | NTUA |

Andreas | Baros | NTUA |

Eleni | Batziou | NTUA |

Georgios | Birmpas | AUEB |

Paschalis | Bizopoulos | NTUA |

Giannis | Borektsioglou | DIT UoA |

Evangelos | Bousios | CS AUEB |

Angeliki | Chalki | NTUA |

Rafael | Charalambous | NTUA |

Alexandra | Charatsi | Athens University Of Economics And Business |

Evangelos | Chatziafratis | Ntua Student |

Manolis | Christoforou | AUEB |

Manolis | Chronakis | ECE |

Nikos | Chrysanthopoulos | ECE NTUA |

Stavros | Chryselis | UOA |

Aikaterini | Dagre | ntua |

Smaragda | Dalla | Athens University of Econ and Bus |

Sotirios | Dimos | NTUA |

Pylia | Eleni | NTUA |

Eleni | Evangelatou | ECE NTUA |

Vasilis | Evangelou | |

Ioannis | Filippas | ECE NTUA |

Maria | Fostini | NTUA |

Dimitris | Fotakis | NTUA |

Evangelos | Fotopoulos | Student |

Myrto | Galenianou | University of Athens |

Konstantinos | Gavriil | DI UoA |

Alkis | Georgiadis-Harris | NTUA |

Marios | Georgiou | City University of New York |

Agisilaos | Georgoulias | undergraduate |

Nikolaos | Giannaros | ECE NTUA |

Georgia | Gkioka | ECE NTUA |

Dionisis | Grigoropoulos | AUEB |

Georgios | Hadjiharalambous | NTUA ECE |

Lulezim | Hamza | Athens University of Economics and Business |

Dimitrios | Kalimeris | University of Athens |

Chrysostomos | Kaniouras | ECE NTUA |

Grigoris | Karagiorgos | TEI of Peloponnese |

Ioannis | Karamanolakis | ECE Student |

Ertval | Karameta | UoA |

Anna | Karasoulou | DI, UoA |

Panagiotis | Katrakazas | Biomedical Engineering Laboratory, NTUA |

Konstantinos | Katsanos | Department of Informatics and Telecommunications |

Aggelos | Kiayias | National and Kapodistrian University of Athens |

Yiannis | Konstantinou | UOA |

Vasiliki | Kontoura | National Technical University of Athens |

Christos | Koukoumialos | Athens University of Economics and Business |

Konstantina | Kouri | University of Patras |

Alexis Orfeas | Kourkakis | NTUA |

Vlasis | Koutsos | NTUA |

Eleni | Kouvela | NTUA |

Chaido | Kriki | AUEB |

George | Krimpas | University of Patras |

Nick | Krimpas | University of Patras |

Nikos | Krisilias | aueb student |

Giwrgos | Labrinos | National and Kapodistrian University of Athens |

Konstantinos | Lekkas | Ece ntua |

Vasilis | Livanos | NTUA |

Thodoris | Lykouris | Cornell University |

Christiana | Lymouri | NTUA |

Marios | Magioladitis | Ionian University |

Polydoros Angelos | Manimanakis | Ntua |

Ioannis | Mantas | DIT UoA |

Vasilis | Margonis | University of Patras |

Vasiliki | Markaki | - |

Vangelis | Markakis | Athens University of Economics and Business |

Georgios | Matikas | National Technical University of Athens |

Dimitris | Matsis | NTUA |

Dimitris | Megremis | |

Antonios | Meimaris | Universiy of Athens |

Orestis | Melkonian | UOA |

Alexandros | Metaxas | NTUA |

Vasilis | Milias | |

Velisarios | Miloulis | CompSci |

Faidra Georgia | Monachou | NTUA |

Maria | Mpampa | Athens University of Econ and Bus |

Konstantinos | Mpitsakos | ECE NTUA |

Dimitrios | Myrisiotis | NTUA |

Ioannis | Nemparis | MPLA UoA |

Katerina | Nikolidaki | NTUA |

Aristotelis | Ntelopoulos | AUEB |

Konstantinos | Ntemos | DIT, UOA |

Vasileios | Ntokos | Athens university of economics and business |

Martha | Oikonomou | Student |

Aris | Pagourtzis | NTUA |

Giorgos | Panagiotakos | UoA-DI |

Vasileios-Orestis | Papadigenopoulos | NTUA |

Michalis | Papadopoullos | ECE NTUA |

Platon | Papadopoulos | NTUA |

Peggy | Papadopoulou | AUEB |

Ioannis | Papaioannou | MPLA |

Themistoklis | Papameletiou | NTUA |

Despoina | Papatheodorou | NTUA |

Konstantinos | Patsourakos | DIT UOA |

Maria | Petrou | university of patras |

Stavros | Petsalakis | DIT UoA |

Nikos | Philiopoulos | T.E.I of Epirus |

Evdokia Christina | Pierrou | SEMFE (graduate) |

Orestis | Plevrakis | ECE NTUA |

Christophoros | Pliakos | AUEB |

Chara | Podimata | NTUA |

Alexandros | Polichronopoulos | Computer Science Student |

Petros | Potikas | NTUA |

George | Proimakis | ECE NTUA |

Dionysis | Rigopoulos | NTUA |

Agapi | Rissaki | ECE NTUA |

Georgios | Routis | NTUA |

Dimitris | Sakavalas | NTUA |

Katerina | Samari | National and Kapodistrian University of Athens |

Alexios | Saougkos | Department of psysics and maths, NTUA |

Selman | Serif-Damadoglou | ECE NTUA |

Lydia | Simantirakis | UOA |

Constantine | Sioumalas | NTUA |

Anna | Spyropoulou | UoA |

Konstantinos | Stratis | Shmmy |

Zois | Tasoulas | |

Grigorios | Thanasoulas | ECE NTuA |

Vassileios | Tsalavoutis | NTUA |

Yiannis | Tselekounis | UoA |

Leonidas | Tsepenekas | NTUA |

Alexandros | Tsiliris | Semfe |

Georgios | Tsimos | AUEB |

Dimitris | Tsipras | NTUA |

Alexios | Tsitsimpis | NTUA |

Ioanna | Tzialla | ECE NTUA |

Nikos | Tziavelis | ECE NTUA |

Sofia | Tzima | ECE NTUA |

Isidoros | Tziotis | MPLA |

Nikolaos | Vasileiou | ECE NTUA |

Georgios | Vlassopoulos | SEMFE NTUA |

Emmanouil Vasileios | Vlatakis Gkaragkounis | ECE NTUA |

Eleftheria | Volianaki | University of Patras |

Alexandros | Voudouris | University of Patras |

Ioanna | Voulkoudi | SEMFE,NTUA |

Panayiotis Yiannis | Vrionis | Ntua |

Constantinos | Vrionis | NTUA |

Alexandros | Zacharakis | NTUA |

Thomas | Zacharias | National and Kapodistrian University of Athens |

Stathis | Zachos | NTUA |

Lydia | Zakynthinou | NTUA |

Bingsheng | Zhang | UOA |

Giorgos | Zirdelis | NTUA |

Λεωνίδας | Μπέης | ΟΠΑ |

Ασπασία | Στρούβαλη | 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.

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.