Topological sorting | Antimatroid, The

Posts Tagged ‘Topological sorting’

Multi-agent ordering

Given a set of agents $A = \{ a_{0}, a_{1}, \dotsc, a_{n} \}$ and a set of entities $V = \{ v_{0}, v_{1}, \dotsc, v_{m} \}$ , agents independently provide preferences $I_a \colon V^{2} \to \{ -1, 0, +1\}$ between different pairs of entities for a subset $S_{a}$ of the possible $E = V^{2}$ pairs. From these preferences, we wish to form a poset that contains the entities in order of least preferred to most preferred.

An agent may prefer an individual pair $e_{i,j}$ in the following ways: $-1$ , the agent prefers $v_{j}$ to $v_{i}$ ; $0$ , the agent is indifferent; $+1$ , the agent prefers $v_{i}$ to $v_{j}$ . Let $G_{a} = (V, S_{a})$ be the undirected graph that represents the preferences of an individual agent.

To form a consensus we are interested in $G= \sum_{a \in A} G_{a}$ . Let the adjacency matrix $M$ represent $G$ . In doing so, we may define $M$ in the following way: $M_{i,j} = \sum_{a \in A} I_a (e_{i,j})$ . It should be evident that $M_{i,i} = 0$ and $M_{i,j} = -M_{j,i}$ . We wish to simplify $M$ by turning it into a directed graph whereby all negative entries are removed. We shall define $N_{i,j} = \max{(0, M_{i,j})}$ to be this directed graph.

Let $deg_{j}^{in} = \sum_{i = 0}^{m} N_{i, j}$ be the sum of weights into vertex $v_{j}$ , $deg_{i}^{out} = \sum_{j = 0}^{m} N_{i,j}$ be the sum of weights out of vertex $v_{i}$ and $\delta_i = (deg_{i}^{in}, deg_{i}^{out})$ be the set of tuples for each vertex in $V$ . Thus, let $\delta$ along with the relation: increasing first element, then by decreasing second element be the poset $P$ of entities order from least preferred to most preferred.

Consider the following example: on a merchant’s website, customers $A = \{a,b,c,d,e,f\}$ independently provide comparisons between products that the merchant sells. The merchant wishes to know his customers’ preferences about his products $V = \{1,2,3,4,5,6\}$ .

Customers have provided the following set of preferences:

multi_agent_preferences

The consensus graph is produced from these preferences, followed by the directed graph until $\delta = \begin{pmatrix} (1,4) & (4,3) & (2,0) & (1,4) & (0,2) & (4,0) \end{pmatrix}$ is computed, which, when used to form $P$ , will yield $P = \{6,2,3,1,4,5\}$ . The merchant can infer from this analysis that customers least preferred product is 6, and most preferred product is 5.

Now, this model assumes that the agents are being truthful in their preferences. It is conceivable that a consortium of agents could force an entity to become the least or most preferred entity by providing false preferences. This premise presents two questions: how do we identity fallacious behavior, and two: how do we prevent it. The answer to the later of these two questions is simple: we add an additional term $\tau_a \in [0,1]$ when constructing $M_{i,j} = \sum_{a \in A} (1 - \tau_a) I_a (e_{i,j})$ where $0$ indicates that the agent provides factual preferences and $1$ indicates non factual preferences. The prior of these two questions is more involved and ties into calculating $\tau_a$ .

Lets consider two plausible hypotheses: a single agent tells the truth $\phi_{a}$ or he does not tell the truth about a single comparison $e$ . An agent is telling the truth about a single comparison if his preference $I_{a}(e)$ is identical to the majority preference $\sum_{a \in A} I_{a}(e)$ . An agent is not telling the truth if his preference is not identical to the majority preference. Let $\phi_{a}(e) = 1$ when $I_{a}(e)\sum_{\alpha \in A} I_{\alpha}(e) < 0$ , $0$ otherwise formalize this membership. Thus, we may define $\displaystyle \tau_{a} = \frac{\sum_{e \in S_{a}} \phi_{a}(e)}{ \lvert S_{a} \rvert }$ as the probability that a’s comparisons are majority comparisons.

This formalization assumes that there is an objective comparison and naturally, this formalization would not hold for subjective comparisons.

Consider the following example: seven robots are asked to order a collection of five blocks from smallest to largest and the result is an incorrectly ordered list. We wish to identify the defective robot(s), remove their preferences and reproduce the corrected list. The following table summarizes each robot’s preferences starting from the top left to right then down to the bottom left to right.

Going through the process above we arrive at an order of $\{0, 1, 3, 2, 4\}$ which is incorrect, thus we look at what our values are for this first iteration: $\tau_{a}^{(0)} = \begin{pmatrix}0 & 0.25 & 0 & 0 & 0 & 0.\overline{1} & 0\end{pmatrix}$ . Robots $a_{1}, a_{5}$ are more likely than their piers to deviate from the established majority. So, applying these values, we continue to perform this process iteratively until we arrive at $\{0,1,2,3,4\}$ using values of $\tau_{a}^{(2)} = \begin{pmatrix}0 & 0.41\overline{6} & 0 & 0 & 0 & 0.\overline{2} & 0 \end{pmatrix}$ . This process can be visualized the iterations of $N$ below. Edge weights represent the consensus. Thicker lines for the majority, thinner for the minority.

While not previously alluded to, it is possible that it may take several iterations to achieve a correct ordering. Which raises a couple questions: under what conditions will the correct ordering exist, how many iterations will it take to reach the correct ordering and are the number of iterations finite. The last one is left to the reader.

As a thought experiment, it is evident that there has to be at least $m - 1$ preferences for a correct ordering to be produced. Starting at any one vertex, there exists a path to every other vertex, otherwise a consensus cannot be achieved because $G$ could be decomposed into a set of disjoint subgraphs and no ordering is possible.

If there is an objective order $P^{\star}$ , it is still possible to arrive at a separate order $P^{\prime}$ that is produced after successive iterations if the majority preferences are all incorrect with respect to $P^{\star}$ . Thus, we cannot guarantee that the process will converge. If the preferences are correct with respect to $P^{\star}$ , then convergence will be achieved as the weight of dissenting agent’s preferences tends towards zero.

Written by lewellen

2010-01-01 at 8:00 am

Posted in Graph Theory

Tagged with Topological sorting

Antimatroid, The

Posts Tagged ‘Topological sorting’

Multi-agent ordering

Pages

Follow by Email

Follow by RSS

Categories

Archives

Meta