We’ve just released a new version of FADecider (0.3 -> 0.4), see Projects.

We have added a multi-layer caching system that increases the speed and reduces the memory footprint when solving more complicated instances. Also, we have added support for pending calls and returns.

Let us know what you think.

So as expected the spammer answered me (see part 1). This scam is hilarious. Here’s the spammers mail:

Sehr geehrter Herr Habicht,

Hiermit möchte ich mich Ihnen gerne vorstellen. Ich bin Fachanwältin und Spezialistin in Sachen Erbrecht und arbeite für eine große Anwaltskanzlei in Großbritannien. Unsere Schwerpunkte sind Familienrecht, Strafrecht sowie Erbrecht. Herr Arendt hat mich gebeten mich mit Ihnen in Kontakt zu setzen und alle notwendigen Schritte zu Ihrem Fall durchzugehen.
Da Herrn Arendt die deutsche Sprache nicht leicht fällt, hat er mich in Ihren Fall eingeweiht und mich gebeten zu übernehmen. Natürlich nur mit Ihrem Einverständnis.
Gerne werde ich auf alle Ihre Fragen und Anliegen eingehen und mit Ihnen das Prozedere durchgehen.
Meine Kontaktdaten lauten wie folgt:-

Jenna Smith
Mobile:- (removed)

Ich bin durch Gerichtstermine ziemlich angebunden. Sie erreichen mich jedoch täglich von 9.30 Uhr bis 11.00 Uhr und von 12.00 Uhr bis 14.00 Uhr Ihrer Zeit.
Gerne können Sie mir auch Ihre Rufnummer zukommen lassen unter der ich Sie am besten erreichen kann und ich werde mich kurzfristig bei Ihnen melden.

Mit freundlichen Grüßen
Jenna Smith

And I’ve replied:

Sehr geehrte Frau Smith,

ich danke Ihnen sehr für Ihre Antwort.

Erlauben Sie mir eine kurze Erläuterung zu Herrn Arendt, die Ihnen Ihre Zusammenarbeit mit Herrn Arendt erleichtern wird. Seit einiger Zeit möchte Herr Arendt als Frau gesehen werden. Natürlich würde eine zurückhaltende Person wie Herr Arendt Sie niemals direkt darauf hinweisen, aber wenn Sie zwischen den Zeilen lesen, werden Sie bemerken, was ich meine. Dies nur als kleine Information unter uns Pfarrerstöchtern.

Ich danke Ihnen auch für Ihre Kontaktdaten. Leider kann ich Sie nicht telefonisch erreichen, da ich von Geburt an taubstumm bin. Ich habe über viele Jahre hinweg versucht mit den besten Logopäden zusammen ein wenig sprechen zu lernen, aber meine Freunde sagen, ich könnte allenfalls in Zombiefilmen als Synchronsprecher arbeiten. Das ist betrüblich, aber so ist eben das Leben.

Es würde zunächst genügen, wenn Sie mir den Totenschein und den Kontoauszug des Verstorbenen per E-Mail zukommen liessen.

Hochachtungsvoll
Alexander Habicht

Here is the Google translation of the spammer’s mail:

Dear Mr. Habicht,

Hereby I would like to introduce myself. I am a trade lawyer and specialist in the field of inheritance and work for a large law firm in the UK. We focus on family law, criminal law and inheritance law. Mr. Arendt asked me to sit in contact with you and go through all the steps necessary to your case.
As Mr. Arendt, the German language is not easy, he initiated me into your case and asked me to take over. Of course, with your consent.
I will be happy to respond to all your questions and concerns and to walk you through the procedure.
My contact details are as follows: –

Jenna Smith
Mobile: – (removed)

I’m pretty tied up by court dates. You can reach me but daily from 9.30 bis 11.00 clock clock and from 12.00 bis 14.00 clock clock your time.
Feel free to send me your number and let where I can best reach you and I’ll be in touch with you shortly.

Sincerely yours
Jenna Smith

Dear Ms. Smith,

