Posted in Uncategorized on April 25, 2014| Leave a Comment »
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.
Posted in Uncategorized on April 22, 2014| Leave a Comment »
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)
Posted in Uncategorized on April 11, 2014| Leave a Comment »
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…
Posted in Uncategorized on April 10, 2014| Leave a Comment »
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!
Posted in Uncategorized, tagged Conferences on April 8, 2014| 6 Comments »
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.
Posted in Uncategorized on April 7, 2014| Leave a Comment »
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.
Turing's Invisible Hand 