Agents’s Competition for Selecting a Representative Guillermo De Ita, Mireya Tovar, Meliza Contreras Computer Sciences Faculty, Universidad Autónoma de Puebla {deita,mtovar,mcontreras}@cs.buap.mx 1 Introduction The selection of a representative is an important and common problem wherever it is necessary to choose candidates from political parties, for selecting a depart- ment’s boss, for selecting a supervisor, etc. In general, when it is necessary to select the best candidate from a group of people. One of the most common criteria for choosing representatives is for direct popular voting. In this case, the candidate who obtains the maximum number of supportive votes is chosen as the representative. This method works based on the popularity of the candidates. Working with intelligent agents has been reformulated the methods in the area of automatic reasoning [1]. In this research, we consider a set of deliberative agents who build a Knowledge Base (KB) Σ containing the beliefs of the agents about who can be the best representative among them. Each agent establishes a set of supportive and opposing constraints, agreeing on their beliefs about of the candidacy of any other agent. We apply procedures based on propositional logic in order to determine the candidate with minimum inconsistencies with the total system of beliefs of the agents. 2 Building the Knowledge Base of the Agents Let A = {A1 , A2 , . . . , An } be a set of n intelligent agents. An opposing constraint has a type: Ai → ¬(Aj ) (Wij ), indicating that the agent Ai believes that the agent Aj is not a good candidate, and Ai gives a weight of Wij as a punishment. In general, an opposing constraint always has a negative literal as a succedent. By other hand, the syntax for a supportive constraint, is: ¬(Ai ) → Aj (Wij ), indicating that the agent Ai believes that if he is not selected as candidate then the agent Aj could be a good candidate, and Ai gives a weight of Wij as support. And the constraint Ai → Aj (Wij ) means that the agent Ai believes that an appropiate companion to his candidacy is the agent Aj , giving a support of Wij . Then, a supportive constraint always has as succedent one positive literal. For any agent Ai ∈ A, the sum of its supportive weights cannot be exceed a bound B, and the same bound cannot be exceeded by the sum of its opposing weights. The bound B is common to all agents since the beliefs of one agent is as important as the beliefs of any other agent. The union of all beliefs of the agents of A builds the Knowledge Base Σ. Let v(Σ) = {A ∈ A : A appears in Σ} and Lit(Σ) is the set of literals in Σ. Let GΣ = (V, E) be the dependence graph generated by the constraints of Σ, V = Lit(Σ) and let E be the set of constraints given by the agents. Let ”⇒” be the reflexive and transitive closure of the implication: →, beginning over any literal of Σ. T (x) denotes the set of all literals y forced by x, ∀ x ∈ Lit(Σ), T (x) = {y ∈ Lit(Σ) : x ⇒ y}. We call T (x) the closure of x ∈ Lit(Σ). We say that T (l) is contradictory if ∃A ∈ A such that A ∈ T (l) and ¬A ∈ T (l), otherwise T (l) is consistent. If there is an agent A ∈ A such that both T (A) and T (¬A) are contradictory then Σ is unsatisfiable. If Σ is satisfiable then ∀A ∈ Lit(A) such that T (¬A) is contradictory we have that Σ ` A. After computing the transitive closure over all literals in A, we determine the following sets. Cont(Σ) = {l ∈ Lit(A) : T (l) is contradictory}. Note that for any literal l ∈ Cont(Σ), (Σ∪{(l)}) is unsatisfiable. Base(Σ) = {l ∈ Lit(A) : T (l) is consistent and T (¬l) is contradictory}. The set Base(Σ) determines the set of literals that appear in any model of Σ. For any literal l, such that l ∈ Base(Σ) then ¬(l) ∈ Cont(Σ), so Base(Σ) ∩ Any(Σ) = ∅. Let Any(Σ) = Lit(Σ) − (Base(Σ) ∪ Cont(Σ)), then ∀ l ∈ Any(Σ), l is a literal which could appear with anyone of the two logical values in some models of Σ. Then, {Cont(Σ), Base(Σ), Any(Σ)} is a partition of Lit(Σ). If Σ is satisfiable then for any model M of Σ we have Base(Σ) ⊆ M and if Any(Σ) 6= ∅ then Any(Σ) ∩ M 6= ∅. We also refer with ’Closure’ to the procedure that computes T (x) ∀ x ∈ Lit(Σ). Closure runs in polynomial time [3]. In fact, the complexity time is O(n · m) where n is the number of agents and m the number of constraints determined by the agents. After computing T (l) ∀l ∈ Lit(Σ), it is easy to obtain the sets: Base(Σ), Cont(Σ) and Any(Σ). Moreover, based on those sets, we determine if Σ is satisfiable or unsatisfiable. 3 Selecting a Representative Based on a Base of Beliefs The theoretical framework for processing Σ in order to find a candidate is by choosing the agent whose candidacy does not generate contradictions with the beliefs of the other agents. So in this model we prefer consistency in the candidacy of the agent over the popularity of the same agent. Let us illustrate the selection of candidates via a simple example. In a class- room there are four students who have obtained the maximum academic av- erage, but each one in a different subject. The students must select a single representative from the group. Each one of them establishes a set of supports and oppositions for the other ones. In our example, we represent the students by the letters: A = {A(Armando), B(Alberto), E(Erick), M (M ayra)}. The con- straints and their associated weights, given by the students, are: A −→ ¬M (33) A −→ ¬E (33) A −→ ¬B (33) B −→ ¬A (50) E −→ ¬A (80) M −→ ¬A (45) M −→ ¬E (35) ¬B −→ M (20) ¬B −→ E(20) ¬E −→ M (80) ¬M −→ B (50) The KB Σ is formed by those constraints. Let W (e) be the weight asso- ciated with any edge e in GΣ and let in edge(Y ) = {X −→ Y } be the set of input edges toPthe node Y of GΣ . The support for the candidacy of Ai , is: Support(Ai ) = e∈in edge(Ai ) W (e), and its opposition is: Opposition(Ai ) = P e∈in edge(¬Ai ) W (e). Then, the Popularity of the candidacy of Ai ∈ A, is: Suit(Ai ) = Support(Ai ) − Opposition(Ai ). And the closure sets, are: T (A) = {A, ¬M, ¬E, ¬B, B, M, E, ¬A} - Contradictory T (¬A) = {¬A} T (M ) = {M, ¬A, ¬E} T (¬M ) = {¬M, B, ¬A} T (E) = {E, ¬A} T (¬E) = {¬E, M, ¬A} T (B) = {B, ¬A} T (¬B) = {¬B, M, E, ¬A, ¬E} - Contradictory A model M of the KB Σ assigns a unique truth value to each agent variable. If Ai ∈ M , this means that its candidacy is not contradictory with the beliefs of the multi-agent system. If ¬Ai ∈ M , this means that the agents agree with the not candidacy of Ai . Then the positive literals appearing in all models of Σ represent the candidates which are consistent with the beliefs of the agents. We assign the name Base of candidates to the set of positive literals appearing in all models of Σ: Cand Base(Σ) = {Ai ∈ A : Ai ∈ Base(Σ)}. If we compute the ’Popularity’ for each agent Ai ∈ A, according to our example, we have: Support(A) = Σe∈in edges(A) W (e) = 0, Opposition(A) = Σe∈in edges(¬A) W (e) = 50 + 45 + 80 = 175 and Suit(A) = Support(A) − Opposition(A) = −175. Support(B) = 50, Opposition(B) = 33 and Suit(B) = 17. Support(E) = 20, Opposition(E) = 33 + 35 = 68 and Suit(E) = −48. Support(M ) = 20 + 80 = 100, Opposition(M ) = 33 and Suit(M ) = 67. The Closure procedure generates the following sets: Cont(Σ) = {A, ¬B}, Base(Σ) = {¬A, B} and Any(Σ) = {E, ¬E, M, ¬M }. This means that ’Alberto’ (B) appears in all models of Σ; therefore, he is the best candidate from the students. Notice that although ’Mayra’ is more popular than ’Alberto’, he is the unique positive member of Cand Base, meaning that his candidacy is always consistent with all the beliefs of the multi-agent system. Notice that our model for selecting candidates works in polynomial time complexity since it depends mainly on the Closure procedure. So our proposal for finding a representative is a polynomial time algorithm. References 1. Bigus J. P., Bigus J.: Constructing Intelligent Agents Using Java, Wiley Computer Pub., 2da. Edition, 2001. 2. Carmel D., Markovitch S.: Learning Models of Intelligent Agents, Proc. 13th Nat. Conf. on Artificial Intelligence and the Eighth Innovative Applications of Artificial Intelligence Conf., Vol. 2, AAAI Press, (1996), pp 62-67. 3. Gusfield, D., Pitt, L.: A Bounded Approximation for the Minimum Cost 2-Sat Problem. Algorithmica 8, (1992), pp. 103-117.