# Scientific Community Game Playground Designer Guide

This guide is written for teachers, editors, recruters, and software managers who want to use SCG and define new playgrounds. 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 or their avatars

## Domain

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

### 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).
```Problem = (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.
```Problem = (n0,C)
Solution = n
valid: n>n0
quality: irrelevant
```

### Independent Set

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

### 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.
```Problem = X
Solution = Y
valid: y in Y(x)?
quality: irrelevant

Claim(Domain)

A claim in domain D is a 4-tuple: (setOfProblems,q,r,protocol),
where setOfProblems is a subset of D.Problem, q in [0,1] is a quality
and r is a positive integer representing some resource.

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

setOfProblems = (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

setOfProblems = (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)
setOfProblems = {(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)
setOfProblems = {(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.
setOfProblems = {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

Protocol Negation

```