Schedule_of_Lectures-Workshops  

Suggested reading

• Krzysztof Apt Selfishness Level of Strategic Games

We introduce a new measure of the discrepancy in strategic games between the social welfare in a Nash equilibrium and in a social optimum, that we call  selfishness level. It is the smallest fraction of the social welfare that needs to be offered to each player to achieve that a social optimum is realized  in a pure Nash equilibrium. The selfishness level is unrelated to the price of stability and the price of anarchy and in contrast to these notions is  invariant under positive linear transformations of the payoff functions. Also, it naturally applies to other solution concepts and other forms of games.
We study the selfishness level of several well-known strategic games. This allows us to quantify the implicit tension within a game between  players' individual interests and the impact of their decisions on the society as a whole. Our analysis reveals that the selfishness level often provides more refined insights into the game than other measures of inefficiency, such as the price of stability or the price of anarchy. In particular, the  selfishness level of finite ordinal potential games is finite, while that of weakly acyclic games can be infinite. We derive explicit bounds on the
selfishness level of fair cost sharing games and linear congestion games, which depend on specific parameters of the underlying game but are independent  of the number of players. Further, we show that the selfishness level of the $n$-players Prisoner's Dilemma is $1/(2n-3)$, that of the $n$-players public  goods game is $(1-\frac{c}{n})(c-1)$, where $c$ is the public good multiplier, and that of the Traveler's Dilemma game is $\frac12$. Finally,  the selfishness level of Cournot competition (an example of an infinite ordinal potential game), Tragedy of the Commons, and Bertrand competition is  infinite.

Krzysztof R. Apt, Guido Schaefer, Selfishness Level of Strategic Games http://arxiv.org/abs/1105.2432

• Moshe Babaioff Optimal Mechanisms for Selling Information

The buying and selling of information is taking place at a scale unprecedented in the history of commerce, thanks to the formation of online marketplaces  for user data. Data providing agencies sell user information to advertisers to allow them to match ads to viewers more effectively. In this paper we study  the design of optimal mechanisms for a monopolistic data provider to sell information to a buyer, in a model where both parties have (possibly correlated)
private signals about a state of the world, and the buyer uses information learned from the seller, along with his own signal, to choose an action  (e.g., displaying an ad) whose payoff depends on the state of the world.  We provide sufficient conditions under which there is a simple  one-round protocol (i.e. a protocol where the buyer and seller each sends a single message, and there is a single money transfer) achieving optimal revenue. In these cases we present a polynomial-time algorithm that computes the optimal mechanism. Intriguingly, we show that multiple rounds of partial  information disclosure (interleaved by payment to the seller) are sometimes necessary to achieve optimal revenue if the buyer is allowed to abort his  interaction with the seller prematurely. We also prove some negative results about the inability of simple mechanisms for selling information to  approximate more complicated ones in the worst case.

• Liad Blumrosen Should I beat your price? Analysis of Sequential Competing Offers

Sellers often approach customers with competing offers. We study a dynamic market environment, where unit-demand customers sequentially arrive to the market. Sellers have identical goods for sale, and simultaneously publish offers to each arriving customer. Customers then decide whether to accept any of the offers, or leave the market for good. We characterize the equilibrium behavior in this setting, and show that the equilibrium strategies may be  symmetric or asymmetric. We provide a sufficient condition (which relates to the convexity of the virtual valuation) for the existence of a symmetric  equilibrium. We then show some corollaries of the equilibrium characterization, and show that some anomalies (like revenue and price non-monotonicity) can never occur in symmetric equilibria.

• Kevin Leyton-Brown Matching with Partial Information

