Probabilistic Postoffice Problem Architecture

Satellite Image of Hokkaido Island, Japan.

Changes:


Scenario:

There are N members and one spy. Initially each member has exactly one message with his/her own identification. Each member wants to distribute the message to all the members. Each message should be sent via one postoffice. The spy tries to read a fraction of the messages at one or more postoffices. Your mission is to design a protocol which distribute the messages to all the members as quickly as possible with preventing the spy from reading messages as much as possible.

This problem is different from the original problem in that delivery happens probabilistically. In the original problem, every state was considered as discrete and the spy could delay each delivery to arbitrary length to fit to the spy's plan. But in this modified version each delivery follows a certain distribution. Here is the original problem description.

Rules:

Here is a schematic view of the description above:

Information you can use:

At every morning, each member can make a decision based on the following information:

They do not know:

With these restrictions, your protocol can be written as a set of if-then statements (see below).

Information the spy can use:

How long a delivery can take:

Each delivery takes at least one day. Some of them may take several days. The number of days follows a certain distribution which is given as a parameter.

Examples:


Implementation:

Parameter List

At the beginning of a game, your program receives the following parameters:

Here is a sample:

MESSAGE 4
FRACTION 2
VISIT 2
POSTOFFICE 4                  (there are four postoffices: A, B, C and D.)
REACHABILITY 50 30 20 0 0     (equivalent to [0.5, 0.3, 0.2, 0.0, 0.0])

Protocol Format

After taking these parameters, your program generates a set of if-then statements for each member in the following format:

@member: cond1, cond2, ..., condN: action1, action2, ..., actionM

Each line should contain a member label, conditions, and actions. For example:

@1: =1,!2,+3: 1>4-A, *2, 3>2-B

The first field (@1) indicates which member this statement is instructed to.
The second field (=1,!2,+3) is a list of conditions. Each condition is specified in the following format:

NOTE1: Each statement must contain at least one +n condition. This is activated only when the message is delivered, and it triggers the following actions. At the very beginning (day=0), every member receives his/her own message. This initiates the whole process.

NOTE2 (Oct. 31): Extra blanks and commas are ignored. Therefore,

     @ 1 : =1, ! 2, +3,,, :  1 > 4 - A,, *2, 3 > 2 - B ,
is also a valid statement.

The third field (1>4-A, *2, 3>2-B) is a list of performed actions if ALL the conditions are satisfied (if you want to write "OR" condition, you can do this by giving multiple statements). Each action is specified in the following format:

To send a message, you must have the message. So either "=m" or "+m" must be included in the condition field.

The sample statement can read as follows:

"For Member-1,
   if you already have Message-1 and do not have Message-2, and Message-3 is just delivered,
     then send Message-1 to Member-4 via Postoffice-A, rest 2 days, and then send Message-3 to Member-2 via Postoffice-B.
"

You can give multiple statements to each member. At every turn, all statements are scanned and any satisfied statement is executed parallelly.

Any string following "#" character can be regarded as a comment. A sample list can be:

# for member 1
@1: =1,!2,+3: 1>4-A, *2, 3>2-B
@1: =1,=2,+4: 1>3-C, 2>4-A, 4>2-B
@1: +1: 1>2-A, 1>3-D               # this must be triggered first.

# for member 2
@2: =2,+3: 2>1-B, 3>4-D
...

Evaluation program:

The evaluation program takes the parameters and your output specified above and gives a score of your protocol. The score is calculated based on the probability of each message staying at a postoffice without running an actual protocol.

The system maintains two matrix: event matrix and postoffice matrix.

A event matrix (shown below) holds the probability of having or receiving a message for each member and day. First, the system calculates the probability for each condition being triggered for a certain day. Then the system assigns the probability of deliveries caused by each action to the following days. By repeating this from day=0, it can calculate the probabilities of delivery chains.

For example, there are two conditional statements in the protocol:

@1: +1: 1>2-A ...(1)
@2: +1: 1>3-B ...(2)

In this case, the probability of the statement (1) being triggered at day=0 is 1.0. Then it distributes the probability of delivery 0.5, 0.3 and 0.2 for Member-2 to the following days. Now, say at day=2, the probability of the statement (2) being triggered is 0.3 because Member-2 will receive the message with probability=0.3 at this time. Then it further distributes the probability of delivery caused by the statement (2) for Member-3, so on:

At the same time, the system also builds a postoffice matrix, which holds the probability of a certain message staying at a certain postoffice.

In addition to the example above, suppose at the morning of day=2, Member-3 sent his/her own message to someone via Postoffice-B. Then the postoffice matrix could be:

