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.

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.

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

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.