The Use of Belief/Reputation Markets to Study Algorithmic Problems

The purpose of belief/reputation markets is to learn about 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 delivered problem. 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 better solution.

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

SCG/secret:

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 SCG/classic. 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? What about

(SCG/secret belief (IndepSet(1 2 3), approx. ratio 0.7), confidence 0.5)?