Speakers |
Tel Aviv University Testing Truthfulness for Single Parameter Agents [pdf] (joint work with Yishay Mansour) Abstract
We consider the task of designing truthful mechanisms for single parameter agents. We prove a general sufficient condition for truthfulness when the valuation function of the agents of any outcome is one dimensional and continuous. For certain types of natural valuation functions, our condition is also necessary. One of the main advantages of our characterization is that it provides a computationally efficient method for testing whether a given algorithm admits a truthful payment scheme. |
New York University Toward Discrete Distributed Tatonnement Algorithms for Market Equilibria, part I
|
Carnegie Mellon University Complexity of (Iterated) Dominance and Other Solution Concepts (joint work with Tuomas Sandholm)
|
IBM T. J. Watson Research Center Capacity Planning, Quality of Service and Price Wars
|
IBM Toward Discrete Distributed Tatonnement Algorithms for Market Equilibria, part II
|
Carnegie Mellon University Finding equilibria in large sequential games of incomplete information [pdf] (joint work with Andrew Gilpin and Tuomas Sandholm) Abstract
Computing an equilibrium of an extensive form game of incomplete |
Brown University Multiagent Value Iteration in Markov Games
|
Hebrew University of Jerusalem Uncoupled Dynamics and Nash Equilibrium [pdf] (joint work with Andreu Mas-Colell) Abstract We call a dynamical system "uncoupled" if the dynamic for each player does not depend on the payoff functions of the other players. This is a natural informational restriction. We study convergence of uncoupled dynamics to Nash equilibria, and present a number of possibility and impossibility results. |
Microsoft Research TBA
|
Stanford University A Contract-Based Model for Directed Network Formation (joint work with Shie Mannor (McGill) and John N. Tsitsiklis (MIT)) Abstract
We consider a network game where the nodes of the network wish to form a graph to route traffic between themselves. We present a model where costs are incurred for routing traffic, as well as for a lack of network connectivity. We focus on directed links and the link stability equilibrium concept, and characterize connected link stable |
University of Tsukuba The Degree of a Braess-like Paradox in a Symmetric Network Can Increase without Bound Abstract We first mention noncooperative networks and distinguish between those with non-atomic (infinitely many infinitesimal) users and those with atomic (a finite number of) users. Next, we characterize the concept of Braess-like paradoxes in noncooperative optimization exemplified by the Braess paradox, i.e., after adding means to a network (so that each user has extra freedom in decision) the state of a network is at times Pareto inferior to the state before doing so. We give a measure of the degree of a Braess-like paradox. Then, we present the analysis of a very simple symmetric network with atomic users where the Braess-like paradox is apparently counter-intuitive and where the degree of a Braess-like paradox can increase without bound. In contrast, it seems that there have been seen no networks with non-atomic users where the degree of the Braess-like paradox can increase without bound. |
Massachusetts Institute of Technology Collusion-Free Protocols
|
McGill University Calibrated Forecasts: Efficiency versus Universality
|
Massachusetts Institute of Technology Universal Mechanism Design [pdf] (joint work with Sergei Izmalkov and Matt Lepinski)
|
University of Aarhus Computing Equilibrium Refinements for Zero-sum Games (joint work with Troels Bjerre Sorensen) Abstract
The linear-programming based algorithm by Koller, Megiddo and von Stengel for computing minimax strategies for extensive-form zero-sum games has been used by the AI community for computing prescriptive strategies for games with hidden information such as poker. We observe that the computation of equilibrium refinements is strongly motivated by such applications. We show that computing sequential equilibria for two-player zero-sum extensive-form games with perfect recall can be done in polynomial time. We discuss whether extensive-form perfect and normal-form proper equilibria for such games can also be found in polynomial time. |
Massachusetts Institute of Technology Sink Equilibria and Convergence
|
Technion Over Two Decades of Research on Networking Games Abstract
The application of game theoretic models and tools in the area of networking has been gaining increasing attention in recent years. From what was a rather "esoteric" area of research not many years ago, it has grown to be well within the mainstream of the networking research agenda. |
Carnegie Mellon University Approximating Revenue-Maximizing Combinatorial Auctions [pdf] (joint work with Anton Likhodedov and Tuomas Sandholm) Abstract
Designing revenue-maximizing combinatorial auctions (CAs) |
London School of Economics Hard-to-solve Bimatrix Games
|
Massachusetts Institute of Technology TBA
|
Technion Topological Conditions for Uniqueness of the Nash Equilibrium in Competitive Routing
|
Cornell University Price of Anarchy for a Network Pricing Game for Selfish Traffic [pdf] (joint work with Ara Hayrapetyan and Tom Wexler) Abstract The success of the Internet is remarkable in light of the decentralized manner in which it is designed and operated. Unlike small scale networks, the Internet is built and controlled by a large number of disperate service providers who are not interested in any global optimization. Instead, providers simply seek to maximize their own profit by charging users for access to their service. Users themselves also behave selfishly, optimizing over price and quality of service. Game theory provides a natural framework for the study of such a situation. However, recent work in this area tends to focus on either the service providers or the network users, but not both. This paper introduces a new model for exploring the interaction of these two elements, in which network managers compete for users via prices and the quality of service provided. We study the extent to which competition between service providers hurts the overall social utility of the system. |
Massachusetts Institute of Technology TBA
|
London School of Economics Geometric Views of Linear Complementarity Algorithms and Their Complexity
|
IBM Research TBA
|
Stanford University On Exchange Market Equilibria with Leontief's Utilities: Hardness Results and Hopeful Algorithms
|