CSU 670 Spring 2009
Out: January 20, 2009
Due: January 27, 2009
                                                Karl Lieberherr

Subproject 3

This subproject will already result in our first robot competition
(for the simpler game: Classic SDG CSP Slowpitch Softball)
thanks to the functioning robot "babies" that the teaching staff
has prepared for you. The robots can read and write in a mutually
understandable way and they can walk through the store and find
out what is for sale. What they cannot do well yet is to recognize
good buys and to put derivatives on the market at a price
that will give them life energy.

However in class we did an experiment: to perform a requirements
analysis of the "make money with derivative d" requirement,
we played with a suitably bent coin.
We determined that the average satisfaction ratio
among all assignments generated with the suitably bent coin is
a certain number in [0,1], called break-even(d).
We use the definition: fsat(r,J) is the fraction
of satisfied constraints in raw material r and assignment J.

Our robot can exploit this result in three ways:

If the robot sees the derivative d on sale at a price p < break-even(d),
the robot should buy it in the hope that it quickly can find
for any given raw material r for d an assignment J
with fsat(r, J) >= break-even(d). The robot knows such
a good assignment must exist. The robot will look for the assignment
by flipping a suitably bent coin.

The second way to use the result is to never offer a derivative d
below the price break-even(d) because we know that 
for all raw materials r of derivative d there is an assignment J
that satisfies fsat(r,J) >= break-even(d).

The third way to use the result is to finish a given raw material
using an optimally biased coin.

PART 1:
========================================


Compute an upper bound on the price of the derivative 
d in Classic SDG CSP Slowpitch Softball
at which you would buy
the derivative. You would buy if the price is below this
upper bound because you know there exists an assignment 
that will make a profit for you.

More formally,
we define break-even(d) for a derivative d to be the largest real number
in [0,1] for which we can prove that for all raw materials r
of derivative d there
exists an assignment J satisfying fsat(r,J) >= break-even(d).


Solution:
Map d to a polynomial f[d] in b. b is the bias of a bent coin
used to assign the variables.
f[d](b) = expected fraction of satisfied constraints
  when assignments are generated randomly using a bent coin
  with bias b.
break-even(d) = f[d](b_max), where b_max is the value where
f[d](b) is maximum in [0,1].

============
Note that a more accurate name for break-even(d) would be BuyCeiling(d).

Note that BuyCeiling(d) = OfferFloor(d).
If the creator of d would go below OfferFloor(d),
then for all raw materials of derivative d
there exists an assignment that would lose money
for the creator.