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.
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:
All are invited to submit solutions and prospective upstart-style puzzles for future columns to firstname.lastname@example.org
The Digital Library is published by the Association for Computing Machinery. Copyright © 2015 ACM, Inc.
No entries found