A STEAM Experience For A Flash Mob

1.0 Introduction

STEAM stands for Science, Technology, Engineering, Arts, and Mathematics. This post describes a possible plan for a crowd of many people to participate in. Roles for players consist of:

• A Recorder.
• State Actors.
• Holders of letters in a line.

I once read Terry Eagleton suggesting that part of the definition of art is that it be "somewhat pointless."

2.0 Equipment

Equipment to be provided consists of:

• A six-sided die.
• Two balls. They could be soccer balls, beach balls, volley balls, or so on. One ball is called the Head, and the other ball is called the State Pointer.
• Six sets of equipment, labelled 1 through 6. A set of equipment consists of:
• A set of cards, where each card is a "letter" from an alphabet. Letters can be, for example, "Blank", "(", ")", ";", "End", "0", and "1". Many letters must have many cards with that letter.
• A set of state placards. Each state placard contains:
• An arbitrary label. These labels are arbitrary, but not repeated. They could be in high elvish, for all it matters, as long as participants can pronounce each label.
• Either the word "Halt" or a set of rules. The placards for the halting states may also contain a short phrase. Each rule in a set of rules is designated by a letter from the alphabet.
• Guidelines for setting up. These guidelines include:
• Optional guidelines for the geographical distribution of states.
• A specification of which State Actor initially holds the State Pointer.
• Guidelines for forming an initial line of letters from the alphabet. These guidelines must include a specification of which holder of a letter initially also holds the Head.

3.0 Playing the Game

3.1 Preliminaries

The Recorder throws the die and chooses the corresponding set of equipment. One might create only one set of equipment, and this step would be omitted.

The Recorder distributes the state placards. A audience member comes up for each placard. He collects it, and becomes a State Actor. The State Actors all gather, with some distance between them, in a designated region. (One might break down the region into sub-regions, for subsets of the states, if one wants.)

The Recorder gives the State Pointer to the State Actor holding the placard for the initial state.

The Recorder reads out the guidelines for the initial line of letters. Audience members come up and form a line, accordingly. As an example, the guidelines might say:

The first player sits in the line and holds the "End" letter. The second player stands behind the first player. He holds a "Blank" and the Head. A number of players sit in the line behind the second player. They should each hold "0" or "1", as they choose. A person should sit after these players, and she holds a ";". Another number of players sit in in a row behind her. They also should each hold a "0" or "1".

The Recorder writes down the sequence of letters in the initial set up. This step is optional.

Play can now commence. Play consists of a sequence of clock cycles.

3.2 A Clock Cycle

The player holding the Head commences a clock cycle. This player calls out the letter he is holding.

The state actor holding the State Pointer now plays. He looks at his rules and finds the rule corresponding to the letter that has been called out. Each rule has two parts. The first part is either a letter from the alphabet or the word "Forward" or the word "Backward". The second part is the name of a state. That state could be the label on the state placard that this State Actor is holding. Or it could be another state.

If the State Actor calls out a letter, an audience member comes up. He selects that letter from leftover letters in the initial set of equipment. He replaces the player holding the Head in the line. And that player hands the new player the Head.

If the State Actor calls out Forward, the player holding the Head hands it to the player holding a letter in front of him and sits down. The player now holding the Head stands up. There would be no such player if the player holding the Head at the start of the cycle is standing at the front of the line. In this case, an audience member picks up a "Blank" from the leftover set of equipment. That player accepts the Head and stands at the front of the line.

If the State Actor calls out Backward, the player holding the Head hands it to the player holding a letter behind him and sits down. As you might expect, that player now holding the Head stands up. This step might also result in a new player coming up from the audience and joining the line. And this new player would join the line at the back.

The State Actor holding the State Pointer now calls out the state listed on the second part of the rule he is executing. If that state is not the state listed on his state placard, he hands the State Pointer to the appropriate State Actor.

The Recorder writes down the new state that the State Pointer has now transitioned to. (This step is optional.)

