Algorithmic Game Theory Athens 2016

x Learning in Strategic Environments: Theory and Data
Vassilis Syrgkanis, Microsoft Research

Abstract:
The strategic interaction of multiple parties with different objectives is at the heart of modern large scale computer systems and electronic markets. Participants face such complex decisions in these settings that the classic economic equilibrium is not a good predictor of their behavior. The analysis and design of these systems has to go beyond equilibrium assumptions. Evidence from online auction marketplaces suggests that participants rather use algorithmic learning. In the first part of the talk, I will describe atheoretical framework for the analysis and design of efficient market mechanisms, with robust guarantees that hold under learning behavior, incomplete information and in complex environments with many mechanisms running at the same time. In the second part of the talk, I will describe a method for analyzing datasets from such marketplaces and inferring private parameters of participants under the assumption that their observed behavior is the outcome of a learning algorithm. I will give an example application on datasets from Microsoft's sponsored search auction system.

x Fast Convergence of Common Learning Algorithms in Games
Thodoris Lykouris, Cornell University

Abstract:
We show that learning algorithms satisfying a low approximate regret property experience fast convergence to approximate optimality in a large class of repeated games. Our property, which simply requires that each learner has small regret compared to a (1+ϵ)-multiplicative approximation to the best action in hindsight, is ubiquitous among learning algorithms - it is satisfied even by the vanilla Hedge forecaster. Our results improve upon recent work of Syrgkanis et al. [SALS15] in a number of ways. We improve upon the speed of convergence by a factor of n, the number of players, and require only that the players observe payoffs under other players' realized actions, as opposed to expected payoffs. We further show that convergence occurs with high probability, and under certain conditions show convergence under bandit feedback. Both the scope of settings and the class of algorithms for which our analysis provides fast convergence are considerably broader than in previous work. Our framework applies to dynamic population games via a low approximate regret property for shifting experts. Here we strengthen the results of Lykouris et al. [LST16] in two ways: We allow players to select learning algorithms from a larger class, which includes a minor variant of the basic Hedge algorithm, and we increase the maximum churn in players for which approximate optimality is achieved. In the bandit setting we present a novel algorithm which provides a "small loss"-type bound with improved dependence on the number of actions and is both simple and efficient. This result may be of independent interest.

x Does Information Revelation Improve Revenue?
Christos Tzamos, Massachusetts Institute of Technology

Abstract:
We study the problem of optimal auction design in a valuation model, explicitly motivated by online ad auctions, in which there is two-way informational asymmetry, in the sense that private information is available to both the seller (the item type) and the bidders (their type), and the value of each bidder for the item depends both on his own and the item’s type. Importantly, we allow arbitrary auction formats involving, potentially, several rounds of signaling from the seller and decisions by the bidders, and seek to find the optimum co-design of signaling and auction (we call this optimum the "optimum augmented auction"). We characterize exactly the optimum augmented auction for our valuation model by mapping it to a related multi-item Bayesian auction with additive bidders. Surprisingly, in the optimum augmented auction, there is no signaling whatsoever, and in fact the seller need not access the available information about the item type until after the bidder chooses his bid. Suboptimal solutions to this problem, which have appeared in the recent literature, are shown to correspond to well-studied ways to approximate multi-item auctions by simpler formats, such as grand-bundling (this corresponds to Myerson’s auction without any information revelation), selling items separately (this corresponds to Myerson’s auction preceded by full information revelation as in [Fu et al. 2012]), and fractional partitioning (this corresponds to Myerson’s auction preceded by optimal signaling). Consequently, all these solutions are separated by large approximation gaps from the optimum revenue.

x An algorithmic problem behind Crowdsourcing, Learning and Concentration Bounds
Manolis Zambetakis, Massachusetts Institute of Technology

Abstract:
In this model we consider computation tasks that could be done in environments where we don't know if the whole input that we have is correct. Instead we are able to verify if a specific point of the input is correct but this costs and our goal is find algorithms that produce an approximately optimal solution and minimize the number of points that we have to verify. This a very natural situation that could arise in crowd-sourcing environments where we cannot be sure that all the workers have done their job correctly. In the recent paper by Moran et. al. [1] they proved the relation of such a problem with classical PAC learning tasks by relating the number of points in the input that we have to check with the VC dimension of the function that we want to learn. In this regime we provide efficient algorithm for both approximately verifying the optimality of a solution and for correcting an incorrect solution using as less as possible verification of the input points. We also provide connections of the verification task with the concentration of the function that we want to compute under random input through the Talagrand inequality.