The traditional model of two-sided matching assumes that all agents fully know their own preferences.As markets grow large, however,  it becomes impractical for agents to precisely assess their rankings over all agents on the other side of the market. We propose a novel model of  two-sided matching in which agents are endowed with known partially ordered preferences and unknown true preferences drawn from known  distributions consistent with the partial order. The true preferences are learned through interviews, which reveal the pairwise rankings among all  interviewed agents. Our goal is to identify a centralized interview policy, i.e., an algorithm which adaptively schedules interviews. We would like
the policy to produce a matching that is guaranteed to be both stable and optimal for a given side of the market, with respect to the underlying  true preferences of the agents. As interviews are costly, we seek a policy that minimizes the number of interviews. We introduce three potential  minimization objectives: (very weak) dominance, which minimizes the number of interviews for any underlying true preference profile; Pareto optimality,
which guarantees not being dominated by any other policy; and optimal-in-expectation with respect to the distribution. We formulate our problem as  an exponentially large Markov decision process. Thus, given access to the distributions of true preferences, the optimal-in-expectation  interviewing policy can be computed in exponential time. We show that it is possible to polynomially identify pairs that match in all or no underlying  preference profiles, but that such interviews nevertheless cannot be avoided by policies with our desired properties. We then derive  structural properties, called optimality certificates, of dominant policies. We show that computing a minimum optimality certificate is NP-hard.  This shows that constructing a dominant policy, if it exists, is NP-hard and suggests that even optimal-in-expectation policies might be NP-hard to  compute. Thus we restrict attention to a setting in which agents on one side of the market have common partially ordered preferences  (but potentially distinct underlying true preferences). In this restricted setting, we show how to leverage the idea of minimum optimality  certificates to design a computationally efficient interview-minimizing policy. Our policy works without knowledge of the distributions and is  dominant (and therefore also Pareto optimal and optimal-in-expectation). Background: this talk is paired with Nicole Immorlica's talk, which will
provide more basic background. My talk will cover some joint research of ours, which is described in the following paper:
http://www.cs.ubc.ca/~kevinlb/pub.php?u=2012-matching-partial-info.pdf

• Costis Daskalakis Multidimensional Optimal Mechanism Design

In his seminal paper, Myerson [1981] provides a revenue-optimal auction for a seller who is looking to sell a single item to multiple bidders.  Extending this auction to simultaneously selling multiple heterogeneous items has been one of the central problems in Mathematical Economics.  We provide such an extension that is also computationally efficient.

• Shaddin Dughmi State of the Art in Prior-free Algorithmic Mechanism Design

We review the state of the art in algorithmic mechanism design in prior-free settings. Specifically, we overview algorithmic techniques employed over the  past few years in the design of dominant strategy truthful mechanisms that run in polynomial time for problems such as combinatorial auctions,  public projects, and others.

Nisan/Ronen 1999: Algorithmic Mechanism Design

Lavi/Swamy 2005: Truthful and near-optimal Mechanism Design via Linear Programming

Dughmi, Roughgarden, Yan 2011: From Convex Optimization to Randomized Mechanisms

• Amos Fiat Strongly Truthful Mechanisms and Applications 

We define strongly truthful mechanisms and give applications thereof, resistence to externalities, and implementaiton in undominated strategies of  some multidimensional problems.

• Dimitris Fotakis Approximate Strategyproof Mechanisms for Facility Location Games 

We will review the recent work on approximate mechanism design without money for Facility Location Games. Our emphasis will be on the approximability of  k-Facility Location by deterministic strategyproof mechanisms. Among other interesting results, we will discuss a new elegant characterization  of deterministic strategyproof mechanisms with a bounded approximation ratio for 2-Facility Location on the line. In particular, we will show that  for instances with at least 5 agents, any such mechanism either admits a unique dictator, or always places the facilities at the two extremes. As a  corollary of this characterization, we will obtain that the best approximation ratio achievable by deterministic strategyproof mechanisms for  2-Facility Location on the line is precisely n-2, where n is the number of agents. Another rather surprising consequence is that the Two-Extremes  mechanism of [Procaccia and Tennenholtz, EC09] is the only deterministic anonymous strategyproof mechanism with a bounded approximation ratio for  2-Facility Location on the line. We will also show (i) that for every k >= 3, there do not exist any deterministic anonymous strategyproof mechanisms with a bounded approximation ratio for k-Facility Location on the line, even for simple instances with k+1 agents, and (ii) that there do not  exist any deterministic strategyproof mechanisms with a bounded approximation ratio for 2-Facility Location on more general metric spaces, which is true  even for simple instances with 3 agents located in a star. The talk is based on joint work with Christos Tzamos (MIT).

