No abstract available.
Monday, August 24th, 2015
10:00 am–11:00 am
11:30 am–12:30 pm
Speaker: Christos Papadimitriou, UC Berkeley
I shall recount the beginnings of AGT, developments on equilibria and their complexity, as well as some problems that the field has not solved or may have missed.
The second session of this talk will take place on Tuesday, August 25 from 10:00 am to 11:00 am.
2:00 pm–3:00 pm
Scarf’s lemma is a tool for establishing the existence of allocations that are immune to coalitional deviations (usually called stable) in a variety of settings. For example, Scarf’s lemma implies the existence of bipartite stable matchings, necessary and sufficient conditions for the stable roommates problem to have solution and non-emptiness of the core in unit demand economies with indivisible goods.
Even when stable allocations may not exist, such as stable matchings with couples, Scarf’s lemma gives us a way to define `fractional’ allocations that are stable. Combining this with recent methods for rounding fractional solutions of integer programs (developed in CS), gives us methods for obtaining near feasible stable allocations in settings where stable allocations do not exist.
Interestingly, these rounding methods can be seen as sharpenings of an earlier lemma of Shapley, Folkman and Starr (which in turn was a generalization of the Caratheodory theorem). That lemma can be interpreted as a kind of central limit theorem for sets as it asserts that the Minkowski sum of a large number of sets (none of which may be convex) is approximately convex.
The second session of this talk will take place on Tuesday, August 25 from 11:30 am to 12:30 pm.
3:30 pm–4:30 pm
Speaker: Tim Roughgarden, Stanford University
Approximation guarantees for game-theoretic equilibria (a.k.a. "price of anarchy" (POA) bounds) have long been an important subject within algorithmic game theory. Over the past five years, a coherent and user-friendly theory of such bounds has emerged. The first lecture discusses games and mechanisms that are "smooth", and how this translates to approximation guarantees both for no-regret learners and in games of incomplete information. The second lecture discusses "composition theorems", which reduce bounding the POA of complex mechanisms to that of simpler mechanisms, and techniques for translating lower bounds from computational and communication complexity to POA lower bounds.
The second session of this talk will take place on Tuesday, August 25 from 2:00 pm to 3:00 pm.
Tuesday, August 25th, 2015
10:00 am–11:00 am
Speaker: Christos Papadimitriou, UC Berkeley
I shall recount the beginnings of AGT, developments on equilibria and their complexity, as well as some problems that the field has not solved or may have missed.
The first session of this talk will take place on Monday, August 24 from 11:30 am to 12:30 pm.
11:30 am–12:30 pm
Scarf’s lemma is a tool for establishing the existence of allocations that are immune to coalitional deviations (usually called stable) in a variety of settings. For example, Scarf’s lemma implies the existence of bipartite stable matchings, necessary and sufficient conditions for the stable roommates problem to have solution and non-emptiness of the core in unit demand economies with indivisible goods.
Even when stable allocations may not exist, such as stable matchings with couples, Scarf’s lemma gives us a way to define `fractional’ allocations that are stable. Combining this with recent methods for rounding fractional solutions of integer programs (developed in CS), gives us methods for obtaining near feasible stable allocations in settings where stable allocations do not exist.
Interestingly, these rounding methods can be seen as sharpenings of an earlier lemma of Shapley, Folkman and Starr (which in turn was a generalization of the Caratheodory theorem). That lemma can be interpreted as a kind of central limit theorem for sets as it asserts that the Minkowski sum of a large number of sets (none of which may be convex) is approximately convex.
The first session of this talk will take place on Monday, August 24 from 2:00 pm to 3:00 pm.
2:00 pm–3:00 pm
Speaker: Tim Roughgarden, Stanford University
Approximation guarantees for game-theoretic equilibria (a.k.a. "price of anarchy" (POA) bounds) have long been an important subject within algorithmic game theory. Over the past five years, a coherent and user-friendly theory of such bounds has emerged. The first lecture discusses games and mechanisms that are "smooth", and how this translates to approximation guarantees both for no-regret learners and in games of incomplete information. The second lecture discusses "composition theorems", which reduce bounding the POA of complex mechanisms to that of simpler mechanisms, and techniques for translating lower bounds from computational and communication complexity to POA lower bounds.
The first session of this talk will take place on Monday, August 24 from 3:30 pm to 4:30 pm.
Wednesday, August 26th, 2015
10:00 am–11:00 am
This tutorial will present a modular approach for identifying optimal and approximately optimal mechanisms for agents with multi-dimensional and non-linear preferences. The two running examples for the tutorial will be single-dimensional agents with a public budget, and multi-dimensional unit-demand agents. The modular approach identify families of optimal (or approximately optimal) single agent mechanisms and then construct from these families of mechanisms optimal (or approximately optimal) multi-agent mechanisms. Topics will include marginal revenue maximization, Border's inequality and extensions, Lagrangian virtual values, multi-dimensional virtual values, ex ante relaxations, the Bulow-Klemperer theorem and extensions, and correlation gap. See Chapters 5 and 6 of survey "Bayesian Mechanism Design" (Hartline, 2013).
The second session of this talk will take place on Thursday, August 27 from 10:00 am to 11:00 am.
11:30 am–12:30 pm
Speaker: Drew Fudenberg, Harvard University
When and why will observed play in a game approximate an equilibrium? What sort of equilibrium? To understand how and when equilibrium arises, we will look at the long-run behavior of plausible non-equilibrium dynamic processes. Lecture 1 will consider learning in static or 1-shot games, where Nash equilibrium has been found to be a good description of the outcomes of some (but not all) game theory experiment. Here subjects eventually play as if they have learned the aggregate distribution of play in the population. Lecture 2 will consider learning in extensive form games, where mistaken beliefs about opponents' play are more likely to persist (both theoretically and empirically) due to the tradeoff between exploration and exploitation.
The second session of this talk will take place on Thursday, August 27 from 11:30 am to 12:30 pm.
2:00 pm–3:00 pm
The second session of this talk will take place on Thursday, August 27 from 2:00 pm to 3:00 pm.
Computational complexity provides a fruitful perspective through which to study rational behavior and the design of economic systems. Indeed, computation is an integral part of economic activity as rational agents are ultimately computationally bounded, while economic systems are often complex and implemented on computational platforms such those enabled by the Internet. In these lectures, we will showcase important insights of complexity theory to Economics focusing on solution concepts and mechanism design.
Thursday, August 27th, 2015
10:00 am–11:00 am
Speaker: Jason Hartline, Northwestern University
This tutorial will present a modular approach for identifying optimal and approximately optimal mechanisms for agents with multi-dimensional and non-linear preferences. The two running examples for the tutorial will be single-dimensional agents with a public budget, and multi-dimensional unit-demand agents. The modular approach identify families of optimal (or approximately optimal) single agent mechanisms and then construct from these families of mechanisms optimal (or approximately optimal) multi-agent mechanisms. Topics will include marginal revenue maximization, Border's inequality and extensions, Lagrangian virtual values, multi-dimensional virtual values, ex ante relaxations, the Bulow-Klemperer theorem and extensions, and correlation gap. See Chapters 5 and 6 of survey "Bayesian Mechanism Design" (Hartline, 2013).
The first session of this talk will take place on Wednesday, August 26 from 10:00 am to 11:00 am.
11:30 am–12:30 pm
Speaker: Drew Fudenberg, Harvard University
When and why will observed play in a game approximate an equilibrium? What sort of equilibrium? To understand how and when equilibrium arises, we will look at the long-run behavior of plausible non-equilibrium dynamic processes. Lecture 1 will consider learning in static or 1-shot games, where Nash equilibrium has been found to be a good description of the outcomes of some (but not all) game theory experiment. Here subjects eventually play as if they have learned the aggregate distribution of play in the population. Lecture 2 will consider learning in extensive form games, where mistaken beliefs about opponents' play are more likely to persist (both theoretically and empirically) due to the tradeoff between exploration and exploitation.
The first session of this talk will take place on Wednesday, August 26 from 11:30 am to 12:30 pm.
2:00 pm–3:00 pm
The first session of this talk will take place on Wednesday, August 26 from 2:00 pm to 3:00 pm.
Computational complexity provides a fruitful perspective through which to study rational behavior and the design of economic systems. Indeed, computation is an integral part of economic activity as rational agents are ultimately computationally bounded, while economic systems are often complex and implemented on computational platforms such those enabled by the Internet. In these lectures, we will showcase important insights of complexity theory to Economics focusing on solution concepts and mechanism design.
