Consensus Strategies for Signed Profiles on Graphs
Presented by Dr. Manoj CHANGAT
Type: Oral presentation
Track: Metric Graph Theory
The majority strategy for a set of clients on a connected graph can be described as follows: if we are at vertex $v$, then we move to neighbor $w$ of $v$ if a majority of the clients is closer to $w$ than to $v$. Following the majority strategy by Mulder [Discrete Applied Math. 80 (1997), 97–105], plurality strategy for clients were proposed in [ K..Balakrishnan, M.Changat and H.M.Mulder, Plurality strategy in graphs, Austra. J. Combin. 46 (2010), 191--202]. This strategy is used as a method for finding the median in the sense of a consensus location for a desirable facility which minimize the sum of the distances to the location of the clients and hence this strategy is known as a consensus strategy. By associating signs +1 or -1 for clients both desirable and undesirable facilities can be simultaneously considered. In this paper, we extend the plurality strategy applied on profiles to signed profiles and use these strategies for locating both desirable and undesirable facilities (antimedians). We prove that for signed profiles, the plurality strategy will produce medians and the opposite strategy known as scarcity strategy will produce antimedians for every signed profile if and only if the graphs have both connected medians and antimedians. We prove a similar result for the Hill Climbing( Descent) strategy and for the Steepest Ascent Hill Climbing ( Steepest Descent) strategy. Nice examples of graphs which have both connected medians and antimedians are also presented.