\documentclass{llncs}

\usepackage{fullpage}

\title{ Specker Derivitive Game Requirements \& Design\\ Generic to
  CNF/CSP Versions}

\author{ Karl Lieberherr, Feng Zhou}
\institute{
  College of Computer \& Information Science\\
  Northeastern University, 360 Huntington Avenue \\
  Boston, Massachusetts 02115 USA.\\
  \email{\{lieber,fengzhou\}@ccs.neu.edu}
}

\date{\today}

\begin{document}
\maketitle
\section{Generic Requirements}

We parameterize the {\it Secker Derivitive Game} (SDG) over the
derivatives, raw materials etc. to be used. This supports better
separation of concerns at the requirements level. We can then
formulate the important game rules without knowing the details of the
derivatives.

\subsection{Parameterization}
The SDG game is parameterized by a tuple $C=(\mathit{Typ},D,R,O,F,Q)$,
where $\mathit{Typ}$ is a set\footnote{All sets discussed are finite.}
of {\it types}, $D$ ({\it derivatives}) is a set of pairs $d=(t,p)$,
where $t \in Typ$ and $0 \le p \le 1$.  $R$ ({\it raw materials}) is a
set with each element $r \in R$ having a type $\mathit{typ}(r) \in
\mathit{Typ}$. $O$ is the set of outcomes for elements in $R$; we
denote an outcome for $r$ as $o(r) \in O$.  $F$ ({\it finished products}) is
a set of pairs $(r,o(r))$, with $r \in R$ and $o(r)\in O$.  $Q$ ({\it
  quality}) is a function that maps a finished product $(r,o(r))$ to
$[0,1]$.

The game is about buying and selling derivatives.  When a derivative
$d=(t,p)$ is offered, only its type $t$ and price $p$ are known.  The
creator and buyer of a derivative need to do a {\it min-max} analysis
for the type $t$, which makes the game interesting.  By min-max
analysis we mean that it must be known what the worst-case raw
material is for a given type.  The seller must know this to price the
derivative properly and the buyer must know this to decide whether the
price is right.  The buyer of a derivative will be paid the {\it
  quality} of the finished product achieved for the raw material
produced by the seller, after the derivative was bought.

$\mathit{SDG}(C)$ is a tuple
$(P,\mathit{account},\mathit{store},\mathit{config})$, where $P$ is an
ordered set of players, $\mathit{account}$ is a function that assigns
a positive real number to each player. $\mathit{store}$ is a function
that assigns a pair $(\mathit{forSale}, \mathit{bought})$ to each
player, where $\mathit{forSale}$ is a set of derivatives for sale and
$\mathit{bought}$ is a set of tuples $(d,\mathit{seller},r,f)$, where
$d$ is a derivative, $\mathit{seller} \in P$, $r \in
R\cup\{\mathit{absent}\}$ and $f \in F\cup\{\mathit{absent}\}$.
$config$ is a tuple $(\mathit{init}, \mathit{maxTurns},
\mathit{timeslot}, \mathit{mindec})$, which configures the game.  This
configuration tuple will be later expanded with specifics for the
combinatorial structure\footnote{CNF or CSP for example.} to be used
in the game.  $init$ is a positive real number, giving the initial
amount of the account of each player in $P$.  $\mathit{maxTurns}$ is
the maximum number of turns the game will be played.
$\mathit{timeslot}$ is the amount of time given to each player.
$mindec$ is a small real number which specifies the minimum decrement
when the price of a derivative is lowered.

\subsection{Game Rules}
The $\mathit{SDG}(C)$ game has an asynchronous and a synchronous
version.  Here we define the synchronous version where players operate
sequentially; in the asynchronous version, players can buy and sell
at any time.

The rules of the synchronous $\mathit{SDG}(C)$ game are:

\begin{enumerate}
\item{\it Main Objective.}  The winner of the game is the player with
  the most money in the player's account at the end of the game.  The
  account value ranks the players. Players with the same account value
  have the same rank.
\item{\it Uniform Turns.}  Only one player is playing at a given
  time. When a player is done, the next player is the next element in
  the ordered set $P$.  A player may indicate that s/he is done in a
  variety of ways, for example by creating a file.  In other words,
  the players take turns in a uniform sequence.
\item{\it Buy or Re-offer.}  To make derivatives more attractive, on
  each turn, a player must buy at least one derivative offered for
  sale by other players or re-offer all derivatives for sale by all
  other players at a lower price.  When a derivative is bought the
  seller is paid by the buyer the price of the derivative.
\item{\it Offer new derivative.} On each turn, a player must offer a
  derivative whose type does not exist yet in the store, or whose
  price is lower than the price of all other derivatives of the same
  type in the store.
\item{\it Timely delivery.}  A player must deliver raw materials for
  derivatives bought from them in the previous round. The type of the
  raw material must match type of the derivative.
\item{\it Obligation to the finished product.}  The owner of
  a derivative is obliged to pay for a finished product based on the
  quality achieved as soon as the finished product is delivered.
\item{\it Price lowering.}  When lowering the price of a derivative,
  it must be lowered at least by $\mathit{mindec}$.