Procaccia and Tennenholtz. Approximate Mechanism Design Without Money. EC 2009. http://ie.technion.ac.il/~moshet/facility.pdf

P. Lu, X. Sun, Y. Wang, and Z.A. Zhu. Asymptotically Optimal Strategy-Proof Mechanisms for Two-Facility Games, EC 2010.  http://research.microsoft.com/pubs/121934/ec22-lu.pdf

D. Fotakis and C. Tzamos. Winner-Imposing Strategyproof Mechanisms for Multiple Facility Location Games. WINE 2010. http://www.softlab.ntua.gr/~fotakis/data/wine10.pdf

• Martin Hoefer Strategic Aspects of Wireless Networks

In this talk we survey our recent work on game-theoretic approaches to flexible and robust frequency allocation which represents a major challenge in  the future development of wireless networks. For coordinated environments we consider secondary spectrum auctions that implement local channel access under interference constraints. In scenarios, where a coordination device is absent, we analyze the performance of no-regret learning algorithms for power
control and channel selection. Our work extends existing models and tools in algorithmic game theory, uses non-standard graph parameters such as the  inductive independence number, and offers a variety of interesting opportunities for future research.

M. Hoefer, T. Kesselheim, B. Voecking. Appproximation Algorithms for Secondary Spectrum Auctions. SPAA 2011.

J. Dams, M. Hoefer, T. Kesselheim. Convergence Time of Power-Control Dynamics. ICALP 2011.
M. Hoefer, T. Kesselheim. Secondary Spectrum Auctions for Symmetric and Submodular Bidders.EC 2012.

• Robert Kleinberg Online Algorithms Applied to Auction Design

• Spyros Kontogiannis Recent Advances in the Computability / Approximability of Nash equilibria in Bimatrix Games

In this talk we shall explore the computability of Nash equilibria in Bimatrix Games,ie, non-cooperative normal-form games with two players whose  payoff functions are described by their payoff matrices. We shall demonstrate fundamental properties of these games, as well as various formulations  for the problem 2NASH of constructing at least one Nash equilibrium (NE) point of the game. We shall also demonstrate the most characteristic algorithms  solving 2NASH. Due to the apparent (PPAD) hardness of 2NASH, we shall then explore two distinct lines of attack: The first is the determination of broad  subclasses of games for which 2NASH is polynomial-time tractable, and the second is the provision of polynomial-time approximation algorithms for 2NASH,  for various notion of NE approximations.

• Elias Koutsoupias  Strongly truthful  mechanisms 

• Piotr Krysta Online Mechanism Design (Randomized Rounding on the Fly)

We study incentive compatible mechanisms for combinatorial auctions (CAs) in an online model with sequentially arriving bidders, where the arrivals'  order is either random or adversarial. The bidders' valuations are given by demand oracles. Previously known online mechanisms for CAs assume that each  item is available at a certain multiplicity $b > 1$. Typically, one assumes $b =\Omega(\log m)$, where $m$ is the number of different items. We present the first online mechanisms for CAs guaranteeing competitiveness without assumptions about the minimum multiplicity. We introduce an online  variant of oblivious randomized rounding enabling us to prove competitive ratios that are close to or even beat the best known offline approximation  factors for various CAs settings. Our mechanisms are universally truthful, and they significantly improve on the previously known mechanisms.
Joint work with Berthold Voecking.

• Katrina Ligett Privacy and Economics

This lecture gives an introduction to differential privacy and surveys some recent connections between privacy and economics/mechanism design/game theory.  Along the way, we consider questions such as: Is privacy-preserving mechanism design possible? Can privacy be construed as a component of individuals'  utility functions? How should harm from privacy loss be formally modeled? Attendees may optionally wish to familiarize themselves with the definition of differential privacy. One nice introduction is Cynthia Dwork's article "A Firm Foundation for Private Data Analysis" in Jan 2011 issue of the  Communications of the ACM, available here:

http://research.microsoft.com/pubs/116123/dwork_cacm.pdf

• Milena Mihail Mathematical Models for Complex Networks

