main page

back to computer sicence
back to OSM

Lefebvre Polynomials and Their Applications

Igor Borovikov,
igor.borovikov@ g m a i l . c o m


In this discussion we introduce Lefebvre reflexive polynomials and explore their applications to minimax strategy and to the analysis of interaction complexity of sentient agents. Such analysis can be helpful in designing AI engine for computer games.

1 Introducion to Reflexive Polynomials

While studying reflexive behavior Vladimir Lefebvre [VL] developed an elegant algebraic notation, the so-called reflexive polynomials. Lefebvre reflexive polynomials can be of a big help in reasoning about mutual awareness of sentient agents.
Let’s assigns a symbol T to the scene where the agents’ interaction is happening. Suppose that there are only two agents in the scene - a and b The scene with two agents is naturally described as T+a+b. This is a presentation of the scene from the point of view of an external observer. For now the agents a and b are not aware of each other or of the scene. This is represented with a simple summation. A figure to the right illustrates awareness of objects.
If the agent a becomes aware of the scene T (but not of the agent b or itself), the polynomial describing such situation becomes T+a+b+Ta. If the agent a also becomes aware of the agent b in the scene, the polynomial changes to T+a+b+(T+b)a. An awareness of himself added on top of that gives a polynomial T+a+b+(T+b+a)a. Here is graphical representation of these situations.
More complex situations will become increasingly awkward to depict with nested images. The algebraic notation becomes indispensible for both representation and analisys of such situations.

2 Axioms of Lefebvre Algebra
Let's establish formal rules of the algebra of reflexive polynomials.
  1. Multiplication of reflexive polynomials is non-commutative.

    It's easy to see since "a from the point of view of b" is apparently not the same as "b from the point of view of a", so ab ba.

  2. Distributive property: we can "open brackets", e.g.: (T+b)a = Ta+ba. Due to non-commutative multiplication we need explicitely declare that we can do that on both sides - left and right. Thus

    We can intperpret brackets in (T+b)a as if "an agent a has a whole image of the scene T with b in it" in it. The right-hand side Ta+ba then corresponds to a having separate images of T and b. While sometimes this distinction is important, for most purposes we will ignore it, so the distributive rule (in both - left and right - versions) will be one of the axioms.

  3. Reduction rule: duplicate members can be eliminated, e.g. T+Ta+Ta=T+2Ta=T+Ta.

    An agent does not receive any new information by having second copy of his image of the scene or other agents.

Because of the rule 3 reflexive polinomials can be always reduced to the form with only unit multipliers at all non-zero terms. That leads to the definition of Lefebvre polynomials as general expressions of the form


where ai is a word in an the alphabet {a,b,...} with letters designating agents. The mutlipliers i take values in the binary set {0,1}. They obey the rules of Boolean algebra:

0+0=0, 0+1=1, 1+0=1, 1+1=1, 0*0=0, 0*1=0, 1*0=0, 1*1=1.

The following polynomials are examples of elements of Lefebvre algebra.

0, 1, T, a, 1+a, 1+ab, Ta, T+Ta+Tb+Tc, etc.

3 Awareness Operator
If we drop terms a and b from T+a+b+(T+b+a)a we will get a polynomial

Q = T+Ta+Tb+Taa.

In Q a scene T can be factored out:

Q = T(1+a+b+aa)=Tq.

We will call the polynomial q, which contains no scene symbol T, the awareness operator. Factoring out and eliminating the scene T allows to study mutual awareness of agents in a context independent of the particular scene. Thus awareness operator describes inherent, invariant properties of mutual awareness of agents.

Example 1. It is easy to see that a single act of awareness by agent a corresponds to the operator 1+a. Applying this operator to T we will obtain T+Ta, interpreted as "agent a is aware of the scene T".

Example 2. If two agents a and b are present and their awareness acts are performed consequently, one after another, then the awareness operator for such two-agent system is (1+a)(1+b). Applying this operator to scene gives T+Ta+Tb+Tab, interpreted as "both a and b are aware of the scene T and b is aware of a being aware of the scene."

An important remark. Instead of saying "b is aware of a being aware of the scene" we can say a bit more verbously that "b knows that a is aware of itself in the scene and b assumes that a has a model of the scene T". It is important to note that we don't make any assumptions on the "quality" or adequacy of such awareness or situational models created by the agents. Lefebvre polynomial only states that such awareness or model exists but does not say anything about its validity.

Example 3. When two agents perform act of awareness simulteniously the operator takes form 1+a+b.

