=Paper=
{{Paper
|id=Vol-408/paper-13
|storemode=property
|title=Agents's competition for selecting a representative
|pdfUrl=https://ceur-ws.org/Vol-408/Poster1.pdf
|volume=Vol-408
|dblpUrl=https://dblp.org/rec/conf/lanmr/LunaTC08
}}
==Agents's competition for selecting a representative==
https://ceur-ws.org/Vol-408/Poster1.pdf
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.