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)?