\item{\it Bought once.}  A derivative may only be bought once from the
  store.
\item{\it Positive account.}  Players must maintain a positive
  account.
\item{\it Time limit.}  Players must finish within $\mathit{timeslot}$.
\item{\it Consequences.}  Players that don't comply with the rules are
  removed from the game. If a player is removed from the game, its
  derivatives are removed from the store and its bought, but
  unfinished derivatives are refunded to the buyer.
\item{\it Completion.}  After $\mathit{maxTurns}$ rounds, nothing can
  be bought but raw materials are still delivered and finished until
  all outstanding obligations are met.
\end{enumerate}

\subsection{Archiving Concern}

We want to be able to archive games for further analysis.  We use the
following 4 archiving transactions.
\begin{enumerate}
\item
When a player $p$ offers a derivative $d$, we archive
$\mathit{create}(p,d)$.
\item
When a player $p$ buys a derivative $d$ from $\mathit{seller}$, we
archive $\mathit{buy}(\mathit{seller},p,d)$.
\item
When a player $p$ delivers raw material $r$ for derivative $d$, we
archive $\mathit{deliverR}(p,d,r)$.
\item
When a player $p$ delivers the finished product $f=(r,o(r))$ for raw
material $r$ and derivative $d$, we archive $\mathit{deliverF}(p,d,f)$.
\end{enumerate}
Given a sequence of archived transactions, we can check whether the
players followed the rules of the game.  For example, a player can
only finish raw material for a derivative that was bought previously.

\subsection{Security Concern}

It must be difficult for the players to cheat, which is a so called
{\it non-functional} requirement.  Currently, we do not implement this
requirement, to avoid an overload, but in principle we should.  It is
not a good idea to add security as an after-thought.


\section{Specialization}

\subsection{For CNF}
This specialization initiates learning about propositional calculus
and basic combinatorics. Algorithms for MAX-SAT are important to
play the game well.

For this formulation, $\mathit{Typ} = \{r1,r2\}$ where $r1$ and $r2$
are {\it clause types}.  A clause type is a pair $(l,p)$, where $p$ is
a set of positive literals with $l$ elements.  $R$ is the set of
weighted CNF-formulas of type $Typ$, where each clause has a positive
integer {\it weight}.  $O$ is the set of all assignments for a
CNF-formula.  $F$ is a pair $(r,J)$, where $J \in O$ is an assignment
for the CNF-formula $r$.  $Q(r,J)$ is the weighted fraction of
satisfied clauses in CNF-formula $r$ under assignment $J$.

To make the sets finite we add the following configuration
tuple:$$(\mathit{maxVars}, \mathit{maxClauses}, \mathit{maxWeight},
\mathit{maxClauseLength})$$

\subsection{For CSP}
This specialization initiates learning about Boolean constraint
satisfaction.  Algorithms for MAX-CSP are important to play the game
well.

For this formulation, $\mathit{Typ}$ is the set of boolean relations
of at most rank 3, of which there are 256.  $R$ is the set of
CSP$(\mathit{Typ})$-formulas.  A derivative is a set of relations in
$\mathit{Typ}$ and a price.  $O$ is a Boolean assignment $J$ for a
CSP$(\mathit{Typ})$-formula.  $F$ is a pair $(r,J)$, where $J$ is an
assignment to the variables of $r$.  $Q(r,J)$ is the weighted fraction
of satisfied constraints in $r$ under assignment $J$.

To make the sets finite we add the following configuration tuple:
$$(\mathit{maxVars}, \mathit{maxConstraints}, \mathit{maxWeight})$$

\section{Reflection on the course}

We can recognize elements of the game in real life.  You have selected
this course based on a a set of features: course description, college
requirements, reputation, etc.  Based on those features you have
selected to take my course.  The features correspond to the type of a
derivative which you buy only by knowing the type.  Now Feng and I are
delivering raw materials (subprojects) within the constraints of the
course features we agreed upon.  While we make the raw materials a bit
hard for you, we do this with the objective of challenging and
expanding your intellectual capabilities in managing software
development.  (This is different than in the game where we find hard
raw materials to avoid a high payout.)  You finish the raw materials
by finding solutions to the subprojects and you will be paid by the
quality of your finished product (your grade). Your real payout,
however, is the set of new skills you learn about managing software
development.

You can learn about managing software development by learning the
theory and by practicing the management of a software development
project. It is my belief that without having experienced a project,
you won't absorb the theory well.  That is why we experience the
project of developing algorithmic players.

\section{Design} 
The requirements don't specify how the players communicate with each
other. There are two options: a centralized versus a decentralized
design. We use a centralized design using an administrator.  The
players and the administrator communicate through XML documents.

\section{Implementation}
We use Java as implementation language and a Java data binding tool to
automatically generate parsers and printers from an XML schema.

In the implementation we practice Adaptive Programming (AP).  In AP,
as little structural information as possible is spread as narrowly as
possible.  (A good design principle in general not only for structural
information.)

{\bf Acknowledgements:} Milena Georgieva Dimitrova has given detailed
feedback on the requirements and she has written the previous version
of the requirements.

\end{document}