[1] Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff. Compressing and Teaching for Low VC-Dimension. FOCS 2015: 40-51

x Competitive Equilibrium and Trading Networks: A Network Flow Approach
Markos Epitropou, University of Pennsylvania

Abstract:
In trading networks where agents exchange indivisible goods (or indivisible contracts), recent literature has established that under a full substitutability condition on agents’ preferences, a competitive equilibrium exists. Moreover, competitive equilibria of trading networks are also stable outcomes, which is equivalent to the seemingly weaker chain stability condition. This paper’s contribution is to show that under the full substitutability assumption, all these results can be obtained simply and directly from the optimality conditions of a generalized submodular flow problem in an appropriately defined network.

x Approximation Algorithms for Computing Maximin Share Allocations
George Amanatidis, Athens University of Economics and Business

Abstract:
We study the problem of computing maximin share guarantees, a recently introduced fairness notion. Given a set of n agents and a set of goods, the maximin share of a single agent is the best that she can guarantee to herself, if she would be allowed to partition the goods in any way she prefers, into n bundles, and then receive her least desirable bundle. The objective then in our problem is to find a partition, so that each agent is guaranteed her maximin share. In settings with indivisible goods, such allocations are not guaranteed to exist, so we resort to approximation algorithms. Our main result is a 2/3-approximation, that runs in polynomial time for any number of agents. This improves upon the algorithm of Procaccia and Wang, which also produces a 2/3-approximation but runs in polynomial time only for a constant number of agents. To achieve this, we redesign certain parts of their algorithm. Furthermore, motivated by the apparent difficulty, both theoretically and experimentally, in finding lower bounds on the existence of approximate solutions, we undertake a probabilistic analysis. We prove that in randomly generated instances, with high probability there exists a maximin share allocation. This can be seen as a justification of the experimental evidence reported in relevant works. Finally, we provide further positive results for two special cases that arise from previous works. The first one is the intriguing case of 3 agents, for which it is already known that exact maximin share allocations do not always exist (contrary to the case of 2 agents). We provide a 7/8-approximation algorithm, improving the previously known result of 3/4. The second case is when all item values belong to {0,1,2}, extending the {0,1} setting studied in Bouveret and Lema\^itre. We obtain an exact algorithm for any number of agents in this case.

Joint work with Evangelos Markakis, Afshin Nikzad, and Amin Saberi.

x On Truthful Mechanisms for Maximin Share Allocations
George Birbas, Athens University of Economics and Business

Abstract:
We study a fair division problem with indivisible items, namely the computation of maximin share allocations. Given a set of n players, the maximin share of a single player is the best she can guarantee to herself, if she would partition the items in any way she prefers, into n bundles, and then receive her least desirable bundle. The objective then is to find an allocation, so that each player is guaranteed her maximin share. Previous works have studied this problem mostly algorithmically, providing constant factor approximation algorithms. In this work we embark on a mechanism design approach and investigate the existence of truthful mechanisms. We propose three models regarding the information that the mechanism attempts to elicit from the players, based on the cardinal and ordinal representation of preferences. We establish positive and negative (impossibility) results for each model and highlight the limitations imposed by truthfulness on the approximability of the problem. Finally, we pay particular attention to the case of two players, which already leads to challenging questions.

x The Unreasonable Fairness of Maximum Nash Welfare
Iannis Caragiannis, University of Patras

Abstract:
The maximum Nash welfare (MNW) solution — which selects an allocation that maximizes the product of utilities — is known to provide outstanding fairness guarantees when allocating divisible goods. And while it seems to lose its luster when applied to indivisible goods, we show that, in fact, the MNW solution is unexpectedly, strikingly fair even in that setting. In particular, we prove that it selects allocations that are envy free up to one good — a compelling notion that is quite elusive when coupled with economic efficiency. We also establish that the MNW solution provides a good approximation to another popular (yet possibly infeasible) fairness property, the maximin share guarantee, in theory and — even more so — in practice. While finding the MNW solution is computationally hard, we develop a nontrivial implementation, and demonstrate that it scales well on real data. These results lead us to believe that MNW is the ultimate solution for allocating indivisible goods, and underlie its deployment on a popular fair division website.

Joint work with David Kurokawa, Herve Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang.

x Mechanism Design for Scheduling with Uncertain Execution Time
Angelina Vidali, Teesside University UK

