main page  
Lefebvre Polynomials and Their Applications Igor Borovikov, 

Abstract 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 socalled 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.
Because of the rule 3 reflexive polinomials can be always reduced to the form with only unit multipliers at all nonzero terms. That leads to the definition of Lefebvre polynomials as general expressions of the form
where a_{i} 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:
The following polynomials are examples of elements of Lefebvre algebra.


3 Awareness Operator  
If we drop terms a and b from
T+a+b+(T+b+a)a we will get a polynomial
In Q a scene T can be factored out:
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 twoagent 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 zerosum game (meaning when one wins,
the other looses equal value). VonNeumann's theory tells
that each player of zerosum game can guarantee himself a
certain value against any play of his opponent with the
socalled minimax strategy. A simple model of zerosum game can be represented with a payoff matrix. In a matrixbased 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
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:
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:
The new polynomial Q_{2}= T+(w+wb)a has a form similar to the original one Q_{1}. 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 closedloop 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 a_{i}. To
make them cooperate we need to establish some mutual
awareness of the agents. If every agent a_{i}
is aware of each other agent a_{j},
then we will get the awareness operator:
The total number of second order terms here is N^{2}, due to noncommutativity. 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 a_{i }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:
and contians only N secondorder 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]. 

References  
[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 