Feeds:
Posts
Comments

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.

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.

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

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

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.

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.

SCUGC 2015: The 5th Workshop on Social Computing and User-Generated Content

https://sites.google.com/site/scugc2015/

June 16, 2015, Portland, Oregon.

in conjunction with

ACM Conference on Economics and Computation (ACM-EC 2015).

SUBMISSIONS DUE: April 25, 2015 midnight EDT.

The  workshop will bring together researchers and practitioners from a variety of relevant fields, including economics, computer science, and social psychology, in both academia and industry, that are interested in the field of social computing and user generated content. We solicit research contributions (both new and recently published). The workshop will also feature a discussion panel on prediction markets.

Social Computing and User Generated Content

Social computing systems are now ubiquitous on the web– Wikipedia is perhaps the most well-known peer production system, and there are many platforms for crowdsourcing tasks to online users, including Games with a Purpose, Amazon’s Mechanical Turk, the TopCoder competitions for software development, and many online Q&A forums such as Yahoo! Answers. Meanwhile, the user-created product reviews on Amazon generate value to other users looking to buy or choose amongst products, while Yelp’s value comes from user reviews about listed services; and a significant fraction of the content consumed online consists of user-generated, publicly viewable social media such as blogs or YouTube, as well as comments and discussion threads on these blogs and forums.

Workshop Topics

The workshop aims to bring together participants with diverse perspectives to address the important research questions surrounding social computing and user generated content: Why do users participate- what factors affect participation levels, and what factors affect the quality of participants’ contributions? How can participation be improved, both in terms of the number of participants and the quality of user contributions? What design levers can be used to design better social computing systems? Finally, what are novel ways in which social computing can be used to generate value? The answers to these questions will inform the future of social computing; both towards improving the design of existing sites, as well as contributing to the design of new social computing applications. Papers from a rich set of experimental, empirical, and theoretical perspectives are invited. The topics of interest for the workshop include, but are not limited to

o    Incentives in peer production systems

o    Experimental studies on social computing systems

o    Empirical studies on social computing systems

o    Models for user behavior

o    Crowdsourcing and Wisdom of the Crowds

o    Games with a purpose

o    Online question-and-answer systems

o    Game-theoretic approaches to social computing

o    Algorithms and mechanisms for social computing, crowdsourcing and UGC

o    Quality and spam control in user generated content

o    Rating and ranking user generated content

o    Manipulation resistant ranking schemes

o    User behavior and incentives on social media

o    Trust and privacy in social computing systems

o    Social-psychological approaches to incentives for contribution

o    Algorithms and systems for large scale decision making and consensus

o    Usability and user experience

Organizing Committee

Boi Faltings, École Polytechnique Fédérale de Lausanne (EPFL)

John Horton, New York University

Alex Slivkins, Microsoft Research NYC