The Scientific Community Game = The Specker Challenge Game (SCG) for Crowdsourcing Algorithms

The High-Level Game

SCG is a game to promote and study problem solving capabilities of teams. The teams may be in the same class or geographically spread around the globe as the game works through the web. The game is simulating a community of scientists; we call them virtual scientists. The community has a chief scientist that dictates the niches of various problem domains to be addressed. We assume that two virtual scientists, Alice and Bob are playing. In this document Alice and Bob are programs developed by research teams. For more scientists we organize a Swiss style or full round-robin tournament. The goal of the virtual scientists is to maximize their reputation. This egoistic behavior leads to social welfare: knowledge accumulation in the domain selected by the chief scientist. Alice and Bob make predictions about how well they can solve families of problems, called a niche. There is an interactive protocol between Alice and Bob to determine who is the better problem solver/ predictor. Often the interactive protocol has only two steps. The game is played at two levels.

Level 1: Better Problem Solver

In level one, the virtual scientists provide problems to each other in the domain selected by the chief scientist. They solve those problems, both from the other scientist and their own. Alice wins reputation if she solves Bob's problems better than Bob solves Alice' problems.

Level 2: Better Problem Solver and Predictor

In level two, the virtual scientists become more sophisticated. Bob must make predictions about hwo well he will solve problems provided by Alice and vice-versa. The prediction is in the form of a feature of the problem that is measured as a set of numbers, like the size of the problem. The prediction is a function with domain = feature and range given by (a subset of) real numbers. It serves either as an upper bound or lower bound of some property of the solution to the problem. For Alice to win reputation, Alice must be right in the following way: Her solution on Bob's problem must satisfy the prediction. If Bob is right too, i.e., his solution on Alice' problem satisfies his prediction, Alice wins reputation if her prediction is stronger than Bob's prediction.

Simulating A Scientific Community: Maximizing Reputation

SCG is similar to a real scientific community. We consider the prediction functions as hypotheses about the problem domain selected by the chief scientist and the solution method chosen by the virtual scientist. Scientists are encouraged to (1) offer hypotheses that are not easily strengthened. (2) offer hypotheses that they can successfully support. (3) stay active and publish new hypotheses or oppose current hypotheses. (4) be well-rounded: solve posed problems and pose difficult problems for others. (5) become famous!

(1) virtual scientists are encouraged to offer hypotheses that are strong. Otherwise they lose reputation. (2) virtual scientists must produce solutions to problems that are consistent with the prediction function. (3) virtual scientists must propose prediction functions and they must oppose the prediction function of their opponent. This takes two forms: They strengthen the prediction function of their opponent or they challenge it by delivering a problem where the other agent cannot satisfy the prediction function. (4) virtual scientists must solve the problems they get and they must deliver hard problems to their opponents. (5) to win the game, virtual scientists must maximize their reputation.

Simple Example

The chief scientist has determined that the domain of innovation is Sorting. Here is a sequence of sorting innovations and how they would influence SCG(Sorting):

Shell sort with different gap sequences:
(1) original by Shell: O(n^2)
(2) Hibbard: O(n^(3/2))
(3) Sedgewick: O(n^(4/3))
(4) Pratt: O(n * log^2(n))
Merge sort:
(5) John von Neumann already had an O(n*log(n)) algorithm in 1945.

Let's assume that Alice uses the basic algorithm (1) and Bob uses innovation (2). For sufficiently large n, Alice will have an advantage in two ways. Within the time bound of the game, Alice will solve more problems than Bob. Alice will make better predictions than Bob about how many comparisons are needed to accomplish the sorting. So even if Alice succeeds with sorting, she will lose at level 2 because Bob is the better predictor in that his prediction is tighter. The game limits the input sequences to have a maximum size. If this size is big enough, asymptotically faster algorithms with reasonable constants will have an advantage. A similar argument can be made for innovations (2) and (3), (3) and (4), (4) and (5). In summary, this sorting example shows how algorithmic innovations help to win in the SCG game.

Controlling Innovation

The winner of the game is the virtual scientist with the highest reputation at the end of a tournament. The winner may receive money, like a pound of gold, or a certificate on topic X or an outstanding grade. There are several knobs that influence innovation.

Defining reputation gain

Reputation is gained by being a better problem solver. Let's assume that Alice and Bob exchange 2 problems: Alice creates A1 and A2 and Bob B1 and B2. We use the following notation: qXY describes the quality achieved on X's problem by Y. Alice wins if and only if qA1B/qA1A + qA2B/qA2A < qB1A/qB1B + qB2A/qB2B. On the left-hand side there is Bob's performance on Alice' problems and on the right-hand side is Alice' performance on Bob's problems.

Reputation is also gained by being a better predictor, i.e., by making tighter predictions. We use the following notation: pqXY describes the predicted quality achieved on X's problem by Y. Based on predicted quality: Alice is right if she achieves >= what she predicted: qBA >= pqBA and qAA >= pqAA. Bob is right if he achieves >= what he predicted. qBB >= pqBB and qAB >= pqAB. Both Alice and Bob may be right. Alice wins if she is right and Bob is wrong. Alice also wins if both Alice and Bob are right and Alice predicted more than Bob. pqAA > pqAB and pqBA > pqBB.

We assume here that predicting more is challenging. In other situations, predicting less is challenging. The reputation that Alice wins is all the reputation that Bob has at this point in the game against Alice times an at-risk-factor which is a constant defined for the entire game. Assume an at-risk-factor of 20%.

Should reputation be accumulated from competition to competition? How does his influence innovation?

Information Release

The game histories should be public for all virtual scientists to learn from and to check for rule-avoiding behavior of other virtual scientists. The solution techniques should also become public after a fixed number of competitions. This fosters inventing new solution techniques.

Enforcing game rules

The game has been carefully designed so that winning is only possible with good problem solving and prediction techniques. But as soon as the SCG rules are not painstakingly followed, there are other ways of winning. Checking the game rules is essential to fostering innovation. To be on the safe side, the following security policy should be used: Even if it is possible to violate game rules, it is strictly forbidden to violate them. Virtual scientists that exploit vulnerabilities of the game checking software will be disqualified when they are caught. The game history is public: the likelihood of being caught is high even long after the game is over. It is desirable to prove formal properties of the game.

Coalitions

What happens when virtual scientists form coalitions?

Confidence

A prediction could be linked to a confidence factor which is used to compute reputation increase. What is the influence on innovation? The virtual scientists would be more likely to make predictions they are not so sure about.

Symmetric SCG

For some problem domains, it is better to use a symmetric version of the game where all virtual scientists are chief scientists, i.e., they propose hypotheses that other scientists oppose. A hypothesis consists of a niche, and a prediction function. Symmetric SCG Home Page.