Allow me a brief explanation of Mr. Arendt, who will facilitate your working with Mr. Arendt. For some time, Mr. Arendt wants to be seen as a woman. Of course, a cautious person like Mr. Arendt would never direct your attention to this, but if you read between the lines, you’ll see what I mean. This pastor daughters just as little information with us.

I also thank you for your contact. Unfortunately, I can not reach you by phone, because I’m deaf and dumb from birth. I have for many years tried to learn with the best speech therapists together to talk a little bit, but my friends say I could possibly work as a voice actor in zombie movies. That is sad, but so is just life.

It would be enough at first, if you send me them extensive death certificate of the deceased and the account statement by e-mail.

Yours faithfully
Alexander Habicht

# Answering Spam and Translating Text

I am sure all of you are exposed to spam on a daily basis – and one of the first lessons you have learned is that you never ever (ever!) answer any spam mails. Most spam mails are so dumb that it is almost impossible to believe that there is even one human being stupid enough to fall for it. One of my favorite spam mails of this kind reached Horst Prillinger a couple of month ago.

One spam mail that popped up in by inbox today was so bizarre that I felt inclined to answer (using a separate email account, of course). It’ll be interesting to see if I’ll get any replies. I’ve changed the author’s name of the original spam mail (although it is definitely a fake name) as well as the name I’ve used to answer it so you can enjoy them here. The catch is that the email conversation is in German. However – since this is a fun post – I’ve used Google Translate to get an English pseudo-translation of it which is quite entertaining in its own right.

Here is the spam email I’ve received:

Hallo,

Ich möchte mich erstmal gerne vorstellen. Mein Name ist Herr Ferdinand Arendt, die persönliche Rechtsanwältin meines verstorbenen Mandanten war als privater Geschäftsmann im internationalen Bereich tätig.

