Talk at MSRI on Learning on Networks (joint with Sly and Tamuz)

Last month at MSRI I gave a talk titled:

Interacting Probability Experts on Networks

This talk is based on this preprint with Allan Sly and Omer Tamuz. 

A nice way to think about the results of the paper is as follows:

Consider a social network of probability experts who try to predict
the outcome of the next election.
When experts meet at an MSRI workshop they each state who is the more
likely candidate to win in their view and then they update their own
private probability regarding the winner given what they've heard.

This type of model has been studied extensively in theoretical
economics. The main results proved in the economics literature concern
the question of the convergence of opinions: do all experts end up
agreeing on who is the more likely candidate to win?

 Our new results resolve major challenges in
economics by establishing conditions for convergence to the correct
answer.

Quantitative Arrow Theorem

This is a version of a talk I gave on a quantitative version of Arrow Theorem.
The paper can be found here.
See also the following post which talks about a result by G. Kalai who proved a somewhat weaker statement (requiring the functions to be balanced).

Quantitative Gibbard–Satterthwaite Theorem

This is a talk I gave in a few places- the last one is the Algorithmic Game Theory Seminar at Hebrew University on Jan 16, 2010.

The topic is a new new Quantitative proof of the Gibbard–Satterthwaite Theorem. This is based on a joint paper with Marcus Isaksson and Guy Kindler.
The talk can be found here (the previous version on google-doc is for some reason not accessible)

The paper can be found here:

See also the blog by Noam Nisan:

http://agtb.wordpress.com/2009/12/23/new-paper-average-case-manipulation-of-elections/

Finally here is the abstract from the Arxiv:

arXiv:0911.0517 (November 2009)

The Geometry of Manipulation - a Quantitative Proof of the Gibbard Satterthwaite Theorem

Marcus Isaksson, Guy Kindler and Elchanan Mossel

Received. 03 November 2009 Last updated. 08 January 2010

Abstract. We prove a quantitative version of the Gibbard-Satterthwaite theorem. We show that a uniformly chosen voter profile for a neutral social choice function $f$ of $q geq 4$ alternatives and $n$ voters will be manipulable with probability at least $10^{-7} eps^2 n^{-3} q^{-32}$, where $eps$ is the minimal statistical distance between $f$ and the family of dictator functions. Our proof is geometric. More specifically it extends the method of canonical paths to show that the measure of the profiles that lie on the interface of 3 or more outcomes is large. To the best of our knowledge our result is the first isoperimetric result to establish interface of more than two bodies.

Categories. math.CO math.PR