The Scientific Community Game (SCG) A Short Introduction

Karl Lieberherr

The Generic SCG

We work on the Scientific Community Game (SCG) where a group of (virtual) scientists optimize their reputations by solving problems and proposing and opposing hypotheses about niches of problems. The social welfare of the game is two-fold: (1) The winning scientist will have the best problem solving technique within the participating group of scientists and (2) knowledge/hypotheses maintenance: the hypotheses that have not been successfully opposed might be theorems. We focus on two-scientist games. Tournaments are played to involve multiple scientists.

There are two ways of winning reputation through opposition, called discounting and strengthening. Scientist Alice wins reputation from scientist Bob, if Alice successfully discounts one of Bob's hypotheses. If the discounting is not successful, the reputation flows in the other direction. In addition, scientist Alice wins reputation from Bob, if Alice can strengthen one of Bob's hypotheses without Bob successfully discounting the strengthened hypothesis. Discounting Bob' hypothesis means that a problem is given to Bob so that the solution that Bob finds, contradicts his own hypothesis. Executing the discounting protocol often requires a trusted party whith which the scientists share their secrets. Initially, all scientists start with the same reputation. The game is zero-sum with respect to reputation. In summary, a scientist must solve and provide problems and propose and oppose (discount,strengthen) hypotheses.

Application to Algorithms

The virtual scientists are programs. The hypotheses are about resource usage or approximability. The niches are defined by predicates such as all relations using relation set R.

The Highest Safe Rung Problem

You have a ladder with n rungs, and you want to find the highest rung from which you can drop a copy of the jar and not have it break. We call this the highest safe rung. You are allowed to break at most k jars. (From Kleinberg/Tardos: Algorithm Design)

A niche is defined by (n,k). Given a niche (n,k), the goal is to find query strategy, that guarantees to find the highest safe rung in q = f(n,k) steps. A hypothesis consists of (n,k) and a prediction q. Alice proposes hypothesis ((26,2), 6) and Bob tries to discount. Bob defines a ladder and shares the highest safe rung with administrator Nina. Alice now executes her query strategy: 6 no 12 no 18 yes 13 no 14 no 15 no 16 no 17 no. The highest safe rung is 17 but 8 questions were used. Bob wins reputation from Alice.

Application to Boolean Constraint Satisfaction

Maximize the fraction of satisfied constraints. Niches are defined by a relation set R: only relations in R are used to formulate the constraints.

Given R, how well can you approximate the optimal solution.

Algorithm techniques: Optimally biased coins and their derandomization, Semidefinite Programming.

R = {ONE-IN-THREE}. Optimally biased coin = 4/9. Semidefinite Programming = ?

R = {INEQUALITY arity 2} (MAXCUT). Optimally biased coin = 1/2. Semidefinite Programming = 0.83 ...

Explore Survey Propagation Algorithms: Mezard, Parisi, Montanari; Devarat Shah, David Gamarnik

The Asymmetric Generic SCG

In the Asymmetric Scientific Community Game the niche or niches are prescribed by a "chief scientist" leading to a focused game. The (virtual) scientists optimize their reputations by solving problems and proposing and opposing hypotheses about the given niches. The social welfare of the game is two-fold: (1) The winning scientist will have the best problem solving technique within the participating group of scientists and (2) knowledge/hypotheses maintenance: the hypotheses that have not been successfully opposed might be theorems.

There are two ways of winning reputation through opposition, called discounting and strengthening. Scientist Alice wins reputation from scientist Bob, if Alice successfully discounts one of Bob's hypotheses. In addition, scientist Alice wins reputation from Bob, if Alice can strengthen one of Bob's hypotheses without Bob successfully discounting the strengthened hypothesis.

Because both Alice and Bob will prepare hypotheses for the same niche, they must define their hypothesis without seeing the hypothesis of the other. This is accomplished through administrator Nina. During the discounting protocol, Nina is also needed to hide secrets and use them for verification later.