Im Jahr 2009 erlag mein Mandant an einen schweren Autounfall. Mein Mandant war ledig und kinderlos. Er hinterließ ein Vermögen in Wert von $9.255.000 (Neun Millionen Zwei Hundert Fünfundfünzig Tausend amerikanischen Dollars). Die sich in Obhut der zuständingen Bank befindet. Die Bank ließ mir zukommen dass ich einen Erbberechtigen, Begünstigten vorstellen muss. Nach mehreren Recherchen erhielt ich keine weiteren hilfreichen Informationen, über die Verwandten meines verstorbenen Mandanten. Aus diesem Grund schrieb ich Sie an, da Sie den gleichen Nachnamen verfügen. Ich benötige Ihre Zustimmung und Ihre Kooperation um Sie als den Begünstigten vorzustellen. Alle meine Bemühungen Verwandte meines verstorbenen Mandanten waren erfolglos. Infolgedessen würde ich vorgeschlagen das Vermögen aufzuteilen, Sie erhalten 25% Prozent des Anteils und 60% Prozent würden mir dann zustehen. 10% Prozent werden an Gemeinnützige Organisationen gespendet, während 5% Prozent beiseite gesetzt werden für Umkosten, Aufwandsentschädigung im Internationalen Bereich. Alle notwendige Dokumente beinhalten sinngemäß auch das Ursprungzeugnis, um demnach Fragen von der zuständigen Bank zu vermeiden. Die beantragten Dokumente Sind legal und begläubigt, die Sie für das Verfahren benötigen. Das Vermögen enthält kein kriminellen Ursprung. Das Verfahren wird einwandfrei ohne Komplikationen erfolgen, die Geldüberweisung wird rechtsgemäß abgeschlossen. Alles was ich von Ihnen benötige ist Ihr Vertrauen und eine gute Zusammenarbeit. Bitte kontaktieren Sie mich bei der privaten E-Mail Adresse. Die vorgeschlagene Transaktion legal ist, appelliert, die Sie schützen wird legal. Mit freundlichen Grüßen Herr Ferdinand Arendt And here is my reply: Sehr geehrte Herr Arendt, vielen Dank für Ihre E-Mail. Ich hoffe es stört Sie nicht, dass ich Sie auf Ihrer privaten E-Mail-Adresse kontaktiere, aber da Sie mich darum baten, denke ich, dass das ausnahmsweise schon in Ordnung gehen wird. Zunächst möchte ich Sie herzlich um Verzeihung bitten. Sie stellen sich als Herr Arendt vor, weisen aber gleich darauf hin, dass Sie als Rechtsanwältin betitelt werden möchten. Ich vermute daher, dass Ihr Name tatsächlich männlichen Ursprungs, Ihre persönliche Geschlechtswahrnehmung aber weiblich ist. Ich werde Sie daher ebenfalls in der weiblichen Form ansprechen, ich hoffe, das ist in Ihrem Sinne. Es freut mich sehr, dass Sie mich aufgrund meines seltenen Nachnamens als Erbberechtigten vorgeschlagen haben. Als alleiniger Erbberechtigter bestürzt es mich allerdings zu hören, wie Sie gedenken, das Erbe Ihres Mandaten aufzuteilen. Natürlich müssen Sie für Ihre Arbeit entlohnt werden. Aber Sie müssen selbst einräumen, dass 60% des Erbes doch ein wenig zu viel des Guten sind. Mit anderen Worten: Sittenwidrig. Mein Vorschlag wäre daher, dass sich Ihre Entlohnung an Ihrem Stundensatz ausrichtet. Sie können da ruhig großzügig sein und auch angefangene Stunden als volle Stunden zählen. Ich bin nicht kleinlich. Auch wüsste ich gerne warum 10% an gemeinnützige Organisationen gespendet werden. Ist das testamentarisch so festgelegt? Worum handelt es sich bei Aufwandsentschädigungen im internationalen Bereich? Sie schreiben, dass Sie von mir Vertrauen und gute Zusammenarbeit benötigen. Das lässt sich durchaus einrichten. Um Ihnen weiteres Vertrauen schenken zu können, lassen Sie mir doch bitte zunächst folgende Unterlagen per E-Mail zukommen: – Testament falls vorhanden – Totenschein – Kontoauszug des Verstorbenen – Aufstellung der Unkosten und der Aufwandsentschädigungen – Vorschläge welche gemeinnützungen Organisationen mit den 10% bedacht werden sollen – Kostenvoranschlag für Ihre Arbeitszeit Herzlichen Dank und auf gute Zusammenarbeit, Ihr Alexander Habicht Here is the spam email I’ve received after Google Translate: Hello, I would like to first introduce myself. My name is Mr. Ferdinand Arendt, the personal lawyer of my late client was working as a private businessman in the international arena. In 2009, my client died in a car accident. My client was single and childless. He left a fortune in value of$ 9,255,000 (nine million two hundred and fifty-five one thousand American dollars). Which is in charge of the bank zuständingen. The bank sent me that I have to imagine a Erbberechtigen, beneficiaries.

After more research, I did not receive any helpful information about the relatives of my late client. This is why I wrote to you because you have the same last name. I need your consent and cooperation to present you as the beneficiary.

All my efforts were unsuccessful relatives of my late client. Consequently, I would propose to divide the assets, you get 25% percent of the share, and 60% percent said they would then I am entitled. 10% percent will be donated to charitable organizations, while 5% percent are set aside for reasonable expenses, allowances in the international area.

All necessary documents include mutatis mutandis, the certificate of origin, in order thus to avoid questions from the appropriate bank. The requested documents are legal and begläubigt you need for the procedure. The property does not contain a criminal origin. The process is properly carried out without complications, the money transfer will be completed in accordance with law. All I need from you is your trust and good cooperation.

Sincerely yours
Mr. Ferdinand Arendt

Dear Mr. Arendt,

Thank you for your email. I hope it does not bother you, I want you on your personal e-mail contact, but since you asked me for it, I think it is going exceptionally okay.

First, I would like to urge you to pardon. They introduce themselves as Mr. Arendt, but have the same then that you want to be titled as a lawyer. I suspect, therefore, that your name is actually male origin, your personal perception of gender is female, however. I will therefore also appeal to the female form, I hope it is in your best interests.

I am very pleased that you have suggested me because of my rare surname as heirs.

