Feeds:
Posts
Comments

Archive for the ‘Uncategorized’ Category

The first of a series of special issues from STOC, FOCS, and SODA has been published in Games and Economic Behavior; it contains papers invited from the 2011 conferences. The papers in the issue cover topics including mechanism design, the price of anarchy, networks, and learning in games. As the introduction to the special issue [pdf] concludes, “2011 was an outstanding year for algorithmic game theory.”

A very big thank you to guest editors Shuchi Chawla and Lisa Fleischer!

Read Full Post »

From Rakesh Vohra:

The Prize in Game Theory and Computer Science of the Game Theory Society in Honour of Ehud Kalai was established in 2008 by a donation from Yoav Shoham in recognition of Ehud Kalai’s role in promoting the connection of the two research areas.

The Prize will be awarded at the Fifth World Congress of the Society, July 24 – 28, 2016, Maastricht, The Netherlands. The Prize will be awarded to the person (or persons) who have published the best paper at the interface of game theory and computer science in the last decade. Preference will be given to candidates of age 45 or less at the time of the award, but this is not an absolute constraint. The amount of the Prize will be USD 2,500 plus travel expenses of up to USD 2,500 to attend the Congress.

The Game Theory Society invites nominations for the Prize. Each nomination should include a full copy of the paper (in pdf format) plus an extended abstract, not exceeding two pages, that explains the nature and importance of the contribution. Nominations should be emailed to the Society’s Secretary-Treasurer, Jean-Jacques Herings (at gts-sbe@maastrichtuniversity.nl) by September 30, 2015. The selection will be made by a committee appointed by the President consisting of

Preston McAfee (Microsoft)
David Parkes (Harvard)
Eva Tardos (chair, Cornell)
Bernhard von Stengel (LSE)

Read Full Post »

The summer edition of SIGecom Exchanges has a new feature: an article profiling the CS-Econ 2016 junior job market candidates (cf. the call for profiles). The goal of this article is to (a) reduce the information inefficiency of the market and (b) present the candidates as a cohesive community. For best results, use the keyword index at the end of the article. The most obvious statistic to report: There are 30 job market candidates for 2016! Many thanks are due to Vasilis Gkatzelis for his efforts in making this happen.



Wordle created from candidate provided keywords.

Read Full Post »

Posting on behalf of Michael Ostrovsky and Parag Pathak.

The National Bureau of Economic Research (NBER) Workshop on Market Design is a forum to discuss new academic research related to the design of market institutions, broadly defined. The next meeting will be held in Cambridge, Massachusetts, on October 23-24, 2015.

We welcome new and interesting research, and are happy to see papers from a variety of fields. Participants in the past meeting covered a range of topics and methodological approaches. Last year’s program can be viewed at: http://conference.nber.org/confer/2014/MDs14/program.html

The conference does not publish proceedings or issue NBER working papers – most of the presented papers are presumed to be published later in journals.

There is no requirement to be an NBER-affiliated researcher to participate. Younger researchers are especially encouraged to submit papers.

If you are interested in presenting a paper this year, please upload a PDF version by August 1, 2015.

Preference will be given to papers for which at least a preliminary draft is ready by the time of submission. Only authors of accepted papers will be contacted.

For presenters and discussants in North America, the NBER will cover the travel and hotel costs. For speakers from outside North America, while the NBER will not be able to cover the airfare, it can provide support for hotel accommodation.

There are a limited number of spaces available for graduate students to attend the conference, though we cannot cover their costs. Please email ppathak@mit.edu a short nominating paragraph.

Read Full Post »

The most salient application area for algorithmic game theory has always been that of Internet technology companies. For example, a large fraction of AGT research papers come from research labs at Microsoft, Google, Yahoo, Facebook, eBay, etc. Just as many other aspects of computing have become more data driven, so will the economics of computation. There are, however, unique challenges in treating data arising from game theoretic behavior. Algorithmic game theory has a very important role to play in addressing these challenges and in data science broadly.

The Workshop on Algorithmic Game Theory and Data Science is taking place on Monday, June 15, 2015 in Portland, Oregon in conjunction with the ACM Conference on Economics and Computation (EC’15) and FCRC. My coorganizers and I are delighted to have gotten diverse and strong submissions and we have a fantastic contributed program. The schedule and talk abstracts are on the workshop webpage. In addition to the contributed program the workshop will include:


  • 1:55-2:20: Break for presentation of Dwork et al.’s Preserving Statistical Validity in Adaptive Data Analysis at STOC’15.
  • 2:25-3:00: Five lightning talks of AGT+DS papers to appear at EC’15.
  • 4:30-5:30: Invited talk by Kevin Leyton-Brown on “Modeling Human Play in Unrepeated Games”.

We hope to see many of you there, and we hope to see much more research at the intersection of intersection of computation, economics, and data science.

Read Full Post »

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.

Read Full Post »

Battle of the Students

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).

Screen Shot 2015-05-20 at 23.22.04

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:

Screen Shot 2015-05-20 at 23.24.35

Read Full Post »

Older Posts »