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


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
  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 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


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.


positive: HSR(n,k) <= q

setOfProblems = (n,k) (singleton)
q = number of questions needed
  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
  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
  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
Bob (n0,C)) Alice(n)
refutation = n>n0 and f(n) <= C*g(n)

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
Alice (G=(V,E),secret sA = Alice' solution) Bob(sB = Bob's solution)
defense = |sB|/|sA| >= 0.9

Protocol Negation