As sole Erbberechtigter it upset me but listen to how you intend to divide the inheritance of your mandates. Of course you have to be rewarded for your work. But you have to concede that 60% of the inheritance a little too much of a good thing yet. In other words, unethical. My suggestion would be that your remuneration aligns to your hourly rate. Can you be quiet spacious and include commenced hours as full hours. I’m not picky.

Also I would like to know why 10% will be donated to charitable organizations. Is the set testament that? What is it with allowances in the international arena?

You write that you need from me trust and cooperation. This can be set up perfectly. To give you further confidence can, let me please first send by e-mail to come:

– Testament, if any

– Death certificate

– Statement of the deceased

– Statement of expenses and allowances

– Proposals which gemeinnützungen organizations should be considered by the 10%

– Cost estimate for your work

Thank you and good cooperation,

Remember back in 2000 when the human genome was completely sequenced for the first time? Well, guess what, you can now get your own genome sequenced in three weeks. That might be a little exaggerated, but there are services that sequence parts of your DNA and test it for known diseases, known risks and other facts that you might want to know about. Or not. All it takes is a little bit of your spit.

Most critics say that you might not want to know about all your risks, particularly not about those that you can’t really manage. You’re at risk of having an aneurysm in your brain, but the preventive surgery is even riskier than just waiting and wishing? Would have been better if you hadn’t known about it in the first place, right?

Well, I can definitely see the critics’ point, but personally, I do want to know about all that. Even about the stuff that I can’t change. Call me a control-freak or whatever. But before you’re going to use such services, ask yourself if you really want to know that much about your biological setup.

Note that you should also take the results with a good grain of salt. The results are based on studies and correlation statistics. Many of the studies might be biased, flawed or just to small to make really decisive projections about your health. The service I was using always cited the study or the paper it was referring to, which might helps you to asses the legitimacy of the claimed results. And you should always remember that correlation that does not imply causation. I can’t repeat that sentence often enough.

I was using the service 23andme and it is quite astonishing what they’ve found out about my genome.

They start by telling you stuff that you already know. Guess that should make you feel comfortable that they’re really using your DNA and not just make wild random guesses. So according to them, I have brown eyes, slightly curly hair and I am able to taste bitter tastes. Yep, three of three points. Thumbs up.

They then tell you stuff that you might had always suspected but didn’t know for sure: I am likely lactose tolerant. Sounds about right, but I still don’t like cheese. And then “Subjects who drank coffee consumed a slightly higher amount of coffee per day, on average.” – right you are again! (although “slightly” is a very humble word to describe the amounts of coffee I drink per day)

Then there is also the bad stuff: “If a smoker, likely to smoke more”. I suppose I’m lucky that I’ve never started to smoke. Let’s get back quickly to the good stuff: strongly decreased likelihood of developing Alzheimer’s. I guess if I hadn’t forgotten what that was I could be happy about it…They also tell you an awful lot about your blood groups which might be helpful in case you need to get or give a blood transfusion in the future.

There are a couple of surveys that they encourage you to take once you’ve signed up for the service. They use their users’ answers to find new correlations with their users’ genomes, and some of their findings are already incorporated into the service. They found some genes, for instance, that are correlated with the photic sneeze reflex. They claim that I don’t have it, and they are right again.

Although hardcore quantified self services like 23andme are definitely not for everyone, I highly enjoyed using it. So how are your genes?

# Launch of Ziggeo

We have just launched Ziggeo in open beta, a service that allows interviewers to screen candidates by video before actually meeting them. Which should save interviewers a lot of time.

You can use the service for finding roommates, job candidates or even dates (if you’re so adventurous!). Check out our blog to get more ideas about what Ziggeo could be used for.

Since the service is in beta, we would love to hear your comments. Just go there, sign up (it’s free!), and try it out. You can either send us an email or use the Feedback button to let us know what you think.

# Scientific Sermon: Extracting Winning Strategies from Parity Game Winning Sets

[latexpage]
If you’ve read the last posts in the series, you might remember that solving a parity games means to determine the partition into winning sets for both players and to provide witnessing winning strategies on the sets.