3.3 Ending the Game

The game ends either when the players become convinced it could go on forever, or it ends when a State Actor holding a placard for a halting state receives the State Pointer. If the game ends in a halting state, the State Actor reads the corresponding phrase from the state placard. That phrase might be something like:

You have been a Turing machine computing the sum of two non-negative integers, written in binary.

Or it could be:

You had at least one unmatched parentheses in your initial line.

If you want, the Recorder could have more audience members come up to recreate the initial line. You can then review, if you like, the computation. For example, you might check that the sum of the two numbers separated by a comma in the initial line up is equal to the number now represented by the final line up on the stage.

4.0 Much To Do

Obviously, much would need to be done to flesh this out. In particular, equipment sets need to be constructed. Some choices to think about:

• Would one want to include an equipment set in which the simulated Turing machine does not terminate for some initial line of letters? Or would one want to, at least for the first performance, only have rules that are guaranteed termination for all (valid?) inputs?
• Might one want to emulate automata for languages lower down on the Chomsky hierarchy? For example, one might create a stack to be pushed and popped before the start of the line. Here I envision that a subset of the states specify subroutines. And the State Actors defining these subroutines might be grouped separately from the other actors.
• Would one want to share alphabets among more than one equipment set? Maybe all six sets should have the same alphabet.
• How would one describe the initial line up for a Turing machine that is to decide or semi-decide whether a given string is in a given language? The specification of a grammar for generating a string can be quite confusing to beginners.
• I am thinking that one would not want to create rules for a universal Turing machine. Even some of the suggestions above might be too long to play.

An interesting variation would be to simulate a non-deterministic Turing machine. For some clock cycles, the line would be duplicated. And one would introduce another Head and State Pointer.

5.0 Instruction and Theatrics

This activity could serve pedagogical purposes. Suppose the players are different cohorts of students. Could the older students be directed to write the rules for some other computation at the next meeting? Could a set of recursive functions be built up over many meetings? Maybe one would end up with a group engaging in real-time debugging in a joint activity.

One could set up an accompanying talk or lecture. Many topics could be broached: The Church-Turing thesis and universality, uncomputable functions and the halting problem, computational complexity and the question of whether P equals NP, linguistics and the Chomsky hierarchy, etc. Or one might talk about the British secret service and reading the Nazi's mail. I guess there is both a Broadway play and a movie to go along with this activity.

One could introduce some sophistication in showmanship, depending on where this concept is instantiated. I like the idea of the alphabet players wearing different colored shirts, with each color corresponding to a character. Zero could be red, and one could be green. Blanks would be a neutral color, such as white. The State Actors could be in a dim area, with a spotlight serving as the State Pointer. The State Actors or the letter holders could be members of an orchestra, with some tune being played for every state transition or invoked rule. At termination, the entire derivation written down by the Recorder could be run-through. I imagine it would be difficult to design a set of rules that results in an interesting tune. At any rate, I guess the interests of an observing mathematician, the participants, and a theatergoer would be in tension.

I hope if somebody was to try this project, they would give me appropriate acknowledgement.

Reference

• Lou Fisher (1975). "Nobody Named Gallix", The Magazine of Fantasy and Science Fiction (Jan.): pp. 98-109.
• Andrew Hodges (1983). Alan Turing: The Enigma, Princeton University Press.
• HarryR. Lewis and Christos H. Papadimitriou (1998). Elements of the Theory of Computation, 2nd edition. Prentice Hall.

Math Is Power

1.0 Introduction

A common type of post in this blog is the presentation of concrete numerical examples in economics. Sometimes I present examples to illustrate some principle. But usually I try to find examples that are counter-intuitive or perverse, at least from the perspective of economics as mainstream economists often misteach it.

Voting games provide an arena where one can find surprising results in political science. I am thinking specifically of power indices. In this post, I try to explain two of the most widely used power indices by means of an example.

