Feeds:
Posts
Comments

Sperner’s Lemma hits the popular press

Here’s an article that has been trending on the New York Times site. It’s about Sperner’s Lemma–and, amazingly, they get the technical details right! The article describes a pretty practical scheme for pairing n indivisible goods with n agents; it’s motivated by the example of matching roommates with rooms, each of which has different pros and cons that the roommates each value differently. There’s a nice discussion of the idea of fair division, a pretty thorough description of a paper by Francis Su, a shout-out to Turing’s Invisible Hand Blogger Emeritus Ariel Procaccia and his web site spliddit, a quote from Stephen Brams, an online rent division calculator, and a very nice interactive graphic of how Sperner’s Lemma works.

So, what do you all think? Do you buy it? And, have you ever used a formal fair-division algorithm to make a real-life decision?

Blogger emeritus and COMSOC co-chair Ariel asked me to announce that the registration for COMSOC 2014 is open. The list of accepted papers can be found here. The invited speakers are Edward Felten, Jean-Francois Laslier, and Mark Satterthwaite.

Registration for the temporally co-located Meeting of the Society for Social Choice and Welfare (SCW) is open as well.

 

The organizers of the AdAuctions workshop have extended the submission deadline to April 27. Updated information on the workshop is as follows.

The Tenth Ad Auction Workshop  (here is the call for papers)

  • Date: June 8, 2014, 8:30-15:30
  • Submission deadline: April 27, 2014, (23:59 Hawaii time)
  • Organizing Committee: adauctionsworkshop2014@gmail.com
    Itai Ashlagi (MIT Sloan)
    Patrick Jordan (Microsoft)
    De Liu (University of Kentucky)
    Renato Paes Leme (Google)
    Chris Wilkens (Yahoo)
  • Keynote speakers: Hal Varian (Google) and Paul Milgrom (Stanford).

SAGT 2014

The 7th International Symposium on Algorithmic Game Theory (SAGT) will take place in Haifa, Israel, from September 30 to October 2, 2014.  The submission deadline is May 1st, and the Call for Papers is here.  This would be the place to send all your papers that were rejected from EC…

This year, EC will feature three workshops. All of them are inviting contributed papers. I hope you will consider submitting some of your work to one of these!

  1. The Tenth Ad Auction Workshop  (here is the call for papers)
    • Date: June 8, 2014, 8:30-15:30
    • Submission deadline: April 22, 2014, (23:59 Hawaii time)
    • Organizing Committee: adauctions2014@gmail.com
      Itai Ashlagi (MIT Sloan)
      Patrick Jordan (Microsoft)
      De Liu (University of Kentucky)
      Renato Paes Leme (Google)
      Chris Wilkens (Yahoo)
    • Keynote speakers: Hal Varian (Google) and Paul Milgrom (Stanford).
  2. The Fourth Workshop on Social Computing and User-Generated Content  (here is the call for papers)
    • Dates: June 8-9, 2014, 14:00-15:30 on June 8 and 8:30-12:30 on June 9.
    • Submission deadline: April 25, 2014
    • Organizing Committee: scugc2014@easychair.org
      Yan Chen (University of Michigan)
      Yiling Chen (Harvard University)
      Arpita Ghosh (Cornell University)
      Ashish Goel (Stanford University)
      Alex Slivkins (Microsoft Research)
  3. The Second Workshop on Crowdsourcing and Online Behavioral Experiments (here is the call for papers)
    • Date: June 8, 2014, 16:00-18:00
    • Submission deadline: April 30, 2014
    • Organizing Committee:
      Siddharth Suri (Microsoft Research NYC)
      Winter A. Mason (Facebook)
      Daniel G. Goldstein (Microsoft Research NYC & London Business School)

 

The list of accepted papers for ACM EC 2014 has been posted.

PS: Since I accepted the intimidating invitation below, I’ve been thinking of what my first post should be about. Now I have to admit I took the easy way out. Thanks for letting me participate. I’ll try to think of something more original next time.

Image

Over the last half century, our community has discovered several Chapters from The Book on the theory of algorithms and computational complexity, such as those on randomized algorithms, approximation algorithms, cryptography, and hardness of approximation. (Yes, I agree this sounds Erdosian, but when it comes to our fabulous theory, surely it is justified!)

Spectacular work, much of it done over the last decade, has revealed a new Chapter: on equilibrium computation. The following striking dichotomies, based on these insights, speak for themselves. For the readers’ convenience, all the relevant references have been hyperlinked.

 

2-Nash k-Nash, k ≥ 3
Nature of solution Rational [1] Algebraic;
irrational example [2]
Complexity PPAD-complete [3]
[4] [5]
FIXP-complete [6]
Practical algorithms Lemke-Howson [1] —?—
Decision version NP-complete [7][8] ETR-complete [9][10]

 

SPLC utilities PLC utilities
Nature of solution Rational [11][12] Algebraic [12];
irrational example [17]
Complexity PPAD-complete [11] [13] FIXP-complete [14] [15]
Practical algorithms Lemke-based [16] —?—
Decision version NP-complete [11] ETR-complete [14]

 

SPLC production PLC production
Nature of solution Rational [18] Algebraic [15];
irrational example [18]
Complexity PPAD-complete [18] FIXP-complete [15] [14]
Practical algorithms Lemke-based [18] —?—
Decision version NP-complete [18] ETR-complete [14]

 

Note: PLC = piecewise-linear concave

SLPC = separable, piecewise-linear concave

In the third table, the utilities of agents are: for all negative results we assume the most restricted utilities, i.e., linear, and for positive results we assume SPLC.

These dichotomies were first identified in [15]. This paper also extends the second and third dichotomies from SPLC to the new class of Leontief-free functions, which properly contains SPLC.