DOI: 10.1145/2743036 Dennis Shasha
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/sha-sha/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.
All are invited to submit solutions and prospective upstart-style puzzles for future columns to upstartpuzzles@
Dennis Shasha ( firstname.lastname@example.org) is a professor
of computer science in the Computer Science Department
of the Courant Institute at New York University, New York,
as well as the chronicler of his good friend the omniheurist
Copyright held by author.
Publication rights licensed to ACM. $15.00
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
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 en-
tities, 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
The general upstart question is,
given a configuration of risk-ready en-
tities, no two of which have the same
wealth, how would you test for its sta-
bility? If unstable, devise a formula
or an algorithm to determine a stable
configuration that can be reached and
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
1. Assume there are three entities—
E1, E2, E3—with force 5, 4, 3 and wealth
Despite a tempting target, a stable outcome.
If E3 is eliminated,
then E2 will fall to E1;
if E1 is eliminated,
then E3 will fall to E2;
and if E2 is eliminated,
then E3 will fall to E1.
This configuration is stable,
even though E3 is such a