Requirements analysis
Making your challenges more attractive

Relation R of arity 3
5 variables
All possible constraints
Maximum bias

     R(v1 v2 v3)
     R(v1 v2    v4)
     R(v1 v2       v5)
     R(v1    v3 v4)
     R(v1    v3    v5)
     R(v1       v4 v5)
     R(   v2 v3 v4)
     R(   v2 v3    v5)
     R(   v2    v4 v5)

Specialize for R = 22.
maximize 3*p(1-p)^2
Maximum bias: p = 1/3.
Maximum satisfaction ratio = 4/9.

5/3 = 1.66...
Set two variables to true:
7/9 = 0.77... are satisfied by maximum assignment.
much larger than 4/9 = 0.44...
Can do better.
7/10 still larger than 4/9.


Generalize: n variables instead of 5.
k variables set to true:
k * binomial(n-k,2) / binomial (n,3)

k = n/3

lim [n-> oo] n/3 * binomial(2/3*n, 2)/binomial(n,3)
= 4/9

Our little agents are amazing: could they satisfy in
polynomial time 4/9+10^-6: P=NP.

In other words, our agents already play at the state-of-the-art.