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