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.