# Scientific Community Game Playground Designer Guide

version 0.1

This guide is written for teachers, editors, recruters, and software managers who want to use SCG and define new playgrounds and to call for games taking place in those playgrounds. The playground is to be used by students, researchers, potential employees and software developers or their avatars. The intent is to educate, innovate (through crowd sourcing of small intelligent crowds), or evaluate. SCG is parameterized by a domain D and a set of claims based on D. The playground designs described are submitted to an SCG arena to define a new game to take place in the arena. Students either register themselves or their avatars for the next tournament to determine who has the best skills.

## Domain

A domain is a 4-tuple: (Instance, Solution, valid, quality) where Instance and Solution are sets. valid is a relation between Instance and Solution and quality is a function that assigns an element of Instance and Solution a number in [0,1].

### Computational Problems and Instances

A computational problem can be viewed as an infinite collection of instances together with a solution for every instance. The input string for a computational problem is referred to as a problem instance (which we abbreviate to instance), and should not be confused with the problem itself. A problem refers to the abstract question to be solved. In contrast, an instance of this problem is a rather concrete utterance, which can serve as the input for a decision problem. For example, consider the problem of primality testing. The instance is a number and the solution is "yes" if the number is prime and "no" otherwise. Alternately, the instance is a particular input to the problem, and the solution is the output corresponding to the given input.

### Example HSR

Playing in this playground enhances the following skills: Constructing decision trees, applying linear and binary search, generalizing information-theoretic lower-bound arguments, memoization, dynamic programming, storage minimization in dynamic programming, perspective change. Important concepts that are used: recurrence relation, binomial coefficients, Pascal's triangle (modified), induction, function optimization, calculus (asymptotic analysis).
```Instance = (n,k)
Solution = binary decision tree
valid:
has n+1 leaves labeled 0, 1, ... n.
...
quality: depth of decision tree / n
```

### Example Landau (O notation)

Learning asymptotic analysis.
```Instance = (n0,C)
Solution = n
valid: n>n0
quality: irrelevant
```

### Independent Set

Algorithms for independent set problem.
```Instance = indirected graph G = (V,E)
Solution = subset S of V
valid: S is independent set
quality: |S|/|V|
```

### Domain for mathematical Claim: ForAll Exists

ForAll x in X Exists y in Y(x): predicate(x,y). It is known for a long time http://www.ccs.neu.edu/home/lieber/courses/algorithms/cs4800/f10/resources/quantifiers.pdf how quantifiers connect with games. The refutation protocol is determined directly by the quantifiers.
```Instance = X
Solution = Y
valid: y in Y(x)?
quality: irrelevant
```

## Claim(Domain)

A claim in domain D is a 4-tuple: (setOfInstances,q,r,protocol), where setOfInstances is a subset of D.Instance, q in [0,1] is a quality and r is a positive integer representing some resource. The intuition behind using setOfInstances is to make claims about a subset of the instances of a computational problem. It is often the case that in some application domains the instances have a special form, they are in a niche, and this niche can sometimes be exploited algorithmically.

It is important that claims don't have to mathematical. Mathematical claims are expressed in predicate logic and potentially we can prove them to be either true or false. Because we need a more powerful notion of claim to make SCG interesting we define a claim using a general protocol to determine whether a refutation is successful, in the sense of Karl Popper.

A protocol consists of a data gathering algorithm involving Alice and Bob and a predicate that determines the outcome of the refutation protocol. The data gathering algorithm is of the form (Alice (data) Bob(data))+ or (Bob(data) Alice(data))+. The predicate gets all the data for evaluation. We distinguish between defense and refutation predicates. Alice always makes the claim and Bob tries to refute.

### HSR

#### positive: HSR(n,k) <= q

```setOfInstances = (n,k) (singleton)
q = number of questions needed
protocol:
Bob((n,k)) Alice(decision tree DT for n,k)
defense = valid((n,k),DT) and depth(DT) <= q/n
```

#### negative: HSR(n,k) > q

```setOfInstances = (n,k) (singleton)
q = number of questions needed
r = irrelevant
protocol:
Alice((n,k)) Bob(decision tree DT for n,k)
refutation = valid((n,k),DT) and depth(DT)<= q/n
```

### Landau (O notation)

#### positive: f(n) in O(g(n))

Math: Exists n0,C ForAll n>n0: f(n)<=C*g(n)
```setOfInstances = {(n0,C)}
q = irrelevant
protocol:
Alice(n0,C)) Bob(n)
defense = n>n0 and f(n) <= C*g(n)
```

#### negative: f(n) !in O(g(n))

Math: ForAll n0,C Exists n>n0: f(n) > C*g(n)
```setOfInstances = {(n0,C)}
q = irrelevant
protocol:
Bob (n0,C)) Alice(n)
refutation = n>n0 and f(n) <= C*g(n)

Exercises:
HSR(n,2) in O(n)
HSR(n,2) not in O(log(n))
HSR(n,2) in O(n^(1/2))
n^(1/2) not in O(log(n))
```

### Independent Set

#### positive: Bob can efficiently approximate Alice' solution within 0.9.

