# 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:

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).
```
```(SDG/secret IndepSet(1 2 3), 0.7, Karl)?