10
$\begingroup$

Here is the problem:

There are connected graph with nodes representing a number of people. Each node/person has an opinion on a topic e.g. trump vs clinton, paper books vs kindle, etc

The goal is make every node in a graph share the same opinion, by selecting a specific subset of nodes, in a particular sequence.

If majority of a person A's friends support trump, but person A supports clinton. if person A is selected, his/her opinion will change to trump.

If person's friends opinions are equally divided, then you can decided the selected person's opinion.

I am running out of ideas as how to proof this is achievable. Maybe some of you can give me some pointers.

$\endgroup$
  • $\begingroup$ This is an interesting problem but I don't know if assigning people an opinion is a good idea. $\endgroup$ – Devsman Nov 23 '16 at 13:32
  • $\begingroup$ Sounds similar to the dynamics you find in Risk $\endgroup$ – maxwell Nov 23 '16 at 18:00
17
$\begingroup$

This is known as majority dynamics. Usually the assumption is that all nodes adopt the majority opinion simultaneously, and this is known as the synchronous model. For an arbitrary tie-breaking rule, this converges either to a fixed point or to a cycle of length 2; see for example pages 5-6 of Ginosar and Holzman's The majority action on in nite graphs: strings and puppets. If you break ties in a biased way, then the dynamic probably always converges.

What you describe is the asynchronous model, in which the majority rule is applied in sequence rather than in parallel. In that case the process always converges. See for example Tamuz and Tesler, though their methods are probably overkill for you, since in your case you get to choose the sequence, whereas in their case the sequence is chosen at random.

| cite | improve this answer | |
$\endgroup$
6
$\begingroup$

This is not generally achievable. Consider a blue and a red triangle connected with a single edge. Whatever node you select will keep its previous colour.

In general, if you have large monochromatic clusters with few connections between them, the graph is stable.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This seems like it should be the accepted answer, unless I'm misunderstanding something. $\endgroup$ – tmakino Oct 25 '17 at 18:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.