Hivemind Notes
==============

Hivemind Markets (Hanson Market Maker)
--------------------------------------

Hanson Automated Market Maker:
An event must result in exactly one of n possible mutually distinct outcomes.
Each outcome is assigned a potentially unlimited number of shares which are
valued at the event's end to be either zero or one depending on which outcome
occurred. Shares are purchased or sold from a market maker which has a fixed
formula C for its account value depending solely on the number of shares
outstanding. The cost of purchasing or selling shares is the difference of this
formula before and after the transaction. That is, the total cost to buy (or
sell if the values are negative) M={M1,M2, ...,Mn} shares when there are
currently N={N1,N2,...Nn} shares outstanding is C(N+M) - C(N).

The following constraints ensure that the market maker formula C represents
meaningful prices:
  1. Probability. The price of a share is the market's indication of the
     probability of that outcome. Each term of grad C must be between zero
     and one and collectively sum to one.
  2. Convexity. Repeatedly purchasing a set of shares is increasingly more
     expensive. That is, C(N+2M) - C(N+M) >= C(N+M) - C(N).

The first two constraints suggest the consideration of the convex conjugate
of C. The convex conjugate of a function f is f^(y) = sup_x {<x,y> - f(x)}.
The difference in the braces is the difference of the graphs of z=f(x) and the
plane z=<x,y>, with the supremum occurring when y = (grad f)(x). By sliding the
plane down to be tangent of f, we have that f^ is just the negative z-intercept
of the tangent to f. The conjugate f^ is immediately seen to be convex by
expanding linear combinations of y and f(x) in the first equation. The conjugate
of the conjugate is the highest convex function sitting below f since
  f^^(x) = sup {<y,x> - f^(y)}
         = sup {<y,x> + the z-intercept of the tangents to the graph of f}.
         = highest value at x on all tangents to the graph of f.
         = f(x) if f is convex.
Likewise the x in the relations y = (grad f)(x) and x = (grad f^)(y) are the
same x and so we have (grad f^)((grad f)(x)) = x.

Hanson's market scoring rules are simply the convex conjugates of the market
maker's account formulas C and vice versa. Consider the set of probabilities
P={p1,p2,...,pn} of the outcomes such that each p is between zero and one and
together they sum to one. Any function S(P) is called a score and moreover S
is called a proper score if it is convex.  Hanson creates a rule of scoring
by the process: For each point P there is a tangent at S(P) which intersects
the n axes. Call these intersections S1(P), S2(P), ..., Sn(P).

If the probabilities {q1,q2,...,qn} are known then the expectation
E[S(P)] = S1(P)q1 + S2(P)q2 + ... + Sn(P)qn can be compared against other
scores. Now consider the convex conjugate of S, C = S^. It follows that
(grad C)((grad S)(P)) = (grad S^)((grad S)(P)) = P, and we have what we need in
order for C to be a market maker formula.

Example (Lognormal Scoring Rule):
  S(P) = b sum_i pi log pi
  Si(P) = b log pi
  C(N) = b log sum exp(Ni/b)

Scaled Markets:
For events resulting in exactly one value x in a range [a,b], the outcome set is
approximated to be n disjoint outcomes where:
  [a,a+h], [a+h,a+2h], ... , [a+(n-1)h,a+nh] where h = (b-a)/n.
Any share to be worth an increasing function of x at the event's end is
approximated with a basket of shares in each of the lower events.

TODO : Liquidity sensitive markets.


The Hivemind Vote Process (Deciding Outcomes)
----------------------------------------------

At an interval of N number of blocks known as the tau, the Hivemind vote process
is initiated by the miners. A voting period begins when the current block height
is divisible by the tau value (nHeight % tau) == 0. A voting period ends at
N + (tau - 1).

1. Voters request ballots and submit votes:

During a voting period, the voters (votecoin holders) may query for a ballot
containing the list of recently concluded decisions. Voters are obliged to vote
on the outcome of all decisions which have recently ended. The voters will first
submit a hash of their vote (containing the selected outcome or NA), with the
contents encrypted. After the voting period has ended, voters will submit
unencrypted copies of their vote(s). The hashes of the revealed (unencrypted)
votes and previously submitted sealed (encrypted) votes must match.

2. Creation of the vote matrix M:

A vote matrix M is created with dimensions [ m x n ] where m equals the number
of voters and n equals the number of decisions. Matrix M may or may not contain
votes which have an NA response. NA responses will be filled in with values from
the preliminary outcome vector.

3. Creation of the reputation vector R:

A reputation vector R is created with a single dimension [ m ] where m is equal
to the number of voters.

4. Calculation of the preliminary outcome vector:

The preliminary outcome vector is arrived at as follows:
  1) Let mi be the j-th column in M of all votes case for the j-th decision.
  2) Remove all entries of the vectors {r,mj} corresponding to NA values.
  3) Set the weights of the shortened reputation vector r by setting
  r_j = |r_j|/Sum |r_i|.
  4) The outcome is then sum r_j m_j if the decision is binary, the weighted
  median otherwise.

5. Calculation of new Reputation values:

New voter reputation values will now be calculated in the following manner:
  Let M be the [ m x n] Filled Vote Matrix and r the Reputation Vector.
  Let A be the reputation-weighted covariance matrix of M

  A_ij =
  sum_k r_k (M_ki - wgtavg(M_.i)) (M_kj - wgtavg(M_.j)) / (1 - sum_k r_k^2)
  with singular value decomposition of A = U D V^T where:
    U m x m unitary.
    D m x n diagonal matrix with nonincreasing diagonal entries.
    V n x n unitary.

  The first column u of U will be used to adjust the voters reputation values
  as follows:
    Score = V u
    Score1 = Score + |min{Score}|, New1 = Score1^T M, reweighted
    Score2 = Score - |max{Score}|, New2 = Score2^T M, reweighted
  uadj = ( ||New1 -  r^T M|| < ||New2 - r^T M|| )? Score1: Score2;
  z be defined by z_i = uadj_i * r_i / avg{r_i}.
  rr be defined by rr_i = |z_i| / sum |z_i|.

  Finally, the reputation vector R is recalculated as follows:
  R = alpha * rr  + (1 - alpha) * R.

6. Final Outcomes:

To conclude the Hivemind voting process, the final outcomes vector will be
calculated. The final calculation is the same as the preliminary calculation in
step 4, but using the new reputation vector R and the filled matrix M.