2.0 Me and My Aunt: A Voting Game

For purposes of exposition, I consider a specific game, called Me and My Aunt. There are four players in this version of the game, represented by elements of the set:

P = The set of players = {0, 1, 2, 3}

Out of respect, the first player gets two votes, while all other players get a vote each (Table 1). A coalition, S, is a set of players. That is, a coalition is a subset of P. A coalition passes a resolution if it has a majority of votes. Since there are four players, one of who has two votes, the total number of votes is five. So a majority, in this game of weighted voting, is three votes.

Table 1: Players and Their Votes

Players	Votes
0 (Aunt)	2
1 (Me)	1
2	1
3	1

One needs to specify the payoff to each coalition to complete the definition, in characteristic function form, of this game. The characteristic function, v(S) maps the set of all subsets of P to the set {0, 1}. If the players in S have three or more votes,v(S) is 1. Otherwise, it is 0. That is, a winning coalition gains a payoff of one to share among its members.

3.0 The Penrose-Banzhaf Power Index

Power for a player, in this mathematical approach, is the ability to be the decisive member of a coalition. If, for a large number of coalitions, you being in or out of a coalition determines whether or not that coalition can pass a resolution, you have a lot of power. Correspondingly, if the members of most coalitions do not care whether you join, because your presence has no influence on whether or not they can put their agenda into effect, you have little power.