Abstract:
Crowdsourcing tasks to agents, in the context of processing big data, creates a lot of uncertainty about the execution times. We study the problem where a task (or multiple unrelated tasks) must be executed, there are multiple machines/agents that can potentially perform the task, and our objective is to minimize the expected sum of the agents' processing times. Each agent does not know exactly how long it will take him to finish the task; he only knows the distribution from which this time is drawn. Agents are selfish and will lie about their distributions if this increases their expected utility. We construct a mechanism that makes it an ex-post equilibrium for the agents to both truthfully report their distributions and exert full effort. We would further like to characterize all possible mechanisms. Joint work with Vincent Conitzer, (Duke University, USA) and ongoing work with Carmine Ventre (Teesside University).

x Asymptotically Tight Bounds for Inefficiency in Risk-Averse Selfish Routing
Thanasis Lianeas, University of Texas

Abstract:
We consider a nonatomic selfish routing model with independent stochastic travel times for each edge, represented by mean and variance latency functions that depend on arc flows. This model can apply to traffic in the Internet or in a road network. Variability negatively impacts packets or drivers, by introducing jitter in transmission delays which lowers quality of streaming audio or video, or by making it more difficult to predict the arrival time at destination. The price of risk aversion (PRA) has been defined as the worst-case ratio of the cost of an equilibrium with risk-averse players who seek risk-minimizing paths, and that of an equilibrium with risk-neutral users who minimize the mean travel time of a path [Nikolova and Stier-Moses, 2015]. This inefficiency metric captures the degradation of system performance caused by variability and risk aversion. In this paper, we provide the first lower bounds on the PRA. First, we show a family of structural lower bounds, which grow linearly with the size of the graph and players' risk-aversion. They are tight for graph sizes that are powers of two. We also provide asymptotically tight functional bounds that depend on the allowed latency functions but not on the topology. The functional bounds match the price-of-anarchy bounds for congestion games multiplied by an extra factor that accounts for risk aversion. Finally, we provide a closed-form formula of the PRA for a family of graphs that generalize series-parallel graphs and the Braess graph. This formula also applies to the mean-standard deviation user objective-a much more complex model of risk-aversion due to the cost of a path being non-additive over edge costs.

x On the Impact of Social Cost in Opinion Dynamics
Katia Papakonstantinopoulou, University of Athens

Abstract:
We study the formation of opinions in a social context. It has been observed that when in a social environment people often average their opinion with their friends’ opinions, so as to highlight their common beliefs. We analyze a popular social network and verify that social interaction indeed results in influence on opinions among the participants. Moreover we create instances of the network using real data and, based on the game theory framework, we experimentally show that the repeated averaging process results to Nash equilibria which are illustrative of how users really behave.

x Opinion Dynamics with Local Interactions
Stratis Skoulakis, National Technical University of Athens

Abstract:
We study convergence properties of opinion dynamics with local interactions and limited information exchange. We adopt a general model where the agents update their opinions in rounds to a weighted average of the opinions in their neighborhoods. For fixed neighborhoods, we present a simple randomized protocol that converges in expectation to the stable state of the Friedkin-Johnsen model. For opinion-dependent neighborhoods, we show that the Hegselmann-Krause model converges to a stable state if each agent's neighborhood is restricted either to a subset of her acquaintances or to a small random subset of agents. Our experimental findings indicate that for a wide range of parameters, the convergence time and the number of opinion clusters of the neighborhood-restricted variants are comparable to those of the standard Hegselmann-Krause model.

x Truthful Incentivization Schemes for Vehicle Sharing Systems
Alexandros Angelopoulos, National Technical University of Athens

Abstract:
The major operational problem in one-way vehicle sharing systems is the vehicle stock imbalance problem. In this paper, we address this problem by proposing a new approach for dynamically allocating vehicles to users based on ``incentivization" schemes which use reservations to coordinate supply-and-demand mismatches and price incentives for rewarding users, if they accept to pick up their vehicle from an oversupplied station and/or to drop off it to an under-supplied station. The system incentivizes users based on the priorities of vehicle relocations from station to station, taking into account the fluctuating demand for vehicles and parking places at different stations over time. We present two different schemes for incentivizing users to act in favour of the system. Both schemes consider budget constraints and are truthful and budget-feasible. We extensively evaluated our approach through simulations and observed significant improvements in the number completed trips and system revenue.