Parent Directory
| 
Revision Log
Initial import
\chapter{A promise analysis example}
We present a simplified example of a pervasive computing scenario
using promises to model the interaction policies between the agents\cite{siri3}.
We examine how the autonomic nodes stabilize into a robust functional
system in spite of their autonomous decision making. We use promises
both as a means of modelling a potential specification and as a
complementary eye glass for interpreting and understanding emergent
behaviour. The analysis of promises reveals `faults' in the policies,
which prevent the collaborative functioning of the system as a
whole. Successful interactions are the result of a bargaining
process. The method of eigenvector centrality is used to locate the
most important and vulnerable agents to the functioning of the system.
\section{Pervasive promises}
Pervasive or ubiquitous computing considers the technologies and
problems associated with having a high density of computing devices,
owned by potentially many different users with different goals and
interests\cite{mobile_security,kagal1,pervmod,marshall1885}. Managing
the complexity of an uncertain environment is a challenge and there is
a lack of modelling techniques to address these
uncertainties\cite{burgessdsom2005,badonnel1}.
Promise theory is a theory of autonomous components joined together in
a logical network\cite{burgessdsom2005,siri1}. It assumes a service
view of interactions, in which each component node offers to play a
part in a collaboration, by promising to constrain its behaviour
according to a standardized set of issues. Since it deals with both
autonomy and constraint, promise theory is of particular interest in
connection with pervasive computing management\cite{perv1,perv2}.
Promise theory builds distributed systems from autonomous components;
in doing so, it forces one to confront the uncertainty that is
inherent in distributed management, and is especially suited to the ad
hoc network scenario. The concept of \emph{voluntary cooperation} is
central, since by their very nature autonomous agents are not externally
controllable: they must be induced to cooperate by incentive alone.
Promise theory also provides a natural organizing principle by which
to view the resulting logical network, as a typed theory of graphs. We
consider the approach to be of great utility for understanding
modern, distributed peer systems in potentially ad hoc networks.
In previous work\cite{burgessdsom2005,siri1,siri2}, we have laid out the rationale
behind promise theory from a theoretical viewpoint. In this paper, we
seek a test model of sufficient size that we can see the usefulness of
the promise approach, but which is also of sufficient limitation to be
accessible to a reader without undue difficulty.
We wish to show here how promise theory identifies the
natural structure in a network without any prejudice of
centralization, based only on a discovery of the autonomous promises
made. If centralization of management is natural, this fact should
emerge from a modelling framework without being assumed at the start.
We begin by describing a constructed scenario (a shopping mall that is
`complicated enough', but not too complicated), from the viewpoint of a
privileged observer with prior knowledge: seeing the mall only as a
collection of promises between the various agents. But, what if we did
not have such in inside view of the roles of the agents, and could
only collect the list of promises made by some means of
discovery. Would that be sufficient to understand the policies and
hence the behaviours in the distributed system?
To investigate this, we then proceed to imagine that we know only the promises
themselves and attempt to derive and understand this snapshot of
the mall purely from a discovery of the promises. Although it is not
clear that anyone in the mall would have such an overview, this gives
us a mode of simulation for understanding the relationships between
autonomous individuals.
\section{A Smart Mall}
We consider the future shopping mall as our test scenario. A public
meeting place, like a shopping mall full of peers interacting freely
by a mixture of private and public communication channels, is a
potentially difficult scenario to understand, as it is formed of an ad
hoc mixture of fixed and transient infrastructure. Although we pick a
specific scenario, our computations are not really tied to this: any
scenario in which a service-oriented interaction pattern prevails can
be analyzed using our method. However, we think that the pervasive
shopping mall is naturally more ad hoc than a ``designed'' system, and
hence we use this as a plausible example in which the analysis crosses
the boundary from management by design, to merely coping.
In the mall, a multitude of mobile devices roams in a changing
environment, with many conflicting interests. The shops and the mall
itself are part of a fixed infra-structure backbone network, while
customers, leaden with personal mobile devices move around,
interacting freely with a variety of shops and retailers over
short-distance links (e.g. BlueTooth), making and breaking connections
and allegiances. Some conversations between parties (either verbal or
electronic) are authoritative, while others are informal: there is
thus a divergence of trust between the individual players.
The mall consists of a number of types of individual: a `mall
management', an Internet Service Provider (ISP), a number of shops,
and a number of customers. These are all network capable entities. To
offer their customers a greater level of service, the mall has an
agreement with an Internet service provider (ISP), which provides a
wireless network throughout the entire mall. This can be accessed by
any customer carrying an appropriate cellular device. Customers and
shops and communicate {\em ad hoc} by short-range private channels; external
communication must be routed via the ISP.
Inside the mall, we find different logical \emph{regions} with
different network coverage.
\begin{itemize}
\item {\em A global network.} This is a wireless network operated by
the mall. It network can be used by customers, by registering for a
username and password. Through this network the customers can obtain a
variety of services, for instance download information about bus
schedules, order bus tickets, download a map of the mall with
information on the different shops and so on, or communicate with the
outside world. To pay for their services, the customers can either use
a credit card, or earn virtual credits which can be used as payment
within the mall.
\item {\em Local networks.} Each shop has its own wireless
network for customer benefit, which is open and offers a limited number
of services. Customers can download available information about
current special offers, and regular prices on goods which they are
interested in. This local network is only available to
customers within the physical wireless range of the store.
\item {\em Ad hoc networks.} Customers have the ability to
communicate directly, using a low power network such
as BlueTooth for instance, as long as they
are within a certain range of each other. This way, customers can
send and receive messages without loading the mall network or
paying them for this service.
\end{itemize}
The networks listed above can be utilised for several benefits for each
actor in this scenario. Particularly,
we can group the network traffic in two main groups:
\begin{enumerate}
\item {\em Information.} The customers might find it useful
to be able to download information about bus schedules, maps of the
shops, product information and so on. The providers of this
information, i.e. the shops and the mall itself, this is a basic
service to the customers, and has only a goodwill value.
\item {\em Commercial messages.} Shops can have special
deals, to attract more customers, and hence increase their turnover.
For the customers, this kind of information might be a source of
annoyance, as their mobile devices is flooded with unwanted data (spam).
\end{enumerate}
\section{The promises and the autonomous agents}
The autonomous agents in this scenario are the set of individual
entities that comprise the mall environment and who have an interest
in one another's behaviour. Each of these agents is represented by a
\emph{node} in a \emph{promise graph}, and there is
a labelled, directed edge (arrow) between node $i$ and node $j$ for
each promise made by node $i$ to node $j$.
They are categorized as follows:
\bigskip
\begin{itemize}
\item The ISP (node 1)
\item The mall (node 2)
\item The shops (nodes 3,4,5)
\item The customers (nodes 6-15)
\end{itemize}
\bigskip
A promise is a labelled edge in a graph, of the form
\beq
a \stackrel{\tau,\chi}{\longrightarrow}b
\eeq
where $a,b$ are agents or nodes in the graph, and $\tau$ is a {\em
type} of promise. $\chi$ represents the constraint that node $a$
promises to uphold with regard to $b$; $b$ is informed of this, but
has no other influence over $a$. See ref. \cite{burgessdsom2005} for
an introduction.
The promise bodies $\tau,\chi$ represent behavioural constraints at
the outset, and can later be interpreted in terms of a \emph{value} or
\emph{currency} that can be exchanged between the actors. We shall not
explore the details of the promise body in this paper, in order to keep
matters simple.
We can now represent the promises between the different agents. We
label the promise types $\tau \in \{q, d, f, lf, r, i\}$.
The roles of these promises is as follows:
\bigskip
\begin{itemize}
\item $q$: This promise asserts a certain Quality of Service (QoS) in network performance,
and is used
\begin{itemize}
\item From ISP to the mall
\item From the mall to the customers
\end{itemize}
\item $d$: A promise to download messages from another agent.
Customers agree to download a certain amount of advertising from the
shops and from the mall, i return for some kind of reward. Customers can also
spread the messages to other customers in return for reward from the mall on
production of a transfer receipt.
\item $r$: A promise to reward forwarding of messages to other customers.
The mall and the individual shops promise to reward customers with points or credits for
forwarding commercial messages to other customers by ad hoc means (this could occur while
they are outside the mall, e.g. in their home neighbourhood).
\item $i$ A promise to offer relevant information from the mall and shops to the customers
in the environment.
\item $f$ This is a promise from the customers to the mall/the shops regarding
forwarding downloaded messages to other customers. It could involve the transmission of
forwarding receipts, for instance.
\item $lf$ This promise is made between the customers. It acts as a courtesy treaty
limiting the amount of messages offered for forwarding to relevant,
official messages, plus some personal advertising. Without such a
treaty, the amount of personal junk messages might overload them and
they could stop choosing the exchange messages altogether. Note, that due to the
autonomy of the nodes, no customer can force messages onto another. The exchange
must be by mutual consent\cite{burgessrpc}.
\end{itemize}
Fig. \ref{pr} shows the full set of promises made by the agents in the
mall, for completeness. Their types and the engineering dimensions used in their
constraints are summarized in table \ref{tab1}.
\begin{table}
\small
\begin{center}
\begin{tabular}{lll}\hline
Promise body & Units & Category \\
\hline\hline
$q, q\ge q_n$ & Mb/sec & Service \\
$r, r=R$ & Credits per message & Service \\
$i, i\in \{T,F\}$ & True/False & Service \\
$d, d\in \{T,F\}$ & Messages per hour & Use-message \\
$f, f\ge f_n$ & Messages per hour & Service \\
$lf, lf\le l_n$ & Messages per hour & Use-value\\
~\\
\end{tabular}
\caption{A summary of promise types.\label{tab1}}
\end{center}
\end{table}
\bigskip
\begin{figure}
\tiny
\begin{center}
\begin{tabular}{|c|c|}
\hline
Node $1$ (the ISP) &
$
% \Pi _{q, q\geq q_1}(\{n_1\}, \{n_2\} )
n_1 \stackrel{q, q\geq q_1}{\longrightarrow}n_2
$
\\\hline
Node $2$ (the Mall) &
$
\left.
\begin{array}{c}
n_2 \stackrel{q, q\geq q_2}{\longrightarrow}n_3\\
n_2 \stackrel{q, q\geq q_3}{\longrightarrow}n_4\\
n_2 \stackrel{q, q\geq q_4}{\longrightarrow}n_5
\end{array}
\right\}
$
,
$
\left.
\begin{array}{c}
n_2 \stackrel{r, r = R_1}{\longrightarrow}n_6\\
n_2 \stackrel{r, r = R_2}{\longrightarrow}n_7\\
n_2 \stackrel{r, r = R_3}{\longrightarrow}n_8\\
n_2 \stackrel{r, r = R_4}{\longrightarrow}n_9\\
n_2 \stackrel{r, r = R_5}{\longrightarrow}n_{10}\\
n_2 \stackrel{r, r = R_6}{\longrightarrow}n_{11}\\
n_2 \stackrel{r, r = R_7}{\longrightarrow}n_{12}\\
n_2 \stackrel{r, r = R_8}{\longrightarrow}n_{13}\\
n_2 \stackrel{r, r = R_9}{\longrightarrow}n_{14}\\
n_2 \stackrel{r, r = R_{10}}{\longrightarrow}n_{15}\\
\end{array}
\right\}
$
,
$
\left.
\begin{array}{c}
n_2 \stackrel{i, i \in \{T,F \}}{\longrightarrow}n_{6}\\
n_2 \stackrel{i, i \in \{T,F \}}{\longrightarrow}n_{7}\\
n_2 \stackrel{i, i \in \{T,F \}}{\longrightarrow}n_{8}\\
n_2 \stackrel{i, i \in \{T,F \}}{\longrightarrow}n_{9}\\
n_2 \stackrel{i, i \in \{T,F \}}{\longrightarrow}n_{10}\\
n_2 \stackrel{i, i \in \{T,F \}}{\longrightarrow}n_{11}\\
n_2 \stackrel{i, i \in \{T,F \}}{\longrightarrow}n_{12}\\
n_2 \stackrel{i, i \in \{T,F \}}{\longrightarrow}n_{13}\\
n_2 \stackrel{i, i \in \{T,F \}}{\longrightarrow}n_{14}\\
n_2 \stackrel{i, i \in \{T,F \}}{\longrightarrow}n_{15}\\
\end{array}
\right\}
$
\\\hline
Node $3$ (Shop1) &
$
\left.
\begin{array}{c}
n_3 \stackrel{q, q\geq q_5}{\longrightarrow}n_{6}\\
n_3 \stackrel{q, q\geq q_6}{\longrightarrow}n_{7}\\
n_3 \stackrel{q, q\geq q_7}{\longrightarrow}n_{8}\\
\end{array}
\right\}
$
,
$
\left.
\begin{array}{c}
n_3 \stackrel{r, r = R_{11}}{\longrightarrow}n_{6}\\
n_3 \stackrel{r, r = R_{12}}{\longrightarrow}n_{7}\\
n_3 \stackrel{r, r = R_{13}}{\longrightarrow}n_{8}\\
\end{array}
\right\}
$
,
$
\left.
\begin{array}{c}
n_3 \stackrel{i, i \in \{T,F \}}{\longrightarrow}n_{6}\\
n_3 \stackrel{i, i \in \{T,F \}}{\longrightarrow}n_{7}\\
n_3 \stackrel{i, i \in \{T,F \}}{\longrightarrow}n_{8}\\
\end{array}
\right\}
$
\\\hline
Node $4$ (Shop2) &
$
\left.
\begin{array}{c}
n_3 \stackrel{q, q\geq q_8}{\longrightarrow}n_{15}\\
n_3 \stackrel{r, r = R_{14}}{\longrightarrow}n_{15}\\
n_3 \stackrel{i, i \in \{T,F\}}{\longrightarrow}n_{15}\\
\end{array}
\right\}
$
\\\hline
Node $5$ (Shop3) &
$
\left.
\begin{array}{c}
n_5 \stackrel{q, q\geq q_9}{\longrightarrow}n_{9}\\
n_5 \stackrel{q, q\geq q_{10}}{\longrightarrow}n_{10}\\
n_5 \stackrel{q, q\geq q_{11}}{\longrightarrow}n_{11}\\
\end{array}
\right\}
$
,
$
\left.
\begin{array}{c}
n_5 \stackrel{r, r = R_{15}}{\longrightarrow}n_{9}\\
n_5 \stackrel{r, r = R_{16}}{\longrightarrow}n_{10}\\
n_5 \stackrel{r, r = R_{17}}{\longrightarrow}n_{11}\\
\end{array}
\right\}
$
,
$
\left.
\begin{array}{c}
n_5 \stackrel{i, i \in \{T,F \}}{\longrightarrow}n_{9}\\
n_5 \stackrel{i, i \in \{T,F \}}{\longrightarrow}n_{10}\\
n_5 \stackrel{i, i \in \{T,F \}}{\longrightarrow}n_{11}\\
\end{array}
\right\}
$
\\\hline
Node $6$ (Customer) &
$
\left.
\begin{array}{c}
n_6 \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{2}\\
n_6 \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{3}\\
n_6 \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{4}\\
n_6 \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{5}\\
\end{array}
\right\}
$
,
$
\left.
\begin{array}{c}
n_6 \stackrel{f, f\geq f_1}{\longrightarrow}n_{2}\\
n_6 \stackrel{f, f\geq f_2}{\longrightarrow}n_{3}\\
n_6 \stackrel{f, f\geq f_3}{\longrightarrow}n_{4}\\
n_6 \stackrel{f, f\geq f_4}{\longrightarrow}n_{5}\\
\end{array}
\right\}
$
,
$
\left.
\begin{array}{c}
n_6 \stackrel{lf, lf\leq l_1}{\longrightarrow}n_{7}\\
n_6 \stackrel{lf, lf\leq l_1}{\longrightarrow}n_{8}\\
\end{array}
\right\}
$
\\\hline
Node $7$ (Customer) &
$
\left.
\begin{array}{c}
n_7 \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{2}\\
n_7 \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{3}\\
n_7 \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{4}\\
n_7 \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{5}\\
\end{array}
\right\}
$
,
$
\left.
\begin{array}{c}
n_7 \stackrel{f, f\geq f_5}{\longrightarrow}n_{2}\\
n_7 \stackrel{f, f\geq f_6}{\longrightarrow}n_{3}\\
n_7 \stackrel{f, f\geq f_7}{\longrightarrow}n_{4}\\
n_7 \stackrel{f, f\geq f_8}{\longrightarrow}n_{5}\\
\end{array}
\right\}
$
,
$
\left.
\begin{array}{c}
n_7 \stackrel{lf, lf\leq l_3}{\longrightarrow}n_{6}\\
n_7 \stackrel{lf, lf\leq l_4}{\longrightarrow}n_{8}\\
\end{array}
\right\}
$
\\\hline
Node $8$ (Customer) &
$
\left.
\begin{array}{c}
n_8 \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{2}\\
n_8 \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{3}\\
n_8 \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{4}\\
n_8 \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{5}\\
\end{array}
\right\}
$
,
$
\left.
\begin{array}{c}
n_8 \stackrel{f, f\geq f_9}{\longrightarrow}n_{2}\\
n_8 \stackrel{f, f\geq f_{10}}{\longrightarrow}n_{3}\\
n_8 \stackrel{f, f\geq f_{11}}{\longrightarrow}n_{4}\\
n_8 \stackrel{f, f\geq f_{12}}{\longrightarrow}n_{5}\\
\end{array}
\right\}
$
,
$
\left.
\begin{array}{c}
wn_8 \stackrel{lf, lf\leq l_5}{\longrightarrow}n_{6}\\
n_8 \stackrel{lf, lf\leq l_6}{\longrightarrow}n_{7}\\
\end{array}
\right\}
$
\\\hline
Node $9$ (Customer)&
$
\left.
\begin{array}{c}
n_9 \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{2}\\
n_9 \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{3}\\
n_9 \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{4}\\
n_9 \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{5}\\
\end{array}
\right\}
$
,
$
\left.
\begin{array}{c}
n_9 \stackrel{f, f\geq f_{13}}{\longrightarrow}n_{2}\\
n_9 \stackrel{f, f\geq f_{14}}{\longrightarrow}n_{3}\\
n_9 \stackrel{f, f\geq f_{15}}{\longrightarrow}n_{4}\\
n_9 \stackrel{f, f\geq f_{16}}{\longrightarrow}n_{5}\\
\end{array}
\right\}
$
,
$
\left.
\begin{array}{c}
n_9 \stackrel{lf, lf\leq l_7}{\longrightarrow}n_{10}\\
n_9 \stackrel{lf, lf\leq l_8}{\longrightarrow}n_{11}\\
\end{array}
\right\}
$
\\\hline
Node $10$ (Customer)&
$
\left.
\begin{array}{c}
n_{10} \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{2}\\
n_{10} \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{3}\\
n_{10} \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{4}\\
n_{10} \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{5}\\
\end{array}
\right\}
$
,
$
\left.
\begin{array}{c}
n_{10} \stackrel{f, f\geq f_{17}}{\longrightarrow}n_{2}\\
n_{10} \stackrel{f, f\geq f_{18}}{\longrightarrow}n_{3}\\
n_{10} \stackrel{f, f\geq f_{19}}{\longrightarrow}n_{4}\\
n_{10} \stackrel{f, f\geq f_{20}}{\longrightarrow}n_{5}\\
\end{array}
\right\}
$
,
$
\left.
\begin{array}{c}
n_{10} \stackrel{lf, lf\leq l_9}{\longrightarrow}n_{9}\\
n_{10} \stackrel{lf, lf\leq l_{10}}{\longrightarrow}n_{11}\\
\end{array}
\right\}
$
\\\hline
Node $11$ (Customer)&
$
\left.
\begin{array}{c}
n_{11} \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{2}\\
n_{11} \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{3}\\
n_{11} \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{4}\\
n_{11} \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{5}\\
\end{array}
\right\}
$
,
$
\left.
\begin{array}{c}
n_{11} \stackrel{f, f\geq f_{21}}{\longrightarrow}n_{2}\\
n_{11} \stackrel{f, f\geq f_{22}}{\longrightarrow}n_{3}\\
n_{11} \stackrel{f, f\geq f_{23}}{\longrightarrow}n_{4}\\
n_{11} \stackrel{f, f\geq f_{24}}{\longrightarrow}n_{5}\\
\end{array}
\right\}
$
,
$
\left.
\begin{array}{c}
n_{11} \stackrel{lf, lf\leq l_{11}}{\longrightarrow}n_{9}\\
n_{11} \stackrel{lf, lf\leq l_{12}}{\longrightarrow}n_{10}\\
\end{array}
\right\}
$
\\\hline
\end{tabular}
~\\
\normalsize
\caption{\small The list of promises grouped according to sender and type (completed over).}
\end{center}
\end{figure}
\begin{figure}
\tiny
\begin{center}
\begin{tabular}{|c|c|}
\hline
Node $12$ (Customer)&
$
\left.
\begin{array}{c}
n_{12} \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{2}\\
n_{12} \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{3}\\
n_{12} \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{4}\\
n_{12} \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{5}\\
\end{array}
\right\}
$
,
$
\left.
\begin{array}{c}
n_{12} \stackrel{f, f\geq f_{25}}{\longrightarrow}n_{2}\\
n_{12} \stackrel{f, f\geq f_{26}}{\longrightarrow}n_{3}\\
n_{12} \stackrel{f, f\geq f_{27}}{\longrightarrow}n_{4}\\
n_{12} \stackrel{f, f\geq f_{28}}{\longrightarrow}n_{5}\\
\end{array}
\right\}
$
,
$
\left.
\begin{array}{c}
n_{12} \stackrel{lf, lf\leq l_{11}}{\longrightarrow}n_{13}\\
n_{12} \stackrel{lf, lf\leq l_{12}}{\longrightarrow}n_{14}\\
\end{array}
\right\}
$
\\\hline
Node $13$ (Customer)&
$
\left.
\begin{array}{c}
n_{13} \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{2}\\
n_{13} \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{3}\\
n_{13} \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{4}\\
n_{13} \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{5}\\
\end{array}
\right\}
$
,
$
\left.
\begin{array}{c}
n_{13} \stackrel{f, f\geq f_{29}}{\longrightarrow}n_{2}\\
n_{13} \stackrel{f, f\geq f_{30}}{\longrightarrow}n_{3}\\
n_{13} \stackrel{f, f\geq f_{31}}{\longrightarrow}n_{4}\\
n_{13} \stackrel{f, f\geq f_{32}}{\longrightarrow}n_{5}\\
\end{array}
\right\}
$
.
$
\left.
\begin{array}{c}
n_{13} \stackrel{lf, lf\leq l_{15}}{\longrightarrow}n_{12}\\
n_{13} \stackrel{lf, lf\leq l_{16}}{\longrightarrow}n_{14}\\
\end{array}
\right\}
$
\\\hline
Node $14$ (Customer) &
$
\left.
\begin{array}{c}
n_{14} \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{2}\\
n_{14} \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{3}\\
n_{14} \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{4}\\
n_{14} \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{5}\\
\end{array}
\right\}
$
,
$
\left.
\begin{array}{c}
n_{14} \stackrel{f, f\geq f_{33}}{\longrightarrow}n_{2}\\
n_{14} \stackrel{f, f\geq f_{34}}{\longrightarrow}n_{3}\\
n_{14} \stackrel{f, f\geq f_{35}}{\longrightarrow}n_{4}\\
n_{14} \stackrel{f, f\geq f_{36}}{\longrightarrow}n_{5}\\
\end{array}
\right\}
$
,
$
\left.
\begin{array}{c}
n_{14} \stackrel{lf, lf\leq l_{17}}{\longrightarrow}n_{12}\\
n_{14} \stackrel{lf, lf\leq l_{18}}{\longrightarrow}n_{13}\\
\end{array}
\right\}
$
\\\hline
Node $15$ (Customer)&
$
\left.
\begin{array}{c}
n_{15} \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{2}\\
n_{15} \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{3}\\
n_{15} \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{4}\\
n_{15} \stackrel{d, d \in \{T,F \}}{\longrightarrow}n_{5}\\
\end{array}
\right\}
$
,
$
\left.
\begin{array}{c}
n_{15} \stackrel{f, f\geq f_{37}}{\longrightarrow}n_{2}\\
n_{15} \stackrel{f, f\geq f_{38}}{\longrightarrow}n_{3}\\
n_{15} \stackrel{f, f\geq f_{39}}{\longrightarrow}n_{4}\\
n_{15} \stackrel{f, f\geq f_{40}}{\longrightarrow}n_{5}\\
\end{array}
\right\}
$
\\\hline
\end{tabular}
~\\
\normalsize
\caption{\small The list of promises grouped according to sender and type (see previous page).\label{pr}}
\end{center}
\end{figure}
\normalsize
We illustrate the promises, as graphs, in
figs. \ref{model-q}-\ref{model-lf}. Even with the small system of
fifteen nodes, some of these graphs are relatively busy; however, they help to show
the mutual relationships in the distributed system. We note that fig. \ref{model-d}
covers both $d$ and $f$ promise types, since the arrows are the same
in each case. (This makes sense, since the promises to download and
forward messages to other customers are both contracts made with the
shops and the mall. They have formally different types, with different
constraints but we can save ourselves an illustration by noting that
the topology is the same.)
In a similar vein, it is worth noting that customers do not promise
anyone to download advertising from one another. If they do this, they do so
at their own option, as a matter of {\em voluntary cooperation}.
\begin{figure}[ht]
\begin{center}
\includegraphics[width=9cm]{figs/model-q}
%\psfig{file=model-q.eps,width=9cm}
\caption{The $q$-promise graph without labels.\label{model-q}}
\end{center}
\end{figure}
\begin{figure}[ht]
\begin{center}
\includegraphics[width=9cm]{figs/model-d}
%\psfig{file=model-d.eps,width=9cm}
\caption{The $d/f$-promise graph without labels. The graphs for $d$ and $f$ are the same.\label{model-d}}
\end{center}
\end{figure}
\begin{figure}[ht]
\begin{center}
\includegraphics[width=9cm]{figs/model-r}
%\psfig{file=model-r.eps,width=9cm}
\caption{The $r$-promise graph without labels.\label{model-r}}
\end{center}
\end{figure}
\begin{figure}[ht]
\begin{center}
\includegraphics[width=9cm]{figs/model-i}
%\psfig{file=model-i.eps,width=9cm}
\caption{The $i$-promise graph without labels.\label{model-i}}
\end{center}
\end{figure}
\begin{figure}[ht]
\begin{center}
\includegraphics[width=9cm]{figs/model-lf}
%\psfig{file=model-lf.eps,width=9cm}
\caption{The $lf$-promise graph without labels.\label{model-lf}}
\end{center}
\end{figure}
\begin{figure}[ht]
\begin{center}
\includegraphics[width=9cm]{figs/model-bargains}
%\psfig{file=model-bargains.eps,width=9cm}
\caption{The graph of various bargaining games within the network..\label{model-bargains}}
\end{center}
\end{figure}
\begin{figure}[ht]
\begin{center}
\includegraphics[width=9cm]{figs/model-tidy}
%\psfig{file=model-tidy.eps,width=9cm}
\caption{A simplified schematic graph based on the derived roles.\label{model-tidy}}
\end{center}
\end{figure}
\section{Graphical analysis}
We have constructed the typed promise graph based on this deliberate
scenario, but we can now analyze it, as a list of discovered promises,
without prejudice of its original intent.
There are two reasons why we might want to do this: i) verification,
i.e. for understanding the planning of promises required to bind a
group to a distributed objective; or ii) forensic reconstruction of
the scenario being played out.
The list of promises we have discovered might or might not be
complete, or even consistent, in relation to the objective observer's
impression of the network's goals. That remains for us to determine.
Moreover, in a more extensive scenario, we might
simply discover this list of promises without any particular knowledge
of the real world origin. What we refer to as a `shop' might bring
with it certain associations, such as a building with a facade and
shop employees; however, a shop might simply be a server process,
making and performing all the same promises as a physical shop from a
customer's personal device. Our analysis will avoid such prejudice and
group entities according to their function. We might then use the
following analysis as a forensic method of reconstructing its
function.
We emphasize yet again that a band of autonomous agents has no
guaranteed purpose or guaranteeable objective, in the traditional
sense: it can only have an emergent purpose, if the agents themselves
choose to collaborate to a sufficient and appropriate degree. Hence,
our question becomes: does this scenario behave like a shopping mall
with the economic model suggested above?
\subsection{Roles}
We begin by identifying the roles in the graph. There are two approaches
here. The first is based in ref. \cite{siri1} and the latter on
ref. \cite{roles}, which we shall address later. From
ref. \cite{siri1}, we take a node that is pointed to by many nodes of
a type $\tau$ to be a {\em $\tau$-role}. Identifying all such
structures in fig. \ref{pr}, or the illustrations, we find that:
\begin{itemize}
\item Nodes 2,3,4,5 play $d$-roles, i.e. they are recipients of multiple promises
and form an implicit group of those nodes which make such promises to them.
\item Promises $d,f$ to node 2,3,4,5 all come from group \\
${\cal G}_a=\{6,7,8,9,10,11,12,13,14,15\}$.
Hence these are are all {\em groups/roles by association}. They play a specific role in the
promise graph and hence they have a noteworthy meaning.
\item Node 2 makes a $q$-promise to appointed group ${\cal G}_b=\{3,4,5\}$, hence these
form a $q$-role.
Similarly node 1 makes the same promise to node 2.
Other q-roles include ${\cal G}_c=\{9,10,11\}$
${\cal G}_d=\{6,7,8\}$
${\cal G}_e=\{15\}$.
Thus nodes 1,2,3,4,5 have roles in common by appointing other roles.
\item 6,7,8,9,10,11,12,13,14,15 are d,f recipients.
\item with regard to $lf$-promises, the following complete subgraphs are self-appointed groups:
${\cal G}_f=\{6,7,8\}$,${\cal G}_g=\{9,10,11\}$,${\cal G}_h=\{12,13,14\}$.
\end{itemize}
We see the following association:
\begin{itemize}
\item 1,2,3,4,5 are all $q$-service providers. However these have the dependency structure $(1,(2,(3,4,5)))$.
\end{itemize}
The roles are thus summarized in fig. \ref{model-tidy}. We derive this
from a random list of promises, in no particular order and extract the
schematic behaviour accordingly. It is now easy to identify these
groups with the ISP, mall, shops and customers from the original
scenario.
\subsection{Games}
If we define a game, as in ref. \cite{siri2}, to be a back-to-back
bilateral promise, then we obtain the games in
fig. \ref{model-bargains}. This undirected graph yields its own
structure, from ref. \cite{roles}, and thus we identify topological
roles: ${\cal G}_i=\{3,6,7,8\}$,${\cal G}_j=\{5,9,10,11\}$,${\cal
G}_k=\{12,13,14\}$ and ${\cal G}_k=\{4,15\}$.
From fig. \ref{model-bargains} we see that, of all the nodes in the
graph, only node 1 does not participate in a bilateral promise. This
violates the principal of renumeration for a stable
relationship\cite{siri2}, and is therefore a problem to be rectified
(see below).
Finally, we note that there are no `cooperative groups' in this graph,
in the sense of ref. \cite{siri1}. That is, there are no groups who
promise to cooperate in their behaviour so as to behave as a seamless,
indistinguishable group, working together. This is a natural feature of
the present model, where the focus is on individual autonomy rather
than in cooperative collaboration by design.
\section{Stability and games}
Any working system requires a sufficiently stable core to allow it to
have predictable consequences\cite{burgessbook2}. In a collection of
autonomous individuals, predictability is related both to
environmental uncertainties (in a traditional reliability sense) as
well as to the likelihood that nodes will cooperate. Cooperation is,
in turn, related to what value autonomous agents derive from the relationships
with their neighbours. Stability in such a relationship is known to
require mutual benefit. This tells us immediately that sources and sinks
in the type-free or common-currency promise graph are potentially unstable
areas. Node 1 is clearly in such a position, in our model as described.
The notion of a bargaining game has been used as a reasonable means
of prediction of such cooperation\cite{axelrod2,axelrod1,siri2,agents}.
Having identified the games, in terms of back-to-back promises pairs,
as defined in ref. \cite{siri2} (see fig. \ref{game}).
One identifies the stability of such games by relating them to an
equivalent cooperative dilemma\cite{axelrod1} (see fig. \ref{dilemma}),
in which agents decide whether it is worth their while to cooperate with
their agreement, or whether they rather ought to `defect' from their
promises..
Such a game is characterized by four values, for which
one stability requires $T > R > P >S$. If the each agent's perceived
value for cooperation and non-cooperation (defection) satisfies this
inequality, there is a likelihood for stability in the promise relationship,
else it is unlikely that the promises will be kept.
\begin{figure}
\begin{center}
\includegraphics[width=5cm]{figs/dilemma}
%\epsfig{file=dilemma.eps,width=4cm}
\caption{The basic payoff matrix structure for a dilemma game.\label{dilemma}}
\end{center}
\end{figure}
\begin{figure}
\begin{center}
\includegraphics[width=5cm]{figs/yinyang}
%\epsfig{file=twoPromises.eps,width=6cm}
\caption{Node $A$ has made a promise ($\pi_{1}$) to node $B$, and node
$B$ has made a promise ($\pi_{2}$) to node $A$.\label{game}}
\end{center}
\end{figure}
It is worth noting that, of all the nodes, the ISP node 1 does not
participate either implicitly or explicitly in any game. It is purely
`exploited' in the sense of ref. \cite{siri2}. This is a weakness in
the current model. What is missing here is the remuneration node 1
receives for its own promises. In a real scenario, this would
doubtless be `real' money, and we henceforth add such a promise to
the model.
Having established the model as a collection of bargaining games, the
next step is to analyse the typical interaction policies between the
agents, to understand whether the games lead to lasting relationships,
or whether they are likely to fail; i.e.
one can use a basic two-player game model to estimate the likely
stability of the interaction between the agents who have games between
them.
To cover all incidents, we will need a separate game matrix for each
interaction, i.e. we need to define what kind of outcome each agent will
receive in the different possible scenarios. For simplicity, we consider only
the different {\em types} of game, parameterized in a general way.
\subsection{ISP and mall}
The relationship between the ISP and the (centralised) mall is rather
uncomplicated, the main service present is of course the Internet (and
phone) connection that the mall depends on in order to provide the
necessary service for its customers. The only responsibility the mall
has to the ISP is to actually
\emph{pay} for the services provided by the ISP. The payoff matrix for this
game is given in \ref{matrix1}.
\begin{table}[t]
\centering
\begin{tabular}[t]{lll} \hline
ISP, Mall & Mall cooperate & Mall defect \\
\hline
ISP cooperate & $P_s-C_s$, $S-P_s$ & $0-C_s$, $S$ \\
ISP defect & $P_s$, $C_r-P_s$ & 0, $C_r$ \\
\hline\\
\end{tabular}
\caption{Payoff matrix for the ISP-Mall game}
\label{matrix1}
\end{table}
In our example we have considered only \emph{two} parameters in the
payoff-model: \bigskip
\framebox{\small
\begin{minipage}[t]{0.8\linewidth}
\begin{description}
\item[$P_s$:] The price or fee the mall has to pay for service.
\item[$C_s$:] The cost for the ISP as a consequence of providing the
service.
\item[S:] The agreed level of service. This parameter is a numerical
unit, associated with the \emph{value} of the service.
\item[$C_r$:] The cost incurred by not having a sufficient
Internet service/connection.
\end{description}
\end{minipage}
}
\bigskip
\noindent The bargaining interpretation of moves is:
\begin{enumerate}
\item {\em Both cooperate.} The ISP delivers the agreed level of service,
while the mall pays the expected fee.
\item {\em The mall cooperates while the ISP defects.} This means the
mall pays the agreed price while the ISP fail to deliver the
agreed service. For simplicity, we assume that the value of the
service is $0$.
\item {\em The ISP cooperates while the Mall defects.} This means that
the ISP delivers the agreed service while the mall fails to pay.
Again we assume the value of the payment is $0$.
\item {\em Both defect.} The mall does not receive any service, and the
ISP does not receive any payment.
\end{enumerate}
\subsection{Customer and mall}
The mall wishes to reach each customer with certain information, for
instance by sending out messages to all customers that are
\emph{online} on the malls network. The customers however, are often
suffering from limited battery power and memory space, and hence they
not very interested in being flooded by unwanted information.
Customers want to be able to receive the information they need
\emph{on demand}, in addition to having a subsidised Internet and
phone connection. Providing the connection/access (through an ISP) is
a pure cost to the mall, but might also increase the customers usage
of their networks, and hence increased the probability that they will
receive and read the messages distributed by the mall. In addition to
being a significant cost, giving users access to the Internet also
impose the risk of the users actually taking advantage of the mall
network by consuming too much. These scenarios include aspects that
are not necessarily related, and hence we have chosen to represent
them by two different game matrices.
The first case is solved by the mall promising the customer to keep the flow
of messages within a defined limit, while the customer promises to
download the messages as they arrive. The game matrix for this case is given
in \ref{matrix2}. The parameters used in this model are \bigskip
\framebox{\small
\begin{minipage}[t]{0.8\linewidth}
\begin{description}
\item[$R_{\rm max}$:] The maximum limit for the number of messages per hour
sent to a customer(mobile host)
\item[$R_{\infty}$:] Rate of messages per hour sent to a customer(mobile
host) that exceeds the maximum rate $R_{\rm max}$
\item[$V_{msg}$:] The estimated value of sending \emph{one} message to a
customer. This value is a result of the saved costs from not needing to
use billboards etc for diverse information.
\item[$C_{msg}$:] The associated cost (for the mall) of sending one
message.
\item[$I$:] The associated value of receiving a message (information
value).
\item[$C_r$:] The cost (in energy) associated with receiving a message
\end{description}
\end{minipage}
}
\bigskip
\begin{table}[t]
\centering
\begin{tabular}[t]{lll} \hline
Customer, Mall & Mall cooperate & Mall defect \\
\hline
Customer cooperate & $(I - C_r)R_{\rm max}$, $(V_{msg} - C_{msg})R_{\rm max}$ &
$(I - C_r)R_{\infty}$, $(V_{msg} - C_{msg})R_{\infty}$ \\
Customer defect & $0$, $- C_{msg}R_{\rm max}$ & $0$, $- C_{msg}R_{\infty}$ \\
\hline\\
\end{tabular}
\caption{Payoff matrix for the Customer-Mall game: sending and receiving messages from mall.\label{matrix2}}
\end{table}
\bigskip
The agents' move combinations are:
\begin{description}
\item[CC] The Mall is able to reach the customer,
and the customer is not bothered too much by overflow of messages.
The mall has the gain $(V_{msg} - C_{msg})R_{\rm max}$, which is the net
value of sending a message times the number of messages sent per
defined time interval. The customer, on the other hand, receives the
value $(I - C_r)R_{\rm max}$.
\item[CD] {\em The customer cooperates.}
The customer stays online, while the mall exploits this to send a
larger amount of messages than the customer appreciates. The mall has
the gain $(V_{msg} - C_{msg})R_{\infty}$, while the customer receives
$(I - C_r)R_{\infty}$.
\item[DC] {\em The mall cooperates.}
The mall keeps its message rate below a sensible level, but the
customer still does not bother to stay online. The mall has a net loss
equal to the cost of sending the messages, while the customer has a
gain of zero.
\item[DD] {\em Both defect.} The mall spends a lot of resources on
sending a large volume of messages, which are not received as the
customer is not online. Payoff values are similar to the previous
example.
\end{description}
In the second game, the mall promises the customer an Internet
connection with a certain bandwidth, while the customer promises to not
over-consume bandwidth.
\bigskip
\framebox{\small
\begin{minipage}[t]{0.8\linewidth}
\begin{description}
\item[$U_{\rm max}$:] The maximum amount of bandwidth a customer should
consume (on average over some time interval).
\item[$BW_{min}$:] The minimum average bandwidth provided by the mall
(via the ISP).
\item[$C_{\rm bw}$:] The cost of providing the agreed service/bandwidth.
\item[$r_+$:] The (positive) reputation/popularity the mall receives
from providing a good service.
\item[$r_-$:] The (negative) reputation the mall loses from providing
a poor service.
\item[$V_{low}$:] The value of receiving lower bandwidth.
\item[$V_{\rm bw}$:] The value of consuming the maximum bandwidth allocated
for one customer.
\item[$V_{\infty}$:] The value of consuming more than the maximum
allocated bandwidth.
\end{description}
\end{minipage}
}
\bigskip
We assume $V_{low} < V_{\rm bw} < V_{\infty}$.
\begin{table}[t]
\centering
\begin{tabular}[t]{lll} \hline
Customer, Mall & Mall cooperate & Mall defect \\
\hline
Customer cooperate & $V_{\rm bw}$, $r_+ - C_{\rm bw}$ & $V_{low}$, $r_+$ \\
Customer defect & $V_{\infty}$, $r_- - C_{\rm bw}$ & $V_{low}$, $r_-$ \\
\hline\\
\end{tabular}
\caption{Payoff matrix for the Customer-Mall game: network usage}
\label{matrix3}
\end{table}
The interpretation of table \ref{matrix3} is;
\begin{description}
\item[CC] {\em Both cooperate.} The Mall provides the customer a
reasonable bandwidth, while the customer does not consume more than
his fair share. The mall gains reputation amongst
its customers, as the available bandwidth is not affected too much by
the usage from the customer, but still has the cost of providing the
service. The net gain for the mall is represented by $r_+ - C_{\rm bw}$,
while the customer has the net gain of $V_{\rm bw}$.
\item[CD] {\em The customer cooperates.} The
customer uses the network with caution, while the mall fails to
deliver the agreed bandwidth. The mall avoids the cost of providing
the full service, and since the customer avoids over-consumption, the
average performance is not as affected, and the reputation of the
malls service is not affected. The net gain for the mall is hence
$r_+$. The customer on the other hand receives the reduced value
$V_{low}$.
\item[DC] {\em The mall cooperates.} The mall
provides the agreed bandwidth, which the customer exploits by
over-consuming, to the obvious disadvantage of its peer customers and
other users of the network. Implicitly this is a big disadvantage to
the mall. The result payoff for the mall is hence $r_- - C_{\rm bw}$,
while the customer receives the $V_{\infty}$.
\item[DD] {\em Both defect.} The mall fails to deliver the appropriate
service, while the customer consumes as much as possible. The overall
reputation is low, and the customer does not receive maximum bandwidth
because of lower total available capacity. Payoff for the mall is hence
$r_-$ while the customer receives $V_{low}$.
\end{description}
\subsection{Customer-customer}
The only interaction between customers modelled in our example, is the
exchange of promotional messages originally sent by the mall/shops.
The parameters are
\bigskip
\framebox{\small
\begin{minipage}[t]{0.8\linewidth}
\begin{description}
\item[$R_f$:] The reward (points) received from the mall for forwarding a
message to a \emph{peer} customer.
\item[$E_{\rm send}$:] The energy consumed by sending a message.
\item[$E_{\rm rec}$:] The energy consumed by receiving a message.
\item[$N_{\rm max}$:] The maximum number of messages a node should forward
to another during some time interval.
\item[$N_{\infty}$:] Notation for a number of messages forwarded that
satisfies $N_{\rm max} < N_{\infty}$.
\end{description}
\end{minipage}
}
\bigskip
These parameters are used when computing the different payoff values in the
game matrix in table \ref{matrix3}.
The reasoning behind these values is:
\begin{description}
\item[CC] {\em Both cooperate.} This means they both keep the flow of
forwarded messages to each other below the agreed limit ($N_{\rm max}$).
Both customers receive $(R_f-E_s-E_r)N_{\rm max}$
\item[CD] {\em One cooperates.} The defector
wins more credits, while the cooperator suffers from an overload of
messages. The cooperating customer receives the payoff $(R -
E_s)N_{\rm max} - E_rN_{\infty}$, while the defecting one receives $(R -
E_s)N_{\infty} - E_rN_{\rm max}$.
\item[DD] {\em Both defect.} Both offer more than the agreed number of messages and
receive a higher number of credits, but in the long run suffer from
battery and bandwidth problems. They both should gain
$(R_f-E_s-E_r)N_{\infty}$, but as the demand for energy is too high,
they both receive $0$.
\end{description}
\begin{table}[t]
\centering
\small
\begin{tabular}[t]{ll} \hline
Customer 1, Customer 2 & Customer 2 cooperate \\
\hline
Customer 1 cooperate & $(R_f-E_{s}-E_{r})N_{\rm max}$, $(R_f-E_{s}-E_{r})N_{\rm max}$
\\
Customer 1 defect & $(R_f - E_s)N_{\infty} - E_rN_{\rm max}$, $(R_f - E_s)N_{\rm max}
- E_rN_{\infty}$ \\
\hline
\end{tabular}
\begin{tabular}[t]{lll} \hline
Customer 1, Customer 2 & Customer 2 defect \\
\hline
Customer 1 cooperate
& $(R_f - E_s)N_{\rm max} - E_rN_{\infty}$, $(R_f - E_s)N_{\infty} - E_rN_{\rm max}$ \\
Customer 1 defect & $0$, $0$ \\
\hline
\\
\end{tabular}
\caption{Payoff matrix for the Customer-Customer game: forwarding messages from mall}
\label{matrix4}
\end{table}
\section{Policy, strategy and uncertainty}
The foregoing game models describe the outcomes of single `encounters'
between different kind of agents. To predict the outcome of models
over time, we need to analyse the games over multiple interactions.
The common way to do this, is to use the
\emph{iterated} dilemma models, where the outcome of each round is
recorded, and is taken into consideration when the players meet
again for a new round. This requires the recent game
history of both players to be available to their opponents.
From the previous paragraphs, it should be obvious that these kinds of
scenarios constitute a huge potential complexity in terms of the many
individual games to be played. Without some simplifying device, it
could become intractable to obtain a realistic picture of all the
issues. Fortunately, one may be inspired by the principle that
management is about the approximate constraint of a system, not about
completely predictable control. The latter would be a hopeless expectation
in a collaboration based on voluntary cooperation.
Voluntary cooperation theory tells us that `rational' agents, in some
sense, behave so as to maximize their particular payoff. Since this
involves an element of trust of those one interacts with, each round
of interaction involves the choice of whether to cooperate or whether
to break that trust, for each of the autonomous agents. How they
choose to play is their own concern. We consider only a few well-known
policies (strategies) for interaction\cite{axelrod1,axelrod2}:
\bigskip
\begin{enumerate}
\item {\em Always cooperate}: The agent keeps its promises
agent all the time, independently on the other's behaviour.
\item {\em Tit for tat}: The agent always does what its `opponent'
did on the previous encounter. The agent never defects unless the other
agent does.
\item {\em Tit for two tats}: Analogous to {Tit for tat}, but an
agent does not defect until the opponent has defected \emph{twice} in
a row. This strategy is hence known for being more \emph{forgiving}
than Tit for tat.
\item {\em Occasional defections}: The agent cooperates per default, but
tries to get away with occasional defections, to improve overall score.
\item {\em Random}: The agent has no general rule, it cooperates or
defects at random.
\item {\em Always defect}:The agent never keeps it promises to any other
agent.
\end{enumerate}
To follow the Pervasive Computing Environment as the conditions
change, we can perform a simulation of node activity. This is done by
assigning each node a certain strategy, from the above, and then
letting them interact with one another over some time. Each pair of
agents involved in an interaction plays one round of a game and
receives payoff according to the game matrix.
The cumulative result of many rounds of interaction results in one
kind of common currency graph for the model. We defined this graph in
\cite{siri1}, as a snapshot of the promise graph, where each promise
has been reduced to a single, dimensionless real number. There might
be alternative approaches to estimating the reliability of the agents,
with respect to keeping their promises. Traditional reliability theory
could play a role here, depending on the nature of the
environment\cite{hoyland1}.
The common currency graph is represented by its adjacency matrix,
which is a linear combination of the adjacency matrices of the
separate promise types in the scenario. There is no unique matrix that
fits this description, so we shall deal only with an example. The
size of the adjacency matrix is equal to square of the number of
agents participating in the scenario, or the number of nodes in the
graph who have made any promises to anyone. For our scenario, this
means that the size of the matrices is $15 \times 15$ (see
fig. \ref{matrix-big}).
Each element $a_{i,j}$ is a measure of the reliability and activity
level of agent $i$ as experienced by agent $j$. For each promise
$\pi_k$ $i$ has given to agent $j$, $j$ monitors with which
probability this promise is kept. This results in a number $p_k$ for
each promise $\pi_k$, where $p_k \in [0,1]$. For each pair of agents
$(i,j)$ these numbers are summed up and represented in the adjacency
matrix.
Large numbers in the matrix then indicates two different aspects of
agent behaviour:
\begin{enumerate}
\item The promising agent has a high level of reliability, as there is a high probability of kept promises.
\item The promising agent has made a large number of promises.
\end{enumerate}
The weakness in the method lies in the fact that one can not separate
between a low number of agreements made by an agent, and whether the
agent has failed to keep its promises.
One can establish any number of common currency graphs\cite{siri1} in
order to explore different properties of the distributed system. As a
straightforward example, we estimate the sum of the individual promise
probability graphs, i.e. the reliability of keeping each of the
promise types (see fig
\ref{matrix-big}). In section \ref{eigsec} we shall use this to
compute the importance of the nodes to the distributed system.
\begin{figure}
\small
\begin{displaymath}
A_{\rm Common-currency} =
\left(\begin{array}{ccccccccccccccc}
0.0 & 0.9 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0\\
0.0 & 0.0 & 1.7 & 1.7 & 1.7 & 1.7 & 1.7 & 1.7 & 1.7 & 1.7 & 1.7 & 1.7 & 1.7 & 1.7 & 1.7\\
0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 2.5 & 2.5 & 2.5 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0\\
0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 2.6\\
0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 2.4 & 2.4 & 2.4 & 0.0 & 0.0 & 0.0 & 0.0\\
0.0 & 1.4 & 1.4 & 1.4 & 1.4 & 0.0 & 0.7 & 0.7 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0\\
0.0 & 1.8 & 1.8 & 1.8 & 1.8 & 0.9 & 0.0 & 0.9 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0\\
0.0 & 1.8 & 1.8 & 1.8 & 1.8 & 0.9 & 0.9 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0\\
0.0 & 1.4 & 1.4 & 1.4 & 1.4 & 0.0 & 0.0 & 0.0 & 0.0 & 0.7 & 0.7 & 0.0 & 0.0 & 0.0 & 0.0\\
0.0 & 1.0 & 1.0 & 1.0 & 1.0 & 0.0 & 0.0 & 0.0 & 0.5 & 0.0 & 0.5 & 0.0 & 0.0 & 0.0 & 0.0\\
0.0 & 0.4 & 0.4 & 0.4 & 0.4 & 0.0 & 0.0 & 0.0 & 0.2 & 0.2 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0\\
0.0 & 1.6 & 1.6 & 1.6 & 1.6 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.8 & 0.8 & 0.0\\
0.0 & 1.8 & 1.8 & 1.8 & 1.8 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.9 & 0.0 & 0.9 & 0.0\\
0.0 & 1.6 & 1.6 & 1.6 & 1.6 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.8 & 0.8 & 0.0 & 0.0\\
0.0 & 1.4 & 1.4 & 1.4 & 1.4 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0\\
\end{array}\right)
\end{displaymath}
\normalsize
\caption{The sum matrix of probabilities for promises of all types, estimated
over time.\label{matrix-big}}
\end{figure}
\subsection{Example reliability}
Given the game models, or expected decisions, and the chosen strategy
by each agent, we can predict an agent's moves. By letting the agents
interact several times over some time interval, we can compute the
level of cooperation among the agents on average for that specific
time interval. An example of this was presented in ref. \cite{siri2}.
\bigskip
\begin{definition}[Cooperation probability ]
The cooperation probability of an agent $j$ relative to agent $i$ is
noted by $p_c^i(j)$, and is computed according to the formula
\begin{displaymath}
p_c^i(j) = \frac{C}{I}
\end{displaymath}
where $C$ is the number of times agent $j$ cooperated in interactions
with agent $i$, and $I$ is the total number of interactions
between agents $i$ and $j$.
\end{definition}
\bigskip
Consider two of the agents in the Smart Mall, for instance node $6$ and node
$7$, noted by agent $A$ and agent $B$ in this example,
which are both customers. These two are in the same wireless range, and are
able to forward messages to each other. They both make a promise to each
other about keeping the number of forwarded messages below \emph{ten} per
hour, which on average implies maximum \emph{one} per five minute interval.
An interaction between these two agents consists of a message being
forwarded from one to the other, for instance from $A$ to $B$. As long
as the total number of messages from $A$ to $B$ is equal to or less
than ten during one hour, agent $B$ record this as cooperative
behaviour. As soon as message number
\emph{eleven} arrives at $B$ within one hour, the action is being identified
as `defectious' behaviour, or that the promise $\pi_{AB}$ has been broken.
For each of the agents to be able to evaluate the behaviour of its
opponent, they both keep a record of the previous interactions between
them, or more precisely, the actions of the opponent agent. From this
record, the {\em cooperation probability} of each of the agent can be
calculated.
\bigskip
For the entire graph representing all the agents in the smart mall
example, the same mechanisms mentioned in the previous example must be
taken into consideration for \emph{each pair} of interacting
agents. The cooperation probability is computed for each promise, and
added as a scalar \emph{weight} to the edge each promise graph. We
then create the new graph of weighted edges, where each weight now
represents the level of cooperative behaviour for each promise. This
graph can be applied in several different ways.
\section{Predictable Dilemmas}
To be able to predict the outcome of the games, we are particularly
interested in whether the payoff matrices of our example scenario
satisfy the constraints of a Dilemma game
model, i.e. that we should have:
\begin{enumerate}
\item $T > R > P > S$
\item $ R > \frac{T + S}{2} $
\end{enumerate}
The promises in the game, seem reasonable, as do the costs involved in making
them---but is this seeming reasonableness sufficient to ensure a functional
network?
We will now go through each of our game matrices, and for each one we
will discuss for what kind of parameters these constraints will or
will not satisfy the constraints.
\subsection{Table II : ISP-Mall game}
We see that constraint 1 reduces to
\beq
P_s > P_s - C_s > 0 > -C_s
\eeq
which is trivial iff $C_s > 0$, and hence the cost of
providing a service should ideally be non-zero and positive.
Constraint $2$ simply reduces to
\beq
P_s > C_s
\eeq
which means that the price demanded by the ISP should be larger than the
cost it incurs in providing the service.
For the Mall,
constraint $1$ hence implies
\beq
S > S - P_s
> C_r
> C_r - P_s
\eeq
which, given that $P_s > 0$, implies that $S - P_s > C_r$, which also is the result constraint after applying constraint $2$.
This implies that the value of the agreed service minus the price
payed for the service, i.e. the net value for the mall, after buying
the service, should be larger than the costs associated with not having
the service. This will always hold when the net gain is greater than
or equal to zero and makes intuitive sense.
\subsection{Table III: Customer - Mall I}
The constraints here do not hold for either of the parties in this
case. The implications of this is that we do not have a Dilemma game
for the customer-mall interaction, and hence the known stabilities of
dilemma games do not apply here, without modifications to the policy.
\subsection{Table IV: Customer - Mall II}
Again, constraint $1$ is not fulfilled, since
\beq
T > R > P = S
\eeq
i.e. the requirement $P > S$ is not fulfilled.
For the mall, we need
\beq
r_+ > r_+ - C_{\rm bw} > r_- > r_- - C_{\rm bw},
\eeq
which is fulfilled as long as $C_{\rm bw} > 0$, and $r_+ - C_{\rm bw} > r_-$.
This implies that the value of having a good reputation, minus the
cost associated with gaining it, must be worth more to the mall than the loss of
reputation from not providing an adequate service. Since $r_-$ is \emph{negative},
this means that the constraint allows $C_{\rm bw}$ to be up to $|r_-|$
units bigger than $r_+$, which means the cost of maintaining a
reputation is bigger than the associated value of the reputation.
For constraint $2$ to be satisfied, we need
\beq
r_+ - C_{\rm bw} > \frac{r_+ + r_- - C_{\rm bw}}{2},
\eeq
which holds iff $r_+ - r_- > C_{\rm bw}$, implying that maintaining a good
reputation needs to be a cheaper proposition than the cost to the agent to turn
a bad reputation into a good one. This seems like a reasonable assumption.
\subsection{Table V: Customer - Customer}
Consider constraint $1$:
$T > R$, we need $R_f - E_s > 0$, which is equivalent of $R > E_s$, which
means that the value of the credits earned by sending a message
must be larger than the value of the energy wasted by sending a
message. Simply put, a customer must have a net gain from forwarding a
message to another customer.
Further, for $R > P$, it is necessary that
\beq
(R_f - E_s - E_r)N_{\rm max} > 0
\eeq
which again implies that $R > E_s + E_r$. We notice that this
constraint is stronger than the previous one. It translates as: the
credits earned from forwarding messages must be of greater value than
the sum of the energy consumed by sending a message and the energy
consumed by receiving a message.
Finally, to check if $P > S$, we need to establish whether
\beq
(R_f - E_s)N_{\rm max} - E_rN_{\infty} < 0.
\eeq
Constraint $2$ requires that
\beq
(R_f - E_s - E_r)N_{\rm max} > \frac{(R_f - E_s -R_r)(N_{\rm max} + N_{\infty})}{2}.
\eeq
For instance, if we assume $N_{\infty} = 2N_{\rm max}$, the requirement $R >
\frac{T + S}{2}$ then reduces to
\beq
R_f > \frac{3}{2}R_f,
\eeq
which holds only if $R_f$ is negative, defeating its purpose. This
means that the sum of the energy consumed sending and receiving a
message is bigger than the credits earned forwarding a message. This
requirement fails to hold if constraint $1$ is to hold, so this case
is clearly \emph{not} a Prisoner's Dilemma for this value of
$N_{\infty}$.
The conclusion is that the promise values in this model are not
sufficiently well motivated to make voluntary cooperation a
likelihood. A policy maker, who hopes to have this mall environment
succeed would be advised to arrange for the conditions of the promises
to be more conducive to cooperative behaviour by altering either
policy or pricing. This can only be achieved by altering the basic
valuations or attitudes specified.
\section{Importance Ranking}\label{eigsec}
We return, finally to the extraction of management overviews that
might be useful to a planner, or to an agent entering into a new
environment.
The importance ranking of nodes using the spectral properties of a
network is a method that derives from social network theory and is growing in
importance\cite{pagerank,page98pagerank,ding02:unified,roles,burgessroles}; see
ref. \cite{burgessbook2} for an introduction. This model has been applied to
ad hoc networking in ref. \cite{festor1}
In ref. \cite{siri1} it was proposed
to use this method to establish the average understanding of critical node
structure.
The adjacency matrix of the common currency graph is a directed graph
of probabilities for cooperation, as determined either by
observational experience or game theoretical prediction. Each arrow in
this graph is a probable promise, or a willingness to do something for
a neighbour in the pervasive distributed system. The spectral
properties of this graph can tell us about the global properties and
its structure. In particular, the method of eigenvector ranking allows
us to rank the agents in terms of the currency of their cooperation,
with regard to every other node in the network. By doing this, we
obtain a fair picture of the contributions each agent makes to the
collective activity. The functionality of the distributed system is
already implicitly defined by the topology of the promise {\em types}; we are now
looking at the reliability of the system.
Since the promise graph is directed, the common currency adjacency matrix is
also directed and hence $A
\not = A^{\rm T}$. We compute the principal eigenvector of both these to
obtain the following interpretations (see fig \ref{eig}).
\begin{itemize}
\item eig($A$) makes the highest ranking node equal to the most willing to cooperate (the most
subservient or easily influenced node). This information is of great value to anyone
wishing to exploit agents.
\item eig($A^{\rm }$) makes the highest ranking node that which is most able to attract
promises (the strongest recipient of services from around the network).
\end{itemize}
The eigenvalues and components of the principal eigenvector sum up
recursively the contributions from the entire graph, i.e. they do more
than simply count promise reliabilities between neighbours: they give
a distributed notion of reliability and hence stability.
The similarity of concept with refs. \cite{hendrickx1,hendrickx2} is noteworthy.
Eigenvector ranking of the
common currency graph leads to the results in table \ref{eig}.
\begin{table}[ht]
\centering
\begin{tabular}[t]{c|ccc}
Rank & Agent numbers\\
position & $A$ (Senders) & $A^{\rm T}$ (Receivers) & $A+A^{\rm T}$\\
\hline
\small 1 & 2 & 3 &2\\
\small 2 & 13 & 4 &3\\
\small 3 & 7 & 5 &5\\
\small 4 & 8 & 2 &7\\
\small 5 & 12 & 6 &8\\
\small 6 & 14 & 7 &4\\
\small 7 & 3 & 8 &6\\
\small 8 & 6 & 11 &13\\
\small 9 & 9 & 10 &9\\
\small 10 & 15 & 9 &12\\
\small 11 & 10 & 15 &14\\
\small 12 & 5 & 12 &15\\
\small 13 & 1 & 14 &10\\
\small 14 & 11 & 13 &11\\
\small 15 & 4 & 1 &1\\
\end{tabular} \caption{Ranking of the nodes from top to bottom. The
topmost nodes are most powerful ($A^{\rm T}$), or most
subservient ($A$). Rank values for nodes \{7,8\} and \{12,14\} are
identical in each case, indicating a symmetry. Also, the rank
positions for
\{3,4,5\} are identical for $A^{\rm T}$.\label{eig}}
\end{table}
\begin{figure}[ht]
\begin{center}
\includegraphics[width=9cm]{figs/model-rank-power}
%\psfig{file=model-rank-power.eps,width=8.5cm}
\caption{A rank contour for the model, showing the influentialness or `power' the
agents have to attract promises (strong receivers),
eig($A^{\rm T})$.\label{model-rank-power}}
\end{center}
\end{figure}
\begin{figure}[ht]
\begin{center}
\includegraphics[width=9cm]{figs/model-rank-servile}
%\psfig{file=model-rank-servile.eps,width=8.5cm}
\caption{A rank contour of the `willingness' of the nodes to offer and keep
promises (strong senders), eig($A$).\label{model-rank-servile}}
\end{center}
\end{figure}
One sees from the graph that the most `powerful' or coercive agents in
this system are the shops. They even outrank the mall. Indeed the
service provider (node 1) is a non-entity in this regard, since it is
largely outside the area of activity.
The mall node is also of central importance in binding the other nodes
together. If one removes the mall node 2, the graph splits into two natural
regions, in the sense of ref. \cite{roles}, which are dominated by two
of the shop nodes 4 and 5 (see fig. \ref{archip}). These are then bridged together in a
virtual mall by the interacting customers. This is an interesting result, because
it tells us that the establishment of a centralized mall authority is not
necessary for the functioning of the mall. While it might have acted as a seed
for the resulting structure, business can proceed without it when customers are
enabled with personalized services.
\begin{figure}[ht]
\begin{center}
\includegraphics[width=9cm]{figs/archip}
%\psfig{file=archip.eps,width=8.5cm}
\caption{Eliminating the mall node 2 isolates the ISP node and forms two network
regions dominated by two of the shops and bridged by the
intermediary customers.\label{archip}}
\end{center}
\end{figure}
We see the power of the present method, in being able to identify these functional
structures regardless of one's initial prejudices about the functions
of the agents. The roles they assume occur through their promises to others
in the collective. A mall is simply a community structure. It does not
necessarily require a named object to control it.
Customers are `powerful' if they are associated with powerful
shops or conglomerates of customers, i.e. they inherit promises
from those they are promised by, and hence accumulate the certainty that
bolsters their own standing in the network.
\section{Discussion and conclusions}
We have explored a pervasive computing scenario, in which a central
feature is the autonomy of the devices within a region of interaction.
We have demonstrated how promise theory can be utilised as a tool for
predicting the coalitions and structures in a pervasive computing
scenario, with or without prior knowledge. Contradictory policies are
easily found using the notion of a broken promise, and potential flaws in the
scenario are apparent as sources and sinks in the directed graph.
As a tool for modelling, the programme we propose is summarized as
follows:
\bigskip
\begin{itemize}
\item Identify \emph{autonomous agents}, and determine their policies and
\emph{strategies} for interaction.
\item Identify the \emph{promises} between the interacting
agents.
\item Define interaction pattern (interaction frequency) of the
agents.
\item Derive the labelled \emph{adjacency matrices} for each
\emph{type} of promise.
\item For each interacting pair of agents compute estimated payoff
for each agent in order to estimate the likely strategy and hence
cooperativeness of the agent.
\item Update the adjacency matrices according to
the payoff matrices and the interaction pattern. \end{itemize}
\bigskip
There are many outstanding issues to be considered, both in promise theory
and in its application to pervasive computing.
\begin{itemize}
\item How do promises arise to begin with?
\item What consequences arise from the specifics of the individual promises (here we have only
focused on the differing types of promise).
\item How does one develop the payoff function, in respect to an environment?
\item Does the number of nodes itself influence the payoff values?
\item How do we model interaction/encounter between agents that have made
several promises to each other?
\item Network usage: could be customer-customer game?
\end{itemize}
We have made almost no reference to `cooperative' promises $C(\pi)$ in this
paper\cite{burgessdsom2005}. Such promises are instrumental in securing
reliability and consistency in a distributed environment. They are therefore
most important in more traditional scenarios of `managed networks'.
The value of the present method to network forensics can also be
explored in more depth. What can we learn from structure itself? In
the view of refs. \cite{roles,burgessC12}, structure and function are
often closely mapped and a full understanding of the structure allows
one to infer much about the function. This point of view is important
in a situation of widespread autonomy, as management takes on the role
of a police force watchful of infractions rather than pulling the
strings of the devices.
| Administrator | ViewVC Help |
| Powered by ViewVC 1.0.3 |