Portal de Periódicos da CAPES

On the enumeration of majority games

1959; American Mathematical Society; Volume: 13; Issue: 65 Linguagem: Inglês

10.1090/s0025-5718-1959-0103129-5

1088-6842

John Isbell,

Organizational Management and Leadership

(3) In this paper, we shall identify two games if there is a one-to-one correspondence between their players identifying their families of winning sets; to name a more definite object one must say, not game but game with ordered players Pi, * *, P,, or a similar phrase. Beyond this, note that n-player game (e.g. the 435-player game 'of the House of Representatives) may be converted into (n + k)-player game by adjoining k voteless players or dummies. The phrase an n-player game G does not here imply that all n players are non-dummies. (In the first part of the argument we need games with dummies; afterward we shall exclude them.) A majority game is a game for which one can assign numerical weights wl, , wn to the players so that the winning sets are precisely those sets which have more than half the total weight. Some of the wi may be negative or zero; it is easy to see that the corresponding players must be dummies. (Since every superset of a winning set wins, a player can have negative weight wi only if I wi I is so small that it makes no difference.) Given a game G, the question whether is a majority game is effectively decidable, since it turns on a finite system of linear inequalities. No better method than the obvious ones is known. It is clear that every majority game has non-negative integral weights-even positive integral weights, for any weights may be assigned to the dummies provided the weights of the other players are made large enough. The method described below for enumerating all majority games depends on the determination of the game with ordered players with weights (wo, w1, * , w ) by the systems (woV + wl, w2, ***, wn) and (wo -w1, w2, ***, wa). The choice