Approximate secret solution.
```setOfInstances = {G=(V,E)}
q = 0.9 of secret solution
r = running-time <= |E|^2
protocol:
Alice (G=(V,E),secret sA = Alice' solution) Bob(sB = Bob's solution)
defense = |sB|/|sA| >= 0.9
```

### Mathematical Claim: ForAll Exists

#### positive

ForAll x in X Exists y in Y(x): predicate(x,y).
```setOfInstances = X
q = irrelevant
r = time
protocol:
Bob(x) Alice(y)
defense = predicate(x,y)
```

#### negative

Exists x in X ForAll y in Y: !predicate(x,y).
```setOfInstances = X
q = irrelevant
r = time
protocol:
Alice(x) Bob(y)
refutation = predicate(x,y)
```
Both HSR and Landau are mathematical claims.

## Protocol Negation and Complement of a Claim

The above examples illustrate how to negate claims in general, even non-mathematical claims. In many applications we want to have positive and negative claims to solve the instance from both directions, e.g., finding lower bounds and upper bounds.

Alice' claim C1-pos(setOfInstances, q, r) means that if Bob gives her an instance p in setOfInstances she will find a solution of quality q using resources r.

The complement of this claim is: C1-neg(setOfInstances,q,r) means that Alice can find an instance p in setOfInstances so that Bob cannot find a solution y of quality q within resource bound r. Note that such a solution y might exist but the calim says that it is "hard" to find.

```protocol C1-pos:
Bob(x) Alice(y)
defense = predicate(x,y)
```
is translated into
```protocol C1-neg:
Alice(x) Bob(y)
refutation = predicate(x,y)
```
The simple rule for claim negation is: the domain stays the same and, in the protocol, the roles of Alice and Bob are reversed and a defense is changed into a refutation.

## Special case: Mathematical claims and accidental defenses and refutations

We say that Alice is perfect, if she is perfect at playing the game. She optimizes her chances to win. We use the notion of a perfect scholar to make statements about true and false claims.

Alice claims C, Bob tries to refute. Claim is of the form: Exists x in X ForAll y in Y(x): p(x,y). Refutation protocol: Alice provides x, Bob provides y.

If C true and Bob refutes, then Alice is careless. We call this accidental refutation.

If Alice defends C, and Bob is perfect then C is true.

If Bob refutes C, and Alice is perfect then C is false. Bob found a counterexample.

If C is false and Alice defends, then Bob is careless. We call this an accidental defense.

Alice claims C, Bob tries to refute. Claim is of the form: ForAll x in X Exists y in Y(x): q(x,y). Refutation protocol: Bob provides x, Alice provides y. The analysis is similar to the one above.

"If Bob perfect, we have a proof that C is true." can be replaced by: "the stronger Bob is, the more likely it is that the claim is true." A similar statement applies to Alice.

### Baby Steps Towards Proofs

A successful defense is a baby step towards a proof of the defended claim. A successful refutation is a baby step towards a proof of the negation of the refuted claim.

For EA claims: a successful defense might be a big step towards a proof. For AE claims: a successful refutation might be a big step towards a proof of the negation.

Consider the following scenario: You and your partner play with claims C and !C. C always gets defended while !C always gets refuted. This is an indication that you should try to prove C. Example: n^(1/2) in O(n/log(n)).

## Careless Scholars

The playground designer has to decide how to deal with careless scholars. Careless scholars cloud the picture of what is true and what is false and therefore we want to discourage careless scholars in the virtual world of SCG.

How can carelessness happen in HSR?

### Avoidable Accidental Defenses

There are two kinds of avoidable accidental defenses. Both are related to erroneous evaluation of the valid predicate or quality function.

#### Avoidable Accidental Defense of False Claim

Alice claims HSR(9,2)<=3. Bob tries to refute but is careless: Alice gives him the decision tree but he fails to check it carefully for validity or he miscalculates the depth to be 3. Therefore Alice defends her claim and this is an example of an avoidable accidental defense because HSR(9,2)<=3 is a wrong statement.

#### Avoidable Accidental Defense of True Claim

For an accidental defense of a true statement, consider the claim HSR(11,2)<=4 which is true. Alice provides her decision tree but she miscalculates the depth to be 4 when it is actually 5. Bob does not notice and Alice defends successfully.

In the SCG/Board, the TA or the SCG/Board tool deducts points for carelessness and in SCG/Avatar, it is the administrator that makes the deduction.

### Skill-related Accidental Defense and Refutation

#### Defense of False Claim

Alice makes the false claim that in any 2-CNF she can satisfy 0.9 of the clauses. Bob refutes and gives Alice a cnf in which she satisfies 0.95 of the clauses. Alice defends her wrong claim. She could defend because Bob was not skillful in giving Alice a harder cnf. It might also be hard to find such cnfs. Bob should not refute if he does not have a hard cnf? Maybe his solver could not do better.

#### Refutation of True Claim

Alice makes the true claim that in any 2-CNF she can satisfy 0.7 of the clauses. Bob refutes and gives Alice a cnf in which she satisfies only 0.6 of the clauses. So the true claim is refuted. The reason is that Alice was not skillful to find the assignment with the quality she predicted.