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

* 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

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

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.

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.

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.

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


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

On behalf of the organizers of the workshop on the subject, this is a test of the social and information network. If you think you are influential, be sure to share this with all of your colleagues. If you are submitting a paper, be sure to include with your submission that you heard about the workshop here on Turing’s Invisible Hand and who first shared it with you. (Or don’t.)

The Workshop on Social and Information Networks
(with the Conference on Economics and Computation)
June 15, 2015 in Portland, Oregon, USA.

Social and economic networks have recently attracted great interest within computer science, operations research, and economics, among other fields. How do these networks mediate important processes, such as the spread of information or the functioning of markets? This research program emerges from and complements a vast literature in sociology. Much of the recent excitement is due to the availability of social data. Massive digital records of human interactions offer a unique system-wide perspective on collective human behavior as well as opportunities for new experimental and empirical methods.

This workshop seeks to feature some of the most exciting recent research across the spectrum of this interdisciplinary area. On the computational end, we invite work on applications of machine learning, algorithms, and complex network theory to social and economic networks. On the social science end, we welcome new theoretical perspectives, empirical studies, and experiments that expand the economic understanding of network phenomena. As an organizing theme, we emphasize the flow of information in networks, but the workshop is not limited to this.

Submissions are due on April 30th, 2015; see the workshop webpage for more details on the workshop and submission process.

Ido Erev, Eyal Ert, and Ori Plonsky are organizing an interesting competition under the title:  From Anomalies to Forecasts: Choice Prediction Competition for Decisions under Risk and Ambiguity (CPC2015).  The idea is to be able to quantitatively predict the magnitude of a multiple known human “biases” and “non-rational” behaviors.  The first prize is to be invited to be a co-author of a paper about the competition written by the organizers.

Experimental studies of human choice behavior have documented clear violations of rational economic theory and triggered the development of behavioral economics. Yet, the impact of these careful studies on applied economic analyses, and policy decisions, is not large. One justification for the tendency to ignore the experimental evidence involves the assertion that the behavioral literature highlights contradicting deviations from maximization, and it is not easy to predict which deviation is likely to be more important in specific situations.

To address this problem Kahneman and Tversky (1979) proposed a model (Prospect theory) that captures the joint effect of four of the most important deviations from maximization: the certainty effect (Allais paradox, Allais, 1953), the reflection effect, overweighting of low probability extreme events, and loss aversion (see top four rows in Table 1). The current paper extends this and similar efforts (see e.g., Thaler & Johnson, 1990; Brandstätter, Gigerenzer, & Hertwig, 2006; Birnbaum, 2008; Wakker, 2010; Erev et al., 2010) by facilitating the derivation and comparison of models that capture the joint impact of the four “prospect theory effects” and ten additional phenomena (see Table 1).

These choice phenomena were replicated under one “standard” setting (Hertwig & Ortmann, 2001): choice with real stakes in a space of experimental tasks wide enough to replicate all the phenomena illustrated in Table 1. The results suggest that all 14 phenomena emerge in our setting. Yet, their magnitude tends to be smaller than their magnitude in the original demonstrations.

[[ Table 1 omitted here and appears in the source page]]

The current choice prediction competition focuses on developing models that can capture all of these phenomena but also predict behavior in other choice problems. To calibrate the models we ran an “estimation set” study that included 60, randomly selected, choice problems.

The participants in each competition will be allowed to study the results of the estimation set. Their goal will be to develop a model that will predict the results of the competition set. In order to qualify to the competition, the model will have to capture all 14 choice phenomena of Table 1. The model should be implemented in a computer program that reads the parameters of the problems as an input and predicts the proportion of choices of Option B as an output. Thus, we use the generalization criterion methodology (see Busemeyer & Wang, 2000).

The deadline for registration is April 20th.  Submission deadline is May 17th.