Theoretical quantification as well as experimental evaluation is fundamental in establishing the predictive value of algorithms. In this sense, there is  natural overlap between algorithmic game theory and the modeling of complex networks. We present models of complex networks that are high dimensional  generalizations of Erdos Renyi random graphs and capture semantics of correlations of categorical data. We present algorithms to generate such synthetic
data in time linear in the number of output nodes and links (and additional polylogarithic factors accounting for data representation and arithmetic.)

Efficient Generation µ-close to G(n,p) and Generalizations.Antonio Blanca and Milena Mihail.
http://arxiv.org/abs/1204.5834

The Phase Transition in Inhomogeneous Random Graphs. Bela Bollobas, Svante Janson, Oliver Riordan.
http://www2.math.uu.se/~svante/papers/sj178.pdf
http://arxiv.org/abs/math/0504589
Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication. Jurij Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos.

http://eprints.pascal-network.org/archive/00001219/01/kronecker-pkdd05.pdf

• Peter Bro Miltersen Recent results on Howard's algorithm

Howard's algoritme (a.k.a. policy iteration) is a standard algorithm for solving Markov decision processes. Furthermore, generalizations of the  algorithm solve various kinds of two-player games, including parity games, concurrent reachability games and Shapley's stochastic games.  The worst case time complexity of the algorithm was until recently poorly understood, but in recent years, a surge of publications on the topic have  given us an almost complete understanding of its complexity in the various settings in which it applies. We shall give a survey of these results and
explain how they unexpectedly led to the answer to a classical open question concerning the complexity of a randomized variant of the simplex algorithm  for linear programming. We shall also present the open problems that remain. Papers of mine I will be touching  (all available from http://cs.au.dk/~bromille/Papers/):

Rasmus Ibsen-Jensen and Peter Bro Miltersen, Solving simple stochastic games with few coin toss positions,ESA'12, to appear.
Kristoffer Arnsfelt Hansen, Michal Koucký, Niels Lauritzen, Peter Bro Miltersen and Elias P. Tsigaridas
Exact algorithms for solving stochastic games. STOC'11

Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen and Peter Bro Miltersen
The complexity of solving reachability games using value and strategy iteration. CSR'11.

Thomas Dueholm Hansen, Peter Bro Miltersen and Uri Zwick Strategy Iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor. ICS'11.

• Evdokia Nikolova Stochastic Selfish Routing

This lecture focuses on how stochastic delays and risk aversion transform traditional models of routing games and the corresponding equilibrium concepts.  Moving from deterministic to stochastic delays with risk-averse players introduces nonconvexities that make the network game more difficult to analyze  even if one assumes that the variability of delays is exogenous. (For example, even computing players best responses has an unknown complexity.)  We will investigate equilibrium existence and characterization in the different settings of atomic vs. nonatomic players and exogenous vs. endogenous  factors causing the variability of edge delays. We will show that succinct representations of equilibria always exist even though the game is  non-additive, i.e., the cost along a path is not a sum of costs over edges of the path as is typically assumed in selfish routing problems.  Finally, we discuss the inefficiencies<br />resulting from the stochastic nature of delays. We prove that under exogenous stochastic delays, the price of
anarchy is exactly the same as in the corresponding game with deterministic delays. This implies that the stochastic delays and players risk  aversion do not further degrade a system in the worst-case more than the selfishness of players.
http://faculty.cse.tamu.edu/nikolova/papers/SAGT2011-Paper39.pdf
http://faculty.cse.tamu.edu/nikolova/papers/Stochastic-selfish-routing-full.pdf
http://www.sigecom.org/exchanges/volume_11/1/NIKOLOVA.pdf

• Georgios Piliouras Minimally Invasive Mechanism Design: Distributed Covering with Carefully Chosen Advice

A fundamental concern in distributed systems is aligning individual incentives with social welfare to avoid socially inefficient outcomes arising from agents acting autonomously. The role of a system designer is to provide simple mechanisms that achieve socially desirable outcomes. Centrally broadcasting  non-binding advice is one natural and widely-applicable mechanism. The main challenge in such a broadcasting mechanism is to design a provably effective
advice vector. In this paper, we address this challenge by focusing on a broad family of vertex cover and set cover games. These games are  challenging from a mechanism design standpoint because they exhibit highly inefficient equilibria and furthermore finding a solution with minimum social  cost is computationally intractable. We prove that in the case of vertex cover games, an arbitrary broadcasted advice of low social cost suffices to  lead numerous self-interested dynamics to outcomes which are almost optimal (within a constant factor) in polynomial time. These results hold even if  the advice affects only temporally a small fraction of the agents. In the case of set cover games, we provide results utilizing additional structure of  the advice vector. Specifically, we show that a carefully chosen advice can guide self-interested dynamics to outcomes which are $O(\log n)$-optimal.
http://users.ece.gatech.edu/~georgios/papers/learning_with_advice.pdf

• Maria Polukarov Optimizing payments in dominant-strategy mechanisms

Mechanism design is typically used to allocate tasks and resources to agents holding private information about their values for possible allocations.  In this context, optimizing payments within the Groves class has recently received much attention, mostly in allocation domains where agents have one-dimensional types and quasi-linear utilities. Taking an allocation function as an input, we present an algorithmic technique for finding optimal payments in a class of mechanism design problems, including utilitarian and egalitarian allocation of homogeneous items with  nondecreasing marginal costs. Our results link optimality of payment functions to a geometric condition involving triangulations of polytopes. When this condition is satisfied, we constructively show the existence of an optimal payment function that is piecewise linear in agent types. Finally, we extend this approach to multi-parameter domains and illustrate our method by applying it to the problem of allocating heterogeneous items.

V. Naroditskiy, M. Polukarov, and N.R. Jennings (2012). Optimal payments in dominant-strategy mechanisms for single-parameter domains. ACM Transactions  on Economics and Computation (In Press)

L. Dufton, V. Naroditskiy, M. Polukarov, and N.R. Jennings (2012). Optimizing payments in dominant-strategy mechanisms for multi-parameter domains.  In Twenty-Sixth Conference on Artificial Intelligence (AAAI-12), Toronto, CA, 22 - 26 Jul 2012. (In Press)

H. Moulin (2009). Almost budget-balanced vcg mechanisms to assign multiple ob- jects. Journal of Economic Theory, 144(1):96 119.

M. Guo and V. Conitzer (2009). Worst-case optimal redistribution of vcg payments in multi-unit auctions. Games and Economic Behavior, 67(1):69 98.

S. Gujar and Y. Narahari (2011). Redistribution mecha- nisms for assignment of heterogeneous objects. Journal of Artificial Intelligence Research
41:131 154.
M. Guo (2012). Worst-case optimal redistribution of VCG payments in heterogeneous-item auctions with unit demand. In Eleventh International Conference on  Autonomous Agents and Multiagent Systems (AAMAS-12), Valencia, Spain.

• Guido Schaefer Altruism and Spite in Strategic Games

Many real-world applications are complex and distributed in nature in that they involve a multitude of independent decision makers who attempt to achieve  their own goals. It is a well-known that strategic choices often lead to outcomes that are inefficient for the society as a whole. In recent years,  research in algorithmic game theory has contributed significantly to the explanation of such phenomena.  Most previous studies assume that the  decision makers make their choices based on purely selfish grounds. This is often referred to as the "self-interest hypothesis". This assumption is in
stark contrast with a large body of studies in experimental economics and social sciences, which suggest that in several situations decision makers are  motivated by other-regarding preferences such as altruism or spite. Very little attention has been given to the modeling and the analysis of the impact  of such alternative behaviors. In this lecture, we survey some recent papers that study the inefficiency of equilibria when players are  (partially) altruistic or spiteful. We discuss and compare different models of altruism and spite and highlight a few counter-intuitive results. We also  propose a general framework to analyze the inefficiency of various equilibrium concepts by adapting the smoothness framework of Roughgarden.

Chen, de Keijzer, Kempe, and Schaefer. The robust price of anarchy for atomic games with altruistic players. In Proceedings of the  7th Workshop on Internet and Network Economics, pages 383 390, 2011.

Roughgarden. Intrinsic robustness of the price of anarchy.  In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, pages 513 522, 2009.

Caragiannis, Kaklamanis, Kanellopoulos, Kyropoulou, and Papaioannou. The impact of altruism on the efficiency of atomic congestion games.  In Proceedings of the 5th Symposium on Trustworthy Global Computing, 2010.

Buehler, Goldman, Liben-Nowell, Pei, Quadri, Sharp, Taggart, Wexler, and Woods.  The price of civil society. In Proceedings of the 7th Workshop on Internet and Network Economics, pages 375 382, 2011.

Chen and Kempe. Altruism, selfishness, and spite in traffic routing. In Proc. 10th ACM Conference on Electronic Commerce, pages 140 149, 2008.

Chen and Kempe. Bayesian auctions with friends and foes. In Proceedings of the 2nd International Symposium on Algorithmic Game Theory,  pages 335 346, 2009.

• Paul Spirakis Evolutionary Processes on Undirected Graphs

We discuss a model of antagonism in undirected graphs . The model was introduced by Lieberman et. al. in Nature 433:312-316 , 2005. We study the probability of a single intruder to get the whole graph (fixation probability). We demonstrate a class of graphs with lower fixation probability than the clique (a suppressor of selection. We show an FPRAS to compute fixation probability for any given undirected graph. We give bounds for this magnitude and we also introduce a deterministic model of antagonism in graphs which is not an "all or nothing model" but it demonstrates an aggregation process. This is joint work with all the scientists which are coauthors of the corresponding papers (see below) in SODA 2012 and WINE 2011.

" Approximating fixation probabilities in the Generalized Moran Process" , J. Diaz, L.A. Goldberg, G. Mertzios, D. Richerby, M. Serna and P. Spirakis, in SODA 2012 pp. 954-960.

"Natural Models for Evolution in Networks" G. Mertzios, S. Nikoletseas, Ch. Raptopoulos and P. Spirakis, in WINE 2011

• Rob van Stee Techniques for truthful scheduling 

We give an overview of techniques used to create truthful mechanisms for scheduling on related machines. The machines are controlled by selfish agents, and only each agent knows the speed of its machine. The mechanism tries to optimize some function of the loads, where the load of a machine is the total size of the jobs assigned to it divided by its speed. This is an important special case of single-parameter problems, and it is known that it is necessary and sufficient to give a monotone allocation in order to achieve truthfulness. We discuss several recent results in this area, with an emphasis on approximation schemes.

1. Peerapong Dhangwatnotai, Shahar Dobzinski, Shaddin Dughmi, Tim Roughgarden: Truthful Approximation Schemes for Single-Parameter Agents. FOCS 2008: 15-24

2.George Christodoulou, Annamária Kovács: A Deterministic Truthful PTAS for Scheduling Related Machines. SODA 2010: 1005-1016

• Vijay Vazirani Market equilibria, PPAD, and Complementary Pivot Algorithms 

Extensive work over the last decade has led to deep insights into the computability of market equilibria. In this talk, we will show how Lemke's complementary pivot algorithm and Papadimitriou's class PPAD led recently to the resolution of some of the remaining open questions pertaining to markets with separable, piecewise-linear concave utilities and markets with production. Interestingly enough, our algorithms for these markets are practical, despite their PPAD-hardness. Based on a recent work with Jugal Garg and Ruta Mehta, and the following paper:

http://www.cc.gatech.edu/~vazirani/SPLC.pdf

http://www.cc.gatech.edu/~vazirani/SPLC.pdf

http://www.cc.gatech.edu/~vazirani/plc.pdf

• Carmine Ventre Mechanisms with verification 

Incentive-compatability in mechanism design imposes, often severe, limitations on the quality of returned solutions.
In this talk, we will be looking at how real-world information can be used in mechanism design to overcome the aforementioned barriers  and design powerful incentive-compatible mechanisms.

P. Penna and C. Ventre. Optimal-Collusion Resistant Mechanisms with Verification.  In the Proc. of the 10th ACM Conference on Electronic Commerce (ACM EC 2009). ACM, pp. 147 156, 2009.

Jerry R. Green and Jean-Jacques Laffont. Partially Verifiable Information and Mechanism Design.
The Review of Economic Studies, 53:447 456, 1986.

• Angelina Vidali Mechanism design auctions and scheduling

An introduction to truthfulness, mechanism design, the scheduling unrelated machines problem, connection to combinatorial auctions, known  techniques and future directions. homepage.univie.ac.at/angelina.vidali/thesiseng.pdf