The Penrose-Banzhaf power index is one (of many) attempts to quantify this idea. Table 2 lists all 16 coalitions for the voting game under consideration. (The number of coalitions is the sum of a row in Pascal's triangle.) The second column in Table 2 specifies the value for the characteristic function for that coalition. Equivalently, the third column notes which eight coalitions are winning coalitions, and which eight are losing. The last two columns are useful for tallying up counts needed for the Penrose-Banzhaf index.

Table 2: Calculations for Penrose-Banzhaf Power Index

Coalition	Characteristic Function	Winning or Losing	Player
			Aunt (0)	Me (1)
{}	v( {} ) = 0	Losing	0	0
{0}	v( {0} ) = 0	Losing	0	0
{1}	v( {1} ) = 0	Losing	0	0
{2}	v( {2} ) = 0	Losing	0	0
{3}	v( {3} ) = 0	Losing	0	0
{0, 1}	v( {0, 1} ) = 1	Winning	1	1
{0, 2}	v( {0, 2} ) = 1	Winning	1	0
{0, 3}	v( {0, 3} ) = 1	Winning	1	0
{1, 2}	v( {1, 2} ) = 0	Losing	0	0
{1, 3}	v( {1, 3} ) = 0	Losing	0	0
{2, 3}	v( {2, 3} ) = 0	Losing	0	0
{0, 1, 2}	v( {0, 1, 2} ) = 1	Winning	1	0
{0, 1, 3}	v( {0, 1, 3} ) = 1	Winning	1	0
{0, 2, 3}	v( {0, 2, 3} ) = 1	Winning	1	0
{1, 2, 3}	v( {1, 2, 3} ) = 1	Winning	0	1
{0, 1, 2, 3}	v( {0, 1, 2, 3} ) = 1	Winning	0	0

The Penrose-Banzhaf index, ψ(i) is calculated for each player i. It is defined, for a given player, to be the ratio of the number of winning coalitions in which that player is decisive to the total number of coalitions, winning or losing. A player is decisive for a coalition if:

• The coalition is a winning coalition.
• The removal of the player from the coalition converts it to a losing coalition.

From the table above, one can see that player 0 is decisive for six coalitions, while player 1 is decisive for only two coalitions. Hence, the Penrose-Banzhaf index for "my aunt" is:

ψ(0) = 6/16 = 3/8

By symmetry, the index values for players 2 and 3 are the same as the value for player 1:

ψ(1) = ψ(2) = ψ(3) = 2/16 = 1/8

More than one player can be decisive for a winning coalition. No need exists for the Penrose-Banzhaf index to sum up to one. How much one's vote is weighted does not bear a simple relationship to how much power one has. Also note that the definition of this power index is not confined to simple majority games. Power indices can be calculated for voting games in which a super-majority is required to pass a measure. For example, in the United States Senate, 60 senators are needed to end a filibuster.

4.0 The Shapley-Shubik Power Index

The Shapley-Shubik power index is an application of the calculation of the Shapley value to voting games. The Shapley value applies to cooperative games, in general. For its use as a measure of power in voting games, it matters in which order players enter a coalition. Accordingly, Table 3 lists all 24 permutations of all four players in the voting game being analyzed.

Table 3: Calculations for the Shapley-Shubik Power Index

Permutation	Player
	Aunt (0)	Me (1)
(0, 1, 2, 3)	v( {0} ) - v( {} ) = 0	v( {0, 1} ) - v( {0} ) = 1
(0, 1, 3, 2)	v( {0} ) - v( {} ) = 0	v( {0, 1} ) - v( {0} ) = 1
(0, 2, 1, 3)	v( {0} ) - v( {} ) = 0	v( {0, 1, 2} ) - v( {0, 2} ) = 0
(0, 2, 3, 1)	v( {0} ) - v( {} ) = 0	v( {0, 1, 2, 3} ) - v( {0, 2, 3} ) = 0
(0, 3, 1, 2)	v( {0} ) - v( {} ) = 0	v( {0, 1, 3} ) - v( {0, 3} ) = 0
(0, 3, 2, 1)	v( {0} ) - v( {} ) = 0	v( {0, 1, 2, 3} ) - v( {0, 2, 3} ) = 0
(1, 0, 2, 3)	v( {0, 1} ) - v( {1} ) = 1	v( {1} ) - v( {} ) = 0
(1, 0, 3, 2)	v( {0, 1} ) - v( {1} ) = 1	v( {1} ) - v( {} ) = 0
(1, 2, 0, 3)	v( {0, 1, 2} ) - v( {1, 2} ) = 1	v( {1} ) - v( {} ) = 0
(1, 2, 3, 0)	v( {0, 1, 2, 3} ) - v( {1, 2, 3} ) = 0	v( {1} ) - v( {} ) = 0
(1, 3, 0, 2)	v( {0, 1, 3} ) - v( {1, 3} ) = 1	v( {1} ) - v( {} ) = 0
(1, 3, 2, 0)	v( {0, 1, 2, 3} ) - v( {1, 2, 3} ) = 0	v( {1} ) - v( {} ) = 0
(2, 0, 1, 3)	v( {0, 2} ) - v( {2} ) = 1	v( {0, 1, 2} ) - v( {0, 2} ) = 0
(2, 0, 3, 1)	v( {0, 2} ) - v( {2} ) = 1	v( {0, 1, 2, 3} ) - v( {0, 2, 3} ) = 0
(2, 1, 0, 3)	v( {0, 1, 2} ) - v( {1, 2} ) = 1	v( {1, 2} ) - v( {2} ) = 0
(2, 1, 3, 0)	v( {0, 1, 2, 3} ) - v( {1, 2, 3} ) = 0	v( {1, 2} ) - v( {2} ) = 0
(2, 3, 0, 1)	v( {0, 2, 3} ) - v( {2, 3} ) = 1	v( {0, 1, 2, 3} ) - v( {0, 2, 3} ) = 0
(2, 3, 1, 0)	v( {0, 1, 2, 3} ) - v( {1, 2, 3} ) = 0	v( {1, 2, 3} ) - v( {2, 3} ) = 1
(3, 0, 1, 2)	v( {0, 3} ) - v( {3} ) = 1	v( {0, 1, 3} ) - v( {0, 3} ) = 0
(3, 0, 2, 1)	v( {0, 3} ) - v( {3} ) = 1	v( {0, 1, 2, 3} ) - v( {0, 2, 3} ) = 0
(3, 1, 0, 2)	v( {0, 1, 3} ) - v( {1, 3} ) = 1	v( {1, 3} ) - v( {3} ) = 0
(3, 1, 2, 0)	v( {0, 1, 2, 3} ) - v( {1, 2, 3} ) = 0	v( {1, 3} ) - v( {3} ) = 0
(3, 2, 0, 1)	v( {0, 2, 3} ) - v( {2, 3} ) = 1	v( {0, 1, 2, 3} ) - v( {0, 2, 3} ) = 0
(3, 2, 1, 0)	v( {0, 1, 2, 3} ) - v( {1, 2, 3} ) = 0	v( {1, 2, 3} ) - v( {2, 3} ) = 1

Table 3 shows some initially confusing calculations in the last two columns, where each of these columns is defined for a given player. Suppose a player and a permutation are defined. For that permutation, let the set S_{π, i} contain those players in the permutation π to the left of the given player i. The difference, in the last two columns, is the following, for i equal to 0 and to 1, respectively:

v(S_{π, i} ∪ {i}) - v(S_{π, i})

The Shapley-Shubik power index, for a player, is the ratio of a sum to the number of permutations of players. And that sum is calculated for each player, as the sum over all permutations, of the above difference in the value of the value of the characteristic function.

If I understand correctly, given a permutation, the above difference can only take on values of 0 or 1. And it will only be 1 for one player, where that player determines whether the formation of the coalition in the order given will be a winning coalition. As a consequence, the Shapley-Shubik power index is guaranteed to sum over players to unity. In this case, power is a fixed amount, with each player being measured as having a defined proportion of that power.

5.0 Both Power Indices

The above has stepped through the calculation of two power indices, for all players, in a given game. Table 4 lists their values, as well as a normalization of the Penrose-Banzhauf power index such that the sum of the power, over all players, is unity. (I gather that the Penrose-Banzhauf index and the normalized index do not have the same properties.) As one might expect from the definition of the game, "my aunt" has more power than "me" in this game.

Table 4: The Penrose-Banzhaf and Shapley-Shubik Power Indices

Player	Penrose-Banzhaf Power Index		Shapley-Shubik Power Index
	Index	Normalized
0	6/16 = 3/8	6/12 = 1/2	12/24 = 1/2
1	2/16 = 1/8	2/12 = 1/6	4/24 = 1/6
2	2/16 = 1/8	2/12 = 1/6	4/24 = 1/6
3	2/16 = 1/8	2/12 = 1/6	4/24 = 1/6

In many voting games, the normalized Penrose-Banzhauf and Shapley-Shubik power indices are not identical for all players. In fact, suppose the rules for the above variation of Me and my Aunt voting game are varied. Suppose now that four votes - a supermajority - are needed to carry a motion. The normalized Penrose-Banzhaf index for player 0 becomes 1/3, while each of the other players have a normalized Penrose-Banzhaf index of 2/9. Interestingly enough, the Shapley-Shubik indices for the players do not change, if I have calculated correctly. But the values assigned to rows in Table 3 do sometimes vary. Anyways, that one tweak of the rules results in different power indices, depending on which method one adopts. A more interesting example would be one in which the rankings vary among power indices.

Other power indices, albeit less common, do exist. Which one is most widely applicable? I would think that mainstream economists, given game theory and marginalism, would tend to prefer the Shapley-Shubik power index. Felsenthal and Machover (2004) seem to be widely recognized experts on measures of voting power, and they have come to prefer the Penrose-Banzhaf index over the Shapley-Shubik index.

6.0 Where To Go From Here

I have described above a couple of power indices in voting games. As I understand it, many have tried to write down reasonable axioms that characterize power indices. One challenge is to specify a set of axioms such that your preferred power index is the only one that satisfies them. But, as I understand it, some sets of reasonable axioms are open insofar as more than one power index would satisfy them. I seem to recall a theorem that one could create a power index for a reasonable set of axioms such that whichever player you want in a voting game is the most powerful. Apparently, a connection can be drawn between a power index and a voting procedure. And Donald Saari boasts that he could create an apparently fair voting procedure that would result in whatever candidate you like being elected.

I gather that many examples of voting games have been presented in which apparently paradoxical or perverse results arise. And these do not seem to be merely theoretical results. Can I find some such examples? Perhaps, I should look here at some of Daron Acemoglu's work.

I am aware of three types of examples to look for. One is that of a dummy. A dummy is a player that, under the weights and the rule for how many votes are needed for passage, can never be decisive in a coalition. Whether this player drops out or joins a coalition can never change whether or not a resolution is passed, even though the player has a positive weight. A second odd possibility arises as the consequence of adding a new member to the electorate:

"...power of a weighted voting body may increase, rather than decrease, when new members are added to the original body." -- Steven J. Brams and Paul J. Affuso (1976).

A third odd possibility apparently can arise on a council when one district annexes another. Suppose, the district annexing the other consequently increases the weight of its vote accordingly. One might think a greater weight leads to more power. But, in certain cases, the normalized Penrose-Banzhaf index can decrease.

The above calculations for the Penrose-Banzhaf and Shapley-Shubik power indices treat all coalitions or permutations, respectively, as equally likely to arise. Empirically, this does not seem to be true. And this has an impact on how one might measure power. For example, since voting is unweighted on the Supreme Court of the United States, all justices might be thought to be equally powerful. But, because of the formation of well-defined blocks, Anthony Kennedy was often described as being particularly powerful in deciding court decisions, at least when Antonin Scalia was still alive. So empirically, one might include some assessment of the affinities of the players for one another and, thus, some influence on the probabilities of each coalition forming. This will have consequences on the calculation of power indices. But why stop there? In the United States these days, politicians only seem to represent the most wealthy.

Update: This page, from the University of Warwick, has links to utilities for calculating various power indices.

References

• Steven J. Brams and Paul J. Affuso (1976). Power and Size: A New Paradox, Theory and Decision. V. 7, Iss. 1 (Feb.): pp. 29-56.
• Dan S. Felsenthal and Moshé Machover (2004). Voting Power Measurement: A Story of Misreinvention, London Scool of Economics and Political Science
• Andrew Gelman, Jonathan N. Katz, and Joseph Bafumi (2004). Standard Voting Power Indexes Do Not Work: An Empirical Analysis, B. J. Pol. S.. V. 34: pp. 657-674.
• Guillermo Owen (1971) Political Games, Naval Research Logistics Quarterly. V. 18, Iss. 3 (Sep.): pp. 345-355.
• Donald G. Saari and Katri K. Sieberg (1999). Some Surprising Properties of Power Indices.

Inane Responses To The Cambridge Capital Controversy

I consider the following views, if unqualified and without caveats, just silly:

• The Cambridge Capital Controversy (CCC) was only attacking aggregate neoclassical theory.
• The CCC is just a General Equilibrium argument, and it has been subsumed by General Equilibrium Theory. (Citing Mas Colell (1989) here does not help.)
• The CCC does not have anything to say about partial, microeconomic models.
• Perverse results, such as reswitching and capital-reversing, only arise in the special case of Leontief production functions. If you adopt widely used forms for production functions, the perverse results go away.
• It is an empirical question whether non-perverse results follow from neoclassical assumptions. And nobody has ever found empirical examples of capital-reversing or reswitching.
• Mainstream economists have moved on since the 1960s, and their models these days are not susceptible to the Cambridge critique.

I would think that one could not get such ideas published in any respectable journal. On the other hand, Paul Romer did get his ignorance about Joan Robinson into the American Economic Review

References

• Andreu Mas-Colell (1989). Capital theory paradoxes: Anything goes. In Joan Robinson and Modern Economic Theory (ed. by George R. Feiwel), Macmillan.