#
The Use of Artificial Markets to Study Algorithmic Problems

The purpose of the artificial markets is to
learn about
algorithms and gain algorithmic insights,
either theoretically or experimentally.
A second purpose is to possibly learn lessons about real derivative markets.
The Specker Derivative Game has two variants:
SDG/classic and SDG/secret.
SDG/classic is described here:
The Specker Derivative Game (SDG)

SDG/secret was suggested by Emo Welzl at ETH Zurich
after I presented a talk on SDG in July 2008.

The SDG/secret version is about approximating a secret
solution that the seller tries to encode into the
raw material.
The predicate defines a language that must be used to
hide the secret. An interesting algorithmic question that
is behind SDG/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 SDG/secret
is much more challenging to understand than the market
created by SDG/classic. But SDG/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 derivatives can be determined
analytically.

##
SDG/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 derivative is as in SDG/classic:
a triple (pred, p, seller), where p is the price in [0,1].
The price expresses how well the secret should be
approximated by the buyer for the buyer to win.
If the price is 0.8, the buyer must come within
80% of the secret solution that the seller has.
The price lowers the quality that the buyer must achieve because
some NP-hard maximization problems are hard to approximate
and it is a challenge to come close to the maximum.
The raw material is different than in SDG/classic and is a pair (j,q), where
instance j is in mnp and where q is a value that the
seller can achieve through a secret certificate that is not revealed yet.
The finished product is a solution for j with quality q'.
If the buyer successfully finds a solution of value p*q or better,
the buyer gets paid 3*p by the seller.
If the buyer finds a lower quality solution, nothing is paid.
After the buyer has delivered his/her finished product,
the seller must reveal his/her secret solution and the
buyer can check whether it achieves the quality that the seller claimed
when the raw material was delivered.
This requires an additional step in the game protocol compared to
SDG/classic.
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.
For comparison, we summarize

##
SDG/classic

This version works in a less general context: MAX-CSP.
For comparison: let's use the same pay scheme for the secret version.
If the buyer successfully finds a solution that is above or
equal to the price p,
3*p is paid back by the seller.
Otherwise nothing is paid back.
When the seller puts a derivative d on the market at price p,
the claim is that s/he has a solution of quality p
for any raw material satisfying the predicate.
##
Example of playing SDG/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 derivative

(SDG/secret IndepSet(1 2), 0.99, Jeff).

Would you buy it?
What about
(SDG/secret IndepSet(1 2 3), 0.7, Karl)?