A domain Domain consists of the set of all problems, called Domain.Problems and the set of all solutions, called Domain.Solutions and a predicate called Domain.valid: (Domain.Problems, Domain.Solution)-> Boolean. There is also a function Domain.quality: (Domain.Problem, Domain.Solution)->[0,1]. In summary, Domain = (Problems, Solutions, valid, quality).
A claim C(D) for domain D consists of a set of problems in D.Problems, a quality q in [0,1] and a resource bound r in [0,∞). In summary, a claim C(D) is a triple: (problems, q, r).
Informally, the claim C(D) says that the proposer can take any problem in C(D).problems and calculate a solution of at least quality C(D).q using at most C(D).r resources.
The refutation protocol: the refuter creates a problem p in C(D).problems that is conjectured to be hard to solve by the proposer. The proposer solves p and defends successfully if both quality(p,sol) > C(D).q and the resources consumed < C(D).r. Refutations are central to SCG. In the spirit of Karl Popper, every claim has a precisely defined refutation protocol that must be used to refute the claim.
The game is zero sum. All scholars start with a reputation of 100 points. The successful defender wins 10% of the reputation of the refuter. The successful refuter wins 10% of the reputation of the proposer.
To counteract the proposal of trivial claims in the scientific community, there is a second way to oppose: strengthen. Strengthening means to increase C(D).q or decrease C(D).r or both. If the proposer cannot refute the strengthened claim, the proposer will lose 10% of its reputation to the opposer.
There are a few variations of this protocol that are useful. In the early exploration phase of a domain, it makes sense to consider optimal claims: The proposer claims that the refuter cannot find a better solution than the proposer. In this case, there is no need for strengthening and the quality function takes three arguments: Domain.quality: (Domain.Problem, Domain.Solution, Domain.Solution)->[0,1]. The second solution argument is called secretSol and is the solution found by the refuter. The refutation protocol uses a refutation predicate to determine whether the refutation is successful.
The refutation protocol in this case: the refuter creates a problem p in C(D).problems that is conjectured to be hard to solve by the proposer and she finds her secret solution called secretSol. The proposer solves p and defends successfully if both quality(p,sol,secretSol) > C(D).q and the resources consumed < C(D).r.
We consider the Highest Safe Rung problem (HSR): Given a ladder with n rungs and a set of k identical jars, determine the highest safe rung from which to throw a jar without breaking it, using a minimal number of questions. HSR(n,k)=q means that we can find the highest safe rung with q questions. It is an exercise in constrained tree balancing generalizing linear search to binary search and all the shades in between.
We are looking for decision trees of minimal depth to determine the highest safe rung. To explore the domain, we have the scholars use optimal claims. In this phase, they find better ways to balance the trees than their peers. Then we ask them to make absolute claims about how well they can solve the problem, using the standard refutation protocol. For example, HSR(n,2) <= 2 * sqrt(n). Then the scholars go back to the optimal claims and they figure out a way to find the optimal solutions based on rediscovering the modified Pascal triangle where M(q,q) = 2^q. To do well in competitions, the scholars use dynamic programming to efficiently compute the entries in the modified Pascal triangle.
Domain: a problem is a pair (n,k), n a natural number, k <= n. The domain puts an upper bound on the number of rungs, e.g., n < 10000. A solution is a decision tree to determine the highest safe rung. valid((n,k), decisionTree) is a predicate which checks that the decision tree is valid: any path from root to leaf must have at most k left branches. All rungs 0..n of the ladder must appear on the leaves. If a jar breaks on rung n, it breaks on all higher rungs. If a jar does not break on rung n, it does not break on all lower rungs.
The two quality functions are: quality((n,k), decisionTree) = depth(decisionTree)/n. quality((n,k), decisionTree, secretDecisionTree) = if depth(decisionTree) <= depth(secretDecisionTree) then 1 else 0. The proposer claims she can achieve quality 1.
Claim(Domain): HSR ({(25,2)}, 9/25, 5 seconds). In this special case we have a singleton claim. 9/25 is the quality to be achieved within 5 seconds.
For an absolute claim: HSR ({(n,k)}, 2*sqrt(n)/n, 10 seconds). This claim predicts that the depth of the decision tree divided by the number of rungs is at most 2*sqrt(n)/n. The result must be delivered in 10 seconds for ladders with up to 10000 rungs.
The game has been specialized to claims of the form: HSR ({(n,2)},q,r) where at most two jars are allowed to break.
Alice starts the game by claiming: HSR({(20,2), 20, 5 seconds). She uses a linear search decision tree for solving the problem. Linear Search Decision Tree
Bob recognizes that he can strengthen Alice claim to: HSR({(20,2), 12, 5 seconds). Bob uses a better decision tree construction: Instead of stepping through the ladder in steps of one he uses steps of two. This creates decision trees of depth (n/2)+2 instead of depth n. Because this is a strengthening opposition, Alice must now try to refute the strengthened claim. According to the refutation protocol, Bob must deliver a correct decision tree of depth (n/2)+2 which indeed he does. Now Bob's reputation goes up from 100 to 110 and Alice' reputation goes down from 100 to 90. She gets punished for propoing a claim that can easily get strengthened.
Now Alice becomes more ambitious and instead of stepping through the ladder in steps of two, she uses steps of 3. This creates decision trees of depth (n/3)+3. So Alice strengthens Bobs claim to: HSR({(20,2), 10, 5 seconds).
Bob does a retrospective of the the game played so far. Can he refute Alice claim HSR({(20,2), 10, 5 seconds). He can easily construct a correct decision tree of depth 11. Bob recognizes a pattern: (20/s)+s for the depth of the decision tree. He makes a table:
s (20/s)+s 2 12 3 10 4 9 5 9 6 10
and decides to strengthen Alice claim to: HSR({(20,2), 9, 5 seconds). Alice tries to refute but Bob delivers the desired decision tree. Bob's reputation increases from 110 to 119 and Alice reputation goes down from 90 to 81. Alice is punished again for making a claim that can be strengthened.
Now Alice does a retrospective of the game so far and she asks the question: what is the largest value of n so that I can defend HSR({(n,2), 9, _). She comes up with the number 46 after some clever thinking. This seems to indicate that 9 is not the minimum. She considers HSR({(n,2), 8, _). She comes up with the number 46 after some clever thinking. With 8 questions up to 37 rungs can be managed. She finds that with 6 questions up to 22 rungs can be managed. Alice surprises Bob with the strengthened claim: HSR({(20,2), 6, 5 seconds). Bob thinks that this is impossible: he tries to refute. But Alice produces the correct decision tree and Bob loses reputation: From 119 to 119 - 11.9 and Alice reputation increases from 81 to 81 + 11.9. Bob gets punished for proposing a weak claim.
Now Bob thinks he can do better and claims: HSR({(20,2), 5, 5 seconds). Alice knows that this is impossible and she refutes. Bob loses the refutation and loses reputation: From 107.1 to 107.1 - 10.71 = 96.39. Alice gains from 93.9 to 92.9 + 10.71 = 103.61. Bob gets punished for proposing a claim that he cannot defend.
Alice has a higher reputation