Is now here:
http://www.ccs.neu.edu/home/lieber/evergreen/specker/new/scg.html

<H1>
The Scientific Community Game =
The Specker Challenge Game (SCG)
</H1>

<H2> The High-Level Game </H2>
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 scientific 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. 

The game has two levels and we assume that two virtual scientists, Alice and
Bob are playing. 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.

<H3> Level 1: Better Problem Solver </H3>
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.

<H3> Level 2: Better Problem Solver and Predictor </H3>
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 number, like the size
of the problem. The prediction is a function  with domain and range
real numbers.
It serves either as an upper bound or lower bound 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.

<H3> Simulating A Scientific Community: Maximizing Reputation </H3>
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!
<P>
(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.

<H3>Simple Example</H3>

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):
<pre>
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.
</pre>
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.
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.


<H2> Controlling Innovation </H2>

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. 

<H3> 
Defining reputation gain
</H3> 
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.

<P>
Reputation is also gained by being a better predictor.
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.

<P>
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%.

<P>
Should reputation be accumulated from competition to competition?
How does his influence innovation?
<H3>
Information Release
</H3>
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. 

<H3>
Enforcing game rules
</H3>
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.

<H3>
Coalitions
</H3>
What happens when virtual scientists form coalitions?

<H3>
Confidence
</H3>
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.

<H2>
Symmetric SCG
</H2>
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.

<a href= "
http://www.ccs.neu.edu/home/lieber/evergreen/specker/scg-home.html"> 
Symmetric SCG Home Page.</a>