In the above example, there are Message-3 at Postoffice-B with 100% probability, and Message-1 at Postoffice-B with 15% probability. So if the spy visits this point, he/she will read one or two messages with this probability.

Scoring metrics:

The scoring metrics of this problem is also different from the original. You get two numbers: the expected days to deliver all the messages and the probability of being caught by the spy. In the class we decided "the security is first" which means that the probability of success takes precedence over the speed.

The strategy of the spy is to pick a set of locations and dates which maximizes the probability of having messages. Then the program takes the messages which have FRACTION highest probabilities. Since this is a kind of NP-complete problem, there is no guarantee to find the best answer in some short time. The expected days is computed from the event matrix deterministically.

Usage:

The evaluation program is post.py. On Sun machines it's placed at /home/yusuke/post.py . When you run this on your machine, you need Python 2.3 or newer.

First it reads parameters and then reads a protocol specification. You can give them with either a single (concatenated) file or multiple files. It reads files from given arguments or the standard input. You can also give or override some parameters with command-line options on the fly.

Synopsis

 post.py [-d] [-H] [-m member] [-f fraction] [-p postoffice] [-v visit] [-r 1,2,...,n] [-i iteration] [file ...]

Examples

 $ ./yourprogram parameterfile > result
 $ ./post.py -H result > result.html
 $ netscape result.html
or
 $ ./yourprogram parameterfile | ./post.py -m 4 -f 2 -p 2 -v 2 -r 50,50 -i 10000

Options

The following options can be used to override parameters:

Limitations

There are arithmetic errors with small probability. If the process is so spread out (e.g. the reachability has a wide distribution), it might not give a correct result.


Rationale:

How did I calcuate the probabilities?

In the probabilistic situation, each action doesn't occur at once. It is "spreading" over several days like clouds.

Consider the following:

  1. Person1 sends Msg1 to Person2. (it may take 2 days)
  2. After receiving Msg1, Person2 sends Msg2 to Person1.
  3. Both use the same postoffice.

Person:12
day=0send m1
day=1recv m1 & send m2 (50%)
day=2recv m2 (25%) recv m1 & send m2 (50%) - (Can we expect we can get both 2 and 1 with 0.25*0.50 = 12.5% ? - NO)
day=3recv m2 (50%)
day=4recv m2 (25%)
day=5

But you cannot get both Message 1 and 2 at once. Becasue these two event are exclusive (not independent).

To capture this, I firstnumbered each action and then constructed the "execution order graph":

  1. A1: Person1 sends Msg1 to Person2.
  2. A2: Person2 sends Msg2 to Person1.
  3. A1 precedes A2.

Then I looked at every cell, and cluster every action which is preceding any action within the same cell (which means the date and location).

At the postoffice A:

Person:12
day=0m1
day=1m1 by A1 (50%)
day=2m2 by A2 (25%) ||m1 by A1 (50%) - (You can expect only either case.)
day=3m2 by A2 (50%)
day=4m2 by A2 (25%)
day=5

But you can add the probability originating the same action, because if the spy sits at the same place for three days it eventually gets the message:

At the postoffice A:

Person:12
day=0m1
day=1m1 by A1 (50%)
day=2m2 by A2 (25%) v  m1 by A1 (50%) - (You can expect only either case.)
day=3m2 by A2 (50%)v
day=4m2 by A2 (25%)v___100%
day=5

Now suppose that third person were sending Message 2 at the same time (for some reason he already had that message):

At the postoffice A:

Person:132
day=0m1
day=1m2 by A3 (50%) m1 by A1 (50%)
day=2m2 by A2 (25%) + m2 by A3 (50%) = 62.5% ||m1 by A1 (50%) - (now A2 and A3 can be in the same cluster.)
day=3m2 by A2 (50%)
day=4m2 by A2 (25%)
day=5

Because there is not sequential guarantee between A2 and A3, we can conclude these two are independent.

Then we can combine the two probabilities (25% and 50%) as in:

the probability of getting message by either action = 1 - Π (1 - pi)

Choosing the best cells

In the simulated annealing, I tried to find a cell which subsumes other cells:

Person:12
day=0m1
day=1m1 by A1 (50%)
day=21:m2 by A2 (62.5%) ||m1 by A1 (50%) - (You can expect only either case.)
day=32:m2 by A2 (50%)
day=43:m2 by A2 (25%)
day=5

These cells form a cluster. Now each step of simulated annealing is to find the best combination of the clusters.


Yusuke Shinyama