4 Application: Awareness Model of Minimax Strategy
Suppose that agents a and b participate in a zero-sum game (meaning when one wins, the other looses equal value). Von-Neumann's theory tells that each player of zero-sum game can guarantee himself a certain value against any play of his opponent with the so-called minimax strategy.

A simple model of zero-sum game can be represented with a payoff matrix. In a matrix-based game player a chooses a row and player b chooses a column of the matirx. They make choices independently and anounce them simultenioulsy. The value of the selected matrix element is the value that one player wins and the other looses.

The minimax value of the game for player a is the minimum of what player a can achieve knowing the choice of player b. Even though players don't exchange information when making the choice, the minimax strategy of a player b is based on b assuming that a knows the choice of b. Lefebvre polynomial for minimax strategy is

Q1= T + (T+Tb)a

Here is the interpretation corresponding to the minimax strategy: player b is aware of the scene T (the part in the brackets: T+Tb) and his choice is transparent to player a. Or, whatever b thinks and knows (T+Tb) is evident to a: (T+Tb)a. The awareness operator for this polynomial is:

q= 1+a+ba

The main assumption is that b thinks that all his decisions and models are immediately available for the opponent, player a. The act of awareness of this situation that b can perform is again represented by the same operator q. It corresponds to the phrase "as soon as player b knows that player a is aware of all his plans, player a becomes immediately aware of this state of b". Applying operator q second time we will get polynomial:

= T(1+a+ab+ba+bab)a
= T(1+(a+ba)+ (a+ba)b)
where w = T(a+ba).

The new polynomial Q2= T+(w+wb)a has a form similar to the original one Q1. The difference is that the subject of the player b's vision now is not the scene T itself but T(a+ba) - "a sees the scene and b's vision of the scene".

It is easy to check that applying awareness operator any number of times would still keep the form of the reflexive polynomial invariant: T+(w'+w'b)a. Lefebvre calls this invariance reflexive closure. The closure describes impossiblity to get out of the closed-loop thinking "whatever I think, decide or know, will be immediately known to my opponent too". Each next awareness act doesn't break "he knows all my decisions" property.

5 Focal points
In the situation when agents a and b need to cooperate without communication the minimax operator 1+a+ba generates effect of the so called focal points.

Suppose that two agents need to meet each other on a map with several possible locations for meeting. Imagine that both have the same map with all locations but one colored white and a single locaton is colored black. The agents have no information about each other's initial location and can't communicate. Also they have no preference on picking location by distance, but each know that the other has the same map.

It is easy to see that minimax awareness operator provides a solution to the problem. The agent that uses minimax awareness operator thinks "I pick black because there is only one black location on the map. Since my partner can model my way of thinking he will know that I choose black location." Picking white location would give a probability of meeting less than 1 so without any additional information or preferences it wouldn't generate the same result as a unique black location.Black location in this situation is the focal point where sentient agents armed with minimax awareness will meet.

The same kind of logic suggests that search for radio transmittion from extraterrestrial intelligence should focus on wavelegnth 21 cm since it is special in many ways. The wavelength 21 cm is the focal point in our perception.

6 Estimating Complexity of Agents Cooperation
Let's consider a given number N of interacting agents ai. To make them cooperate we need to establish some mutual awareness of the agents. If every agent ai is aware of each other agent aj, then we will get the awareness operator:

1 + ij aiaj, i,j,=1,...,N

The total number of second order terms here is N2, due to non-commutativity. Thus in the case of uniform interaction personal intelligence of agents has to support complexity growing quadratically with the number of cooperating agents.

Now consider a situation with one agent A dedicated to organizing of the remaining agents. The remaining agents can only receive and execute impersonified commands and don't question either the authority of A and are not aware of its existance. Also agents ai know nothing about each other. To make all agents work together the agent A has to be aware of them all, but the responsibilities of the rest of the agents are reduced drastically. The awareness operator for such organization is represented by:

1 + i aiA, i=1,...,N

and contians only N second-order terms. This type of coperation is called hierarchical and is much simpler to implement in real life and software in comparison to "each agent knows each other agent" situation. The advantage of hierarchical control becames more significant with growth of the number of interacting agents. See also [IB].

[VL] Vladimir Lefebvre “Conflicting Structures”, Moscow, 1973, 158 pages. [In Russian]
[IB] Igor Borovikov "An Orwellian Approach to AI architecture", Game Developers Conference, 2005.

main page

back to computer sicence
back to OSM