In our today’s post, we’ll have a look at a polytime-equivalent variation. Assume that we have an algorithm $A$ that takes a parity game $G$ and computes the partition into winning sets without providing any witnessing winning strategies, i.e.
$(W_0,W_1) = A(G)$

The question is, can we easily (in the sense that the blow-up is only polynomial-time) create an algorithm $A’$ based on $A$ s.t. $A’$ additionally computes witnessing winning strategies? The answer is yes and the iterative algorithm is fairly easy:

$A'(G)$:
$(W_0,W_1) := A(G)$
$E' := \{(v,w) \in E \mid v \in (V_0 \cap W_0) \cup (V_1 \cap W_1)\}$
$F := E \setminus E'$
While there are two edges in $E'$ with the same source Do
$(v,w) :=$pick one of such edges in $E'$
$(W_0',W_1') := A(G|_{(E' \cup F) \setminus \{(v,w)\}})$
if $W_0 = W_0'$
$E' := E' \setminus \{(v,w)\}$
else
$E' := E' \setminus \{(v,u) \in E' \mid u \not= w\}$
return the trivial strategies in $G|_{E' \cup F}$ on the winning sets

The basic idea is to reduce the number of strategies for both players on their winning sets until only one strategy remains for each player while maintaining the invariant that after removing strategies there will still be winning strategies left.
We reduce the number of strategies by removing edges from nodes with more than one outgoing edge. Note that we only remove player 0 edges from nodes of the player 0 winning set and player 1 edges from nodes of the player 1 winning set.
Let $e$ be such an edge. Remove it from the game and solve it again using algorithm $A$. If the algorithm returns the same winning sets, we know that there is a winning strategy left for the controller of $e$ that doesn’t require $e$, so we can safely remove it for good. If the winning sets change after removing $e$, we know that $e$ is essential for the winning strategy, so we can remove all other edges except for $e$ emanating from that node.

As we can only remove edges linearly often, the blow-up of $A$ is linear.

In the next post of the series, we will consider a related problem: given a pair of (total) strategies for both players that are guaranteed to be winning on the respective winning sets (without being given the winning sets), can we determine the winning sets easily?

# Bookmarklet Gem for Ruby on Rails

I’ve just uploaded a Ruby Gem for creating bookmarklets. Have fun with it. A bookmarklet is a bookmark that loads remote content into the browser’s context of the currently viewed website. Services like Instapaper are based on bookmarklets.

# Applied Engineering: Modules, Functors and Maps

[latexpage]
In the last post of the series, we introduced the functional programming language OCaml and basic types like lists. We applied higher-order functions like map to them (recall that a higher-order function essentially is a function taking a function as an argument).

Recall that we’ve considered the list of people:

let people = [
(0, "Hank");
(1, "Karen");
(2, "Becka");
(3, "Mia");
(4, "Julian");
(5, "Trixi")
]

If we now want to look up the name of the person with id, let’s say, 4, we can only walk through the list until we find an entry that matches the respective number. This is a very inefficient algorithm for looking up data (its worst-case and average-case complexity are both linear). We can be much faster using a different data structure that stores all entries in order and applies binary search. The classic structure is a balanced tree and all database system rely on such organization of data. Luckily, OCaml already provides a module for handling such data. A module can be seen as a namespace for types and functions that belong together.

We will use the map module that allows to quickly look up a key and return a corresponding value – in our case, the keys would be the people’s ids and the values would be the people’s names. The map module is general enough to allow arbitrary keys and arbitrary values to be stored in a balanced tree.

If you think about that for a minute, you might see an issue here. In order to organize the data in the tree, you need to be able to compare keys with each other, so they can be arranged in the right order. But how would the map module compare stuff with each other if the map module doesn’t know how to compare certain types? Well, it doesn’t. We have to specify how our keys should be compared with each other.

How do we explain to the map module how our keys can be compared with each other? By parametrizing the map module by an auxiliary module that explains the key comparison. More precisely, we map the auxiliary module to a concrete map module by a functor (a mapping from a module to a module).

module IntMap = Map.Make(
struct
type t = int
let compare = compare
end
);;

On other words: we define the module IntMap to bethe  Map.Make-Functor applied to the auxiliary module with key type int (our people’s ids) and the comparator compare (OCaml provides a “magic” compare function for every type that we use here – for ints, it’s the natural ordering on integers).

Next, we want to convert our list of people to an IntMap, mapping ids to people’s names. In order to build and use the map, we need three IntMap-functions: one to create an initial empty IntMap-instance, one to add assignments to it and one to look up keys.

IntMap.empty: 'a IntMap.t
IntMap.add: int -> 'a -> 'a IntMap.t -> 'a IntMap.t
IntMap.find: int -> 'a IntMap.t -> 'a

Recall that ‘a is a type variable. In our case, the type variable corresponds to the value type – and since the map does not care about the specifics of this type, we don’t have to fix it via any auxiliary modules and functors.

The first function, IntMap.empty, simply returns an empty instance of an IntMap. The second function, IntMap.add, takes a key, a value and an existing IntMap as arguments and returns a new IntMap that added the new key-value assignment to the existing IntMap. The third function, IntMap.find, takes a key and an existing IntMap as arguments and returns the corresponding value (assuming that the key-value pair is present).

Our conversion function therefore looks as follows:

let int_list_to_map int_list =
let empty_map = IntMap.empty in
let rec helper rest_list acc_map =
match rest_list with
[] -> acc_map
|	(domain, range)::rest_list' ->
helper rest_list' (IntMap.add domain range acc_map)
in
helper int_list empty_map

The function starts with an empty map and then walks recursively through the last, adding the assignments one by one to the map. We can now use it to generate our people mapping and use it to look up people’s names:

let people_map = int_list_to_map people
let people_func p = IntMap.find p people_map

Recall that in our initial post, we had two more lists – the list of constraints (which person likes to sit next to which person) and the table configuration (which is seat is close to which set). Every entry in each of these lists is a triple – two ids and a value (how likable / how close).

let constraints = [
(0, 1, 1.0);
(0, 2, 1.0);
(0, 3, -0.5);
(0, 4, -1.0);
(1, 0, 0.75);
(1, 2, 1.0);
(1, 3, 0.5);
(1, 4, 0.5);
(1, 5, -0.75);
(2, 0, 0.5);
(2, 1, 0.5);
(2, 3, 0.75);
(2, 4, -0.75);
(3, 0, 1.0);
(3, 5, 0.5);
(4, 1, 0.5);
(5, 0, 1.0);
(5, 1, -0.5)
]

let table = [
(0, 1, 1.0);
(0, 4, 1.0);
(1, 0, 1.0);
(1, 4, 1.0);
(1, 2, 1.0);
(1, 5, 0.5);
(2, 3, 1.0);
(2, 1, 1.0);
(2, 5, 1.0);
(2, 4, 0.5);
(3, 2, 1.0);
(3, 5, 1.0);
(4, 0, 1.0);
(4, 1, 1.0);
(4, 5, 1.0);
(4, 2, 0.5);
(5, 3, 1.0);
(5, 4, 1.0);
(5, 3, 1.0);
(5, 1, 0.5)
]

We again want to convert both lists to maps, but in this case, the key consists of two ids, i.e. is an int product-type. We need to create a new module IntMap2 by mapping a new auxiliary module (that allows to compare key pairs with each other) to a map:

module Int2Map = Map.Make(
struct
type t = int * int
let compare = compare
end
)

let int2_list_to_map int2_list =
let empty_map = Int2Map.empty in
let rec helper rest_list acc_map =
match rest_list with
[] -> acc_map
|	(domain, domain2, range)::rest_list' ->
helper rest_list' (Int2Map.add (domain, domain2) range acc_map)
in
helper int2_list empty_map

let constraint_map = int2_list_to_map constraints

let table_map = int2_list_to_map table

We again want to define functions to look up the respective values by key pairs. There will be cases, however, in which certain key pairs don’t exist in the mappings. We didn’t specify, for instance, any constraints for the two seats 0 and 2 with respect to each other, because we implicitly assign them the proximity value 0. Similarly, this holds true for the constraints. We need to make sure, therefore, that our look up routines catch the exception in which no key pair could be found.

let constraint_func p q =
try
Int2Map.find (p, q) constraint_map
with
Not_found -> 0.0

let table_map = int2_list_to_map table

let table_func p q =
try
Int2Map.find (p, q) table_map
with
Not_found -> 0.0

We say here, try to execute the look up code provided by the Map module. If it raises the exception Not_found, return 0.

Next, we need to define a new type for handling dinner table assignments. It should be a map from a person’s id to a seat id – in other words an int IntMap.t. To play around with it, let us setup a test assignment that assigns each person the seat with the same id:

let test_assignment = int_list_to_map [(0,0); (1,1); (2,2); (3,3); (4,4); (5,5)]

So far, so good. To get a feeling of what’s going on, let us print the table assignment. We will make use of another higher-order function provided by the Map module that allows us to walk through the map:

IntMap.fold: (int -> 'a -> 'b -> 'b) -> 'a IntMap.t -> 'b -> 'b

This looks pretty complicated, so let’s check the details. The first argument is function that accepts a key and a value, and maps some data (of type ‘b) to updated data (of type ‘b again). The second argument is the map and third argument is some initial data (of type ‘b). Overall, the routine routines data of type ‘b. Internally, the function starts with initial data and the first key-value-pair and calls the user function to obtain an updated data object. It continues in that fashion with the second key-value-pair until all key-value-pairs have been handled. The final updated data object is then returned.

We will make us of it build a textual representation of dinner table assignments:

let format_assignment assignment =
IntMap.fold (fun person seat acc_format ->
acc_format ^
people_func person ^
" sits on seat #" ^
string_of_int seat ^ "\n"
) assignment ""

How does it work? It starts with the empty string “” and adds a line for every assignment pair in the user defined function. The current string is given by the accumulator variable acc_format. The output accumulator is built by concatenating (denoted by ^ in Ocaml) the accumulator variable with the person’s name and the seat number.

Applying that to our test assignment, we get the following output:

# print_string (format_assignment test_assignment);;
Hank sits on seat #0
Karen sits on seat #1
Becka sits on seat #2
Mia sits on seat #3
Julian sits on seat #4
Trixi sits on seat #5

We conclude the post by realizing the assignment value function of our initial post that allows us to rate a given dinner table assignment:
$\sum_{p,q \in People} constraint(p,q) \cdot proximity(assign(p), assign(q))$
We make extensive use of the fold operation again (which corresponds to the sum operation here):

let assignment_value assignment =
IntMap.fold (fun p _ acc_value ->
IntMap.fold (fun q _ acc_value' ->
acc_value' +. constraint_func p q *.
table_func (IntMap.find p assignment)
(IntMap.find q assignment)
) people_map acc_value
) people_map 0.0

For the record, the assignment value of our test assignment is 3.5. We should find an assignment that yields a higher value, right? We will see how to accomplish that in our final post in the series.

# Scientific Sermon: Parity Game Solving

[latexpage]
Last time, we saw how parity games look like and what their complexity theoretic status is – we can solve them by a non-deterministic polytime algorithm, but we don’t know how to do it in deterministic polytime.

In this post, we will see one of the most natural algorithms for solving parity games deterministically. Along the way, we will see why parity games are positionally determined, i.e. why every node is won by one of the two players by using a positional strategy, no matter how the opponent is playing. Recall that a general strategy is a plan that tells the player which outgoing edge to take from a node by taking the whole history of the play into account. Positional strategies, on the other hand, don’t care about the history of the play. In other words, no matter how the history looks like, a positional strategy will always choose the same outgoing edge from a node.

Before we get started, let us fix a mathematical formulation of parity games first. We say that $G=(V,V_0,V_1,E,\Omega)$ is a parity game if $(V,E)$ is a directed, total graph – i.e. the arena on which the game is based -, $V_0$ and $V_1$ are a partition of $V$ into the node sets of each player – if you recall the last post, the circular nodes belong to $V_0$ while the rectangular posts belong to $V_1$ -, and $\Omega: V \rightarrow \mathbb{N}$ is the priority assignment function that maps each node to a natural number, its priority.

The algorithm is based on the notion of attractors. Let $i=0,1$ be one of the two players. Given a set of nodes $U$, the $i$-attractor of $U$ is the least superset $A$ of $U$ such that player $i$ can force every play starting in a node $v \in A$ to visit a node $u \in U$. Intuitively, you can think of $U$ as a set of nodes beneficial to player $i$ and $A$ to be an extension in which every path, no matter what the other player is doing, leads to the set $U$.

Mathematically, the attractor $A$ is determined iteratively, starting with $A := U$. In every step, we include all nodes by player $i$ that have an edge leading directly to $A$. Obviously, player $i$ can force these nodes to visit $A$ and by induction to visit $U$. Also, we include all nodes by the other player that have all outgoing edges directed towards $A$. In other words, no matter what player $1-i$ is doing, he ends up in $A$ and by induction in $U$. This process is iterated until no new nodes have been added to $A$. It is immediate to see that the attractor computation can be done in deterministic polytime. Let $Attr_i(U)$ denote the $i$-attractor of $U$.

It should be easy to see that player $i$ can force a visit from $A$ to $U$ by a positional strategy.

The algorithm for solving parity games that we consider here is called the recursive algorithm for parity games. It is based on a recursive descent in the number of priorities. The base case is the empty game. Assume now that the game $G$ is not empty and let $p$ be the largest priority occurring. Let $i$ be the player “owning” the priority, i.e. $i = p \mod 2$. Let $U$ be the set of nodes with priority $p$. It is easy to see that every play that visits $U$ infinitely often is won by player $i$, because the largest priority occurring is $p$. So consider $U$ to be a “good” region for player $i$. We can even extend $U$ to a potentially larger good region by building the $i$-attractor $A = Attr_i(U)$. Every play that visits $A$ infinitely often is won by player $i$.

The question remains whether $i$ can enforce infinitely many visits to $A$. In order to answer that question, we consider the game $G’ = G \setminus A$ in which all $A$-nodes and $A$-edges have been removed. Note that the arena $G’$ is total again only due to the fact that $A$ is an attractor. By recursion, we solve $G’$ and obtain a partition into winning sets for both players $W_i’$ and $W_{1-i}’$.

There are two cases now. The easy one is $W_{1-i}’ = \emptyset$, i.e. player $1-i$ can’t win anything in the sub game G’. In that case, player $i$ wins from every node in $G$, because if player $1-i$ decides to visit $A$ infinitely often, player $i$ wins by forcing the visits to $U$, and if player $1-i$ decides to visit $A$ only finitely often, player $i$ wins by induction. It is easy to see by induction that this can be done with a positional strategy.

The other case is $W_{1-i}’ \not= \emptyset$. Here, we only we only know for sure that player $1-i$ can win on $W_{1-i}’$ as there is no player $i$ escape from $W_{1-i}’$ to $A$ (because $A$ is an attractor already). So what can we do now? We enlarge $W_{1-i}’$ again by computing the $1-i$-attractor $B = Attr_{1-i}(W_{1-i}’)$. It is immediate to see that player $1-i$ wins on $B$ with a positional strategy. We consider a second sub game $G” = G \setminus B$ and solve it recursively again. We obtain a partition into winning sets $W_i”$ and $W_{1-i}”$, which we can use to define the winning sets for $G$, i.e. $W_i := W_i”$ and $W_{1-i} := W_{1-i}” \cup B$.

I’ve updated the respective Wikipedia article as well where you can find a pseudocode outline of the algorithm.

The recursive algorithm is probably the most straight-forward algorithm for solving parity games. It can be easily seen that the algorithm is potentially exponential because of the two recursive descents and one can, in fact, provide a family of games on which the algorithm runs in exponential time. Interestingly, the algorithm is one of the fastest in practice. It also shows that all nodes of a parity game can be partitioned into the winning sets of both players and that they can win with a positional strategy on their respective winning sets.

The next post in this series will consider some interesting, seemingly simpler subclasses of parity games that would allow us to define a polytime algorithm for general parity games, given that we would have a polytime algorithm for one of the simpler classes.