Communications of the ACM

Last byte

Upstart Puzzles: Strategic Friendship

By Dennis Shasha
Communications of the ACM, May 2015, Vol. 58 No. 5, Page 88
10.1145/2743036
Comments

Consider the following game (first posed to my close friend Dr. Ecco) played among several entities. Each entity Ei has a certain force Fi and a certain wealth Wi. A coalition of one or more entities has a combined force equal to the sum of the force of the individual entities. If a coalition C1 has a force that exceeds the force of a coalition C2, and C1 attacks C2, then C2 is eliminated, and the wealth of the entities making up C2 is distributed equally among the coalition members of C1, but the force of the coalition members in C1 does not change. Note every member of a coalition must agree to attack for an attack to take place. If the force of C1 is less than the force of C2, and C1 attacks C2, then C1 is eliminated. This will never happen, however, because we assume every entity wants to survive and increase its wealth. If the force of C1 is equal to the force of C2, then an attack has no effect.

Starter warm-up 1. Suppose there are only two entities—E1 and E2—and F1 > F2. What happens then?

Solution. E1 attacks E2 and takes its wealth; there is indeed no charity in this world.

1. Assume there are three entities—E1, E2, E3—with force 5, 4, 3 and wealth 10, 10, and 100, respectively. What then? See the figure here for a hint.
2. What would happen if there were three entities—E1, E2, E3—each with the same force, say, 2, but with wealth 1, 2, 3, respectively? How does wealth influence outcome?
3. What would happen if there were four entities—E1, E2, E3, E4—with force 5, 4, 3, 6 and wealth 10, 10, 12, and 20, respectively?

Stability among entities sometimes depends on wealth, as we have seen, but also on the willingness of an entity to take risk. Suppose there are four entities, each with force 1 and wealth 6. If, say, E1, E2, and E3 form a coalition to defeat E4, they divide E4's wealth equally, but then one of them will be the target of the other two, based on their self-interest. We say an entity E is "risk ready" if it is willing to agree to an attack that might later expose E to an attack. Otherwise, we say E is "risk averse."

The general upstart question is, given a configuration of risk-ready entities, no two of which have the same wealth, how would you test for its stability? If unstable, devise a formula or an algorithm to determine a stable configuration that can be reached and has the property that the survivors between them would gain as much wealth from the vanquished as possible. Demonstrate any properties—uniqueness, comparison of total force before and after—that strike you as interesting.

For clever reader solutions to this, as well as to other, upstart challenge, see http://cs.nyu.edu/cs/faculty/shasha/papers/cacmpuzzles.html

Solutions that show what happens in this strategically unforgiving world:

1. Nothing happens because E2 and E3 form a coalition; E1 never chooses to attack. E3 never allows that coalition to attack E1, because once E1 goes away, E3 loses to E2. Similarly, E2 never attacks E3 while E1 is still around, because without E3, E2 would lose to E1. This configuration is "stable."
2. Most likely, E1 and E2 would form a coalition to attack E3. When they do, the resulting configuration is stable.
3. There are several possibilities, because any three entities here would form a stable configuration, whereas no two entities are stable. But E4 is the most attractive target due to its wealth. Any two of E1, E2, and E3 could defeat E4, but most likely three are needed to defeat E4. Do you see why?
4. E3 would then form a coalition with E4 from the start, because if E4 would be vanquished, then E3 would definitely be next.

Back to Top

Back to Top

Back to Top

Back to top

The Digital Library is published by the Association for Computing Machinery. Copyright © 2015 ACM, Inc.

---

No entries found