The Use of Belief/Reputation Markets to Study Algorithmic Problems
The purpose of belief/reputation markets is to
algorithms and gain algorithmic insights,
either theoretically or experimentally.
The Specker Challenge Game has two variants:
SCG/classic and SCG/secret.
SCG/classic is described here:
The Specker Challenge Game (SCG)
SCG/secret was suggested by Emo Welzl at ETH Zurich
after I presented a talk on SCG in July 2008.
The SCG/secret version is about approximating a secret
solution that the offerer tries to encode into the
The predicate defines a language that must be used to
hide the secret. An interesting algorithmic question that
is behind SCG/secret: Is the language rich enough so that
the secret can be hidden, i.e., it will be
computationally expensive to find it or an equivalent or
It is believed that the artificial market created by SCG/secret
is much more challenging to understand than the market
created by SCG/classic. But SCG/secret is a nice tool
to experience algorithmic maximization problems and learn more about them.
Based on results by Johan Hastad
(J. Hastad, Some optimal inapproximability results,
Journal of ACM, Vol. 48, 2001, pp 798--859), there is hope
that the price of some of those secret challenges can be determined
Start with any maximization problem mnp whose decision
version is in NP.
NP is the set of all problems for which there is an efficient certifier.
(See, e.g., Kleinberg/Tardos, chapter 8.)
If the decision version is in NP and we are
given a certificate for achieving
a certain value, we can efficiently check whether it achieves that value.
Predicates partition instances of mnp as in the classic version
(it is not necessarily a disjoint partition).
The predicates define the "hiding" language that must be used.
A challenge is as in SCG/classic:
a tuple (b,c), where b is a belief and c a confidence in [0,1].
The confidence c expresses how likely it is that the belief
will be supported when the challenge is accepted.
A belief b is now more complicated in SCG/secret.
A secret belief consists of a predicate pred,
an approximation ratio ar in (0,1], and a confidence in [0,1].
The approximation ratio ar expresses how well the secret
solution should be approximated by the acceptor for the acceptor to win.
If the approximation ratio is 0.8, the acceptor must come within
80% of the secret solution that the offerer has.
The approximation ratio lowers the quality that the acceptor must achieve because
some NP-hard maximization problems are hard to approximate
and it is a challenge to come close to the maximum.
The delivered problem is different than in SCG/classic and is
a pair (j,q), where
instance (or problem) j is in mnp and where q is a value that the
offerer can achieve through a secret solution that is not revealed yet.
If the acceptor successfully finds a solution of value p*q or better,
the acceptor wins and his reputation goes up.
If the acceptor finds a lower quality solution, the acceptor loses reputation.
After the acceptor has delivered his/her solution,
the offerer must reveal his/her secret solution and the
acceptor can check whether it achieves the quality that the offerer claimed
when the problem was delivered.
This requires an additional step in the game protocol compared to
Alternatively, the administrator can keep the secret and check it.
The pay function has the flavor of "lose it all" or "double it":
you lose the price you paid or you earn twice the price you paid.
Example of playing SCG/secret
We use the independent set problem. The predicates we use
to partition the instances are based on the number of edges
incident with each node. (n) means that all nodes must be
incident with n edges. (1 3) means that all nodes must be incident
with one edge or three edges.
Consider the challenge
(SCG/secret belief (IndepSet(1 2), approx. ratio 0.99), confidence 1.0).
Would you accept the belief in the above challenge?
(SCG/secret belief (IndepSet(1 2 3), approx. ratio 0.7), confidence 0.5)?