Robert John Aumann

Hebrew University of Jerusalem

  Tuesday, July 17, 14:15

My Michel



Mourad Baiou

CNRS, Université Blaise Pascal

  Tuesday, July 17, 16:40

Stability with Michel    [pdf]


I will present the fi rst and the last results that I obtained with Michel Balinski along with some souvenirs and personal appreciations. This work was centered on two questions that Michel posed:

(1) What are the linear inequalities that completely describe the convex hull of the stable admission polytope? This had been for several years an open question. I will describe them as inequalities. They may be understood in terms of an equivalent de finition of stability.

(2) Can stable matching be generalized to "matching real numbers" such as hours agents spend together (or what we fi rst called the ordinal transportation problem then the stable allocation problem)? I will show that an extension of the Gale-Shapley "propose-dispose" algorithm is "arbitrarily bad" in the generalized problem. A new "inductive algorithm" is strongly polynomial, meaning that its complexity depends only on the number of the agents in contrast with the extension of the Gale-Shapley algorithm that depends on the "quotas" of the agents as well. Surprisingly, in the "generic" case there is a unique stable allocation (though in general the number of such solutions may be exponential).

Louis J. Billera

Cornell University

  Wednesday, July 18, 9:40

Confessions of an Erstwhile Game Theorist


While I was a graduate student at the CUNY Graduate Center preparing myself for research in game theory, Michel Balinski did his best, as my assigned "academic advisor", to prepare me for work in combinatorics and convex polytopes. He did this both through the courses he taught and by creating an atmosphere in which an endless series of visitors came in to lecture on a wide variety of topics that proved to be central to research in these areas in the decades that followed. So it is not too surprising that I eventually drifted into research in the combinatorics of convex polytopes.

Interestingly, in my subsequent work on polytopes, I was able to borrow ideas and techniques that I learned from game theorists. I will give two examples of this. The first was used to provide part of the answer to the question: How many faces can a convex polytope have? The second was used to address the question: What can one say about subdivisions of a convex polytope? (Quite a bit, it turns out.) I will say enough about the answers to these questions to indicate where these borrowed ideas came into play.

Roberto Cominetti

Universidad de Chile

  Wednesday, July 18, 14:20

Adaptive dynamics and equilibrium in congested networks


In this talk we discuss a class of discrete-time adaptive dynamics that model the behavior of individual drivers in a congested network. The system is viewed as a repeated game in which players can only observe the payoff of the pure strategy used in each stage, and use this minimal piece of information to myopically adapt their future behavior.

Despite the fact that drivers are not assumed to behave strategically by anticipating how the other players will react, the long term dynamics settle at a stationary point which turns out to be a Nash equilibrium for an underlying game. Thus, a traffic equilibrium state emerges naturally from the dynamics.

The analysis uses the ODE approach for stochastic approximation algorithms and requires to study the attractors of a system of ODE's. We will briefly discuss the structure of these equilibria, as well as their connection with the more classical concepts of Wardrop Equilibrium, Stochastic User Equilibrium, and Markovian Traffic Equilibrium.

The talk is based on joint work with Emerson Melo and Sylvain Sorin, as well as ongoing research in collaboration with Felipe Maldonado.

Pradeep Dubey

SUNY at Stony Brook

  Tuesday, July 17, 17:20

The Allocation of a Prize    [pdf]

(joint work with Siddhartha Sahi)


Consider agents who undertake costly e¤ort to produce stochastic outputs observable by a principal. The principal can award a prize deterministically to the agent with the highest output, or to all of them with probabilities that are proportional to their outputs. We show that, if there is sufficient diversity in agents’ skills relative to the noise on output, then the proportional prize will, in a precise sense, elicit more output on average, than the deterministic prize. Indeed, assuming agents know each others’skills (the complete information case), this result holds when any Nash equilibrium selection, under the proportional prize, is compared with any individually rational selection under the deterministic prize. When there is incomplete information, the result is still true but now we must restrict to Nash selections for both prizes.

We also compute the optimal scheme, from among a natural class of probabilistic schemes, for awarding the prize; namely that which elicits maximal effort from the agents for the least prize. In general the optimal scheme is a monotonic step function which lies “between”the proportional and deterministic schemes. When the competition is over small fractional increments, as happens in the presence of strong contestants whose base levels of production are high, the optimal scheme awards the prize according to the “log of the odds”, with odds based upon the proportional prize.

Edi Karni

John Hopkins University

  Wednesday, July 18, 12:05

"Reverse Bayesianism": A Choice-Based Theory of Growing Awareness    [pdf]

(joint work with Marie-Louise Viero)


This paper invokes the axiomatic approach to explore the notion of growing awareness in the context of decision making under uncertainty. It introduces a new approach to modeling the expanding universe of a decision maker in the wake of becoming aware of new consequences, new acts, and new links between acts and consequences. New consequences or new acts represent genuine expansions of the decision maker's universe, while the discovery of new links between acts and consequences renders nonnull events that were considered null before the discovery. The expanding universe, or state space, is accompanied by extension of the set of acts. The preference relations over the expanding sets of acts are linked by a new axiom, dubbed act independence, which is motivated by the idea that decision makers have unchanging preferences over the satisfaction of basic needs. The main results are representation theorems and corresponding rules for updating beliefs over expanding state spaces and null events that have the flavor of "reverse Bayesianism."

Jack Nagel

University of Pennsylvania

  Wednesday, July 18, 10:45

Strategic Evaluation in Majority Evaluation



Maurice Salles

Université de Caen

  Wednesday, July 18, 11:25

Social Choice and Cooperative Games: Voting Games as Social Aggregation Functions    [pdf]

(joint work with Mathieu Martin)


We consider voting games as procedures to aggregate individual preferences. We survey positive results on the non-emptiness of the core of voting games and explore other solutions concepts that are basic supersets of the core such as Rubinstein's stability set and two types of uncovered sets. We consider cases where the sets of alternatives are `ordinary' sets, finite sets and in finite sets with possibly a topological structure.

Martin Shubik

Yale University

  Tuesday, July 17, 14:55

On Mass Experiments in The Social Sciences


The computer and communication systems have fundamentally changed the nature of feasible social choice . In particular Political Science, Economics and Social Psychology have been opened up to experimental and social choice methods that could not have been considered empirically fifty years ago. The future will see an explosive growth of survey, choice and experimental methods on the web. The possibility of such development is illustrated with a web based experimental game. The importance of mass experimentation in political science, political economy, social psychology and game theory is discussed. This will also be illustrated in part by a game provided to the audience to be played for a monetary prize.

Sylvain Sorin

Université Pierre et Marie Curie - Paris 6

  Wednesday, July 18, 9:00

Zero-sum repeated games: asymptotic analysis and limit game


To be posted...

Peyton Young

University of Oxford

  Tuesday, July 17, 15:35

The Mathematics of Representative Government: A Tribute to Michel Balinski