Conventions are powerful because they allow for coordination without communication.

Consider a game with 2 agents, and . Each agent can either take the action left or right, or . 1 Joint actions are tuples of ’s action and ’s action. For example, if goes left and goes right, then the joint action is . Also suppose that and are fully cooperative; they get the same reward. They get a reward of 0 if or occurs and a reward of 5 if or occurs.

Both agents know that the optimal joint policies are and . The hard part is coordination of which joint policy to follow, so they don’t end up both accidentally picking the same action.

One way to do this is for them to communicate. It’s like when you’re playing a sport and you yell, “Got it!”, so that your teammates know that you’ll get the ball and they can focus on other things. can say, “I’m going left!” and then knows it must go right. But communication is complicated. You could run into syncronization issues, have too much noise when sending messages, or it just might not be possible in certain applications.

A simple way to ensure coordination without any communication between the two agents is to pre-establish a convention beforehand. For example, if you already know what the optimal joint policies are beforehand, the absolute easiest thing to do is to just agree to following one optimal joint policy. i.e. “Hey agents, you’re going to do !”.

But generally you don’t even need to precommit to a specific policy, instead you can just precommit to a method for picking which optimal joint policy to execute. For example, you can simply agree that all agents will sort the optimal policies in lexicographic order and then pick the first one to follow. This really only requires two things (1) an order on the agents and (2) an order on the actions.

This contrast between communication vs conventions to solve coordination problems came up again today when I was making a quick fix to BookNLP. BookNLP is an NLP pipeline for literature and there is a part where the list of characters extracted from a story is being finalized. Now characters in a story can be referenced by multiple names, but you still only want to add each character once. I.e. Joe and Mr. Joe Garger are actually just the same person and we don’t want to double-count him.

One part of how this is ensured is by first only picking the longest name for each character (a convention!). For each name, , let be the set that contains split on whitespace. E.g. if , then . Now for every name , if there is a name such that and , then was flagged as a name to not be added.

Code below:

// Filter names that are subsets of others
for (String name : characterHash) {

    boolean flag = false;
    // break out all components of the name (Mr. Joe Gargery)
    Set<String> nameSet = new HashSet<String>(Arrays.asList(name
            .split(" ")));
    for (String name2 : characterHash) {

        Set<String> name2Set = new HashSet<String>(Arrays.asList(name2
                .split(" ")));

        // if one character's name is a complete subset of another's,
        // don't add it (e.g., Joe > Mr. Joe Gargery)
        if (!name.equals(name2) && name2Set.containsAll(nameSet)) {
            flag = true;
            continue;
        }
    }

    if (!flag) {
        BookCharacter character = new BookCharacter(name, id);
        finalNames.add(character);
        id++;
    }
}

But the problem with the way this was written is that if a character was mentioned both as “Sakura Kinomoto” and “Kinomoto Sakura”, then she wouldn’t get added at all!

We wouldn't want that would
we?

This is because , so both sets are subsets of each other and both names would get flagged. Alright, so the way to fix this is to check for when the sets are equal and only flag one of them. One way to do this would be to flag if and has already been added to the final list of names. Another way is to use a convention! Just pick the name that is first in lexicographic order to add.

Anyways, this is all nice and quaint, but the real question is where do conventions come from? There are a lot of people studying this and I think it’s super interesting.


  1. This example is taken from Boutilier, Craig “Planning, Learning and Coordination in Multiagent Decision Processes”. Theoretical Aspects of Rationality and Knowledge, 1996.