Posted in Uncategorized on May 24, 2015| Leave a Comment »
Sad news.
John Nash and his wife Alicia died in a car crash in New Jersey today. They were on their way back from Norway where Nash had received the Abel Prize. In game theory, Nash is best known for the concept of Nash equilibrium, for which he was awarded the Nobel Prize in Economics in 1994.
John Nash was 86 and Alicia Nash 82.
An obituary by Rakesh Vohra can be found on the Game Theory Society’s website.
Posted in Uncategorized on May 20, 2015| 1 Comment »
The Game Theory course that I am teaching is accompanied by weekly exercises which include a so-called G-exercise. G-exercises are games that the students play with or against each other. The (expected) payoff they receive will be accumulated and counts towards their final course grade. Starting with the Prisoner’s Dilemma, these exercises include classics like “Guess 2/3 of the Average“, Centipede, the El Farol Bar game, and an All-Pay Auction.
Last week the students were randomly matched into pairs and were asked to play a variant of the Battle of the Sexes (we slightly changed the payoffs and made the game symmetric).
The students are assigned a private chat channel with their partner and have a couple of days to discuss their strategies. By Saturday Midnight, each student has to privately submit his (possibly mixed) strategy using an online form. Players then directly receive their expected payoff.
Despite its simplicity, this G-exercise turned out to one of the most interesting ones because, over the years, students consistently reinvented solutions concepts such as Stackelberg strategies and correlated equilibrium. At the time the exercise is introduced, the students know about basic concepts such as Pareto optimality, dominated strategies, and maximin strategies. They barely know about Nash equilibrium.
Many students try to agree on one of the pure equilibria. Of course, this turns out to be difficult because of the unfair payoff distribution. Some students are successful in compensating each other (e.g., by offering beers in return for payoff 3). Others aim at evenly dividing the total payoff and agree on randomizing uniformly between A and B. This gives both players an expected payoff of 1, but obviously suffers from the fact that it’s not an equilibrium. So in some cases, players agree to play 50:50, and then one of them (or both!) eventually submit A. In the latter case, they both get no payoff. Some students succeed in computing the mixed equilibrium (3/4 A + 1/4 B), share it with their partner, and submit their strategies. This yields an expected payoff of 3/4 for both players. However, playing the maximin strategy (1/4 A + 3/4 B) guarantees exactly the same payoff no matter what the other player does. Many students seem to realize this and play the maximin strategy instead. A perhaps unexpected tactic by many players is to try to turn this into a sequential game by committing to strategy A:
Good morning,
I have already submitted strategy A (see the attached screenshot). I will be on a hiking trip over the weekend and won’t have Internet access. You can maximize your payoff by choosing B.
Have a nice weekend!
This Stackelbergian bully strategy works surprisingly well (although the screenshot cannot serve as a proof; players can revise their strategies as many times as they like until the deadline).
Finally, a handful of students reinvent the concept of correlated equilibrium. Frustrated by the fact that any real randomization will put positive probability on the undesirable (0,0) outcomes, they decide to randomize between the two pure equilibria. For example, they meet in the cafeteria and throw a coin that decides which pure equilibrium is played. This year, there was a public holiday shortly before the submission deadline, which prevented some students from meeting in person. They therefore designed elaborate mechanisms (correlation devices) to simulate the coin flip, e.g., by checking the timestamp of the first article appearing on a national news website on a given day or by adding their student ID numbers and observing whether the last digit of the sum is odd or even.
These are the little things that make teaching worthwhile.
PS: The final statistics were as follows:
Posted in Uncategorized on May 19, 2015| Leave a Comment »
[The following announcement is from Guido Schaefer, who is the General Chair for WINE 2015.]
WINE 2015: The 11th Conference on Web and Internet Economics
Centrum Wiskunde & Informatica (CWI), Amsterdam, The Netherlands
December 9-12, 2015, with tutorial program on December 9, 2015
http://event.cwi.nl/wine2015
IMPORTANT DATES
* Paper submission deadline: July 24, 2015, 11:59pm anywhere on Earth (UTC-12)
* Tutorial proposal submission deadline: July 31, 2015
* Author notification: September 18, 2015
* Camera-ready copy: October 2, 2015
SCOPE
Over the past decade, research in theoretical computer science, artificial intelligence, and microeconomics has joined forces to tackle problems involving incentives and computation. These problems are of particular importance in application areas like the Web and the Internet that involve large and diverse populations. The Conference on Web and Internet Economics (WINE) is an interdisciplinary forum for the exchange of ideas and results on incentives and computation arising from these various fields. WINE 2015 builds on the success of the Conference on Web and Internet Economics (named Workshop on Internet & Network Economics until 2013), which was held annually from 2005 to 2014.
WINE 2015 will take place at CWI in December 2015. The program will feature invited talks, tutorials, paper presentations, and a poster session. All paper submissions will be peer-reviewed and evaluated on the basis of the quality of their contribution, originality, soundness, and significance. Industrial applications and position papers presenting novel ideas, issues, challenges and directions are also welcome. Submissions are invited in, but not limited to, the following topics:
* Algorithmic game theory
* Algorithmic mechanism design
* Auction algorithms and analysis
* Computational advertising
* Computational aspects of equilibria
* Computational social choice
* Convergence and learning in games
* Coalitions, coordination and collective action
* Economic aspects of security and privacy
* Economic aspects of distributed computing
* Network games
* Price differentiation and price dynamics
* Social networks
SUBMISSION FORMAT
Authors are invited to submit extended abstracts presenting original research on any of the research fields related to WINE 2015.
An extended abstract submitted to WINE 2015 should start with the title of the paper, each author’s name, affiliation and e-mail address, followed by a one-paragraph summary of the results to be presented. This should then be followed by a technical exposition of the main ideas and techniques used to achieve these results, including motivation and a clear comparison with related work.
The extended abstract should not exceed 14 single-spaced pages using reasonable margins and at least 11-point font (excluding references). If the authors believe that more details are essential to substantiate the claims of the paper, they may include a clearly marked appendix (with no space limit) that will be read at the discretion of the Program Committee. It is strongly recommended that submissions adhere to the specified format and length. Submissions that are clearly too long may be rejected immediately.
The proceedings of the conference will be published by Springer-Verlag in the ARCoSS/LNCS series, and will be available for distribution at the conference. Accepted papers will be allocated 14 pages total in the LNCS format in the proceedings. Submissions are strongly encouraged, though not required, to follow the LNCS format. More information about the LNCS format can be found on the author instructions page of Springer-Verlag, see http://www.springer.com/computer/lncs?SGWID=0-164-6-793341-0.
IMPORTANT NOTICE
To accommodate the publishing traditions of different fields, authors of accepted papers can ask that only a one-page abstract of the paper appear in the proceedings, along with a URL pointing to the full paper. Authors should guarantee the link to be reliable for at least two years. This option is available to accommodate subsequent publication in journals that would not consider results that have been published in preliminary form in a conference proceedings. Such papers must be submitted and formatted just like papers submitted for full-text publication.
Simultaneous submission of results to another conference with published proceedings is not allowed. Results previously published or presented at another archival conference prior to WINE 2015, or published (or accepted for publication) at a journal prior to the submission deadline of WINE 2015, will not be considered. Simultaneous submission of results to a journal is allowed only if the authors intend to publish the paper as a one-page abstract in WINE 2015. Papers that are accepted and appear as a one-page abstract can be subsequently submitted for publication in a journal but may not be submitted to any other conference that has a published proceedings.
TUTORIAL PROPOSALS
WINE 2015 is soliciting proposals for tutorials to be held on December 9, 2015. Tutorial proposals should be no more than 2 pages long and contain the title of the tutorial, a description of the topic matter, the names of the tutor(s), and dates/venues where earlier versions of the tutorial were given (if any). In addition, short biographies of the tutor(s) should be attached to the proposal. Informal suggestions of tutorial ideas can also be sent without a full proposal to the program chairs at any time. Tutorial proposals should be submitted by email to wine2015@cwi.nl.
SUBMISSION LINK
Papers must be submitted electronically through https://www.easychair.org/conferences/?conf=wine2015.
Tutorial proposals should be sent to wine2015@cwi.nl.
Posted in Uncategorized on May 8, 2015| 2 Comments »
As part of the SIGecom special initiative on the job market, there will be an article in the June edition of the SIGecom Exchanges profiling 2016 junior job market candidates from the SIGecom community. These profiles will include the thesis title, research summary, brief biography, and citations to three representative papers. At least one of these papers should have appeared in the ACM Conference on Economics and Computation (EC) or a comparable venue. To be considered, submissions must be initiated by May 20 and finalized by May 27. Further instructions for submissions can be found on the submission form. The article will be coedited by Vasilis Gkatzelis, Shaddin Dughmi, and myself.
Posted in Uncategorized on May 5, 2015| 3 Comments »
Economic theory has produced a number of cute mechanisms that have been proven to satisfy various desirable properties. However, and in some cases surprisingly, most of these mechanisms have never been used in practice.
There have been some recent attempts by computer scientists to make these mechanisms accessible to a broader audience. One of them, called Spliddit, developed by former TIH blogger Ariel Procaccia, provides implementations of five fair division mechanisms. Spliddit was revamped some days ago and now also offers the first(?) real-world application of the Shapley value.
Another such attempt that I developed with Christian Geist and Guillaume Chabin called Pnyx will be demonstrated at AAMAS in Istanbul tomorrow. Pnyx is a web-based tool for preference aggregation. We were inspired by the observation that most people use inferior mechanisms (such as plurality rule) and/or unsuitable tools (such as Doodle) when aggregating preferences in everyday situations. Depending on the desired output, Pnyx computes its outcome using the Borda count, Kemeny’s rule, and Fishburn’s maximal lotteries. We tried to keep Pnyx as simple as possible. A similar recently developed tool that offers many more voting rules is Whale3.
I am sure there are other websites or apps that implement well-studied economic mechanisms. Please let us know about these in the comments.
Turing's Invisible Hand 