Search

The paper provides a new characterization of weighted games within the class of simple games. It is based on a stronger form of the point-set-additive pseudoweighting property of simple games. The characterization obtained is of interest in various research fields such as game theory, coherent structures, logic gates, operations research and Boolean algebra. A (monotonic) simple game corresponds to an inequivalent (monotonic) function in Boolean algebra and a weighted game corresponds to a threshold function. The characterization obtained provides a better understanding of these mathematical structures while opening new prospects for solving numerous open problems in these areas. [ABSTRACT FROM AUTHOR]

Kurz and Napel (Optim Lett 10(6):1245–1256, 2015, https://doi.org/10.1007/s11590-015-0917-0) proved that the voting system of the EU council (based on the 2014 population data) cannot be represented as the intersection of six weighted games, i.e., its dimension is at least 7. This set a new record for real-world voting rules and the authors posed the exact determination as a challenge. Recently, Chen et al. (An upper bound on the dimension of the voting system of the European Union Council under the Lisbon rules, 2019, arXiv:1907.09711) showed that the dimension is at most 24. We provide the first improved lower bound and show that the dimension is at least 8. [ABSTRACT FROM AUTHOR]

The remoteness from a simple game to a weighted game can be measured by the concept of the dimension or the more general Boolean dimension. It is known that both measures can be exponential in the number of voters. For complete simple games it was only recently shown in O'Dwyer and Slinko (2017) that the dimension can also be exponential. Here we show that this is also the case for complete simple games with two types of voters and for the Boolean dimension of general complete simple games, which was posed as an open problem in O'Dwyer and Slinko (2017). • We study the dimension of complete simple games. • The dimension of a complete simple game with two type of voters can be exponential. • A polynomial upper bound for the Boolean dimension of a complete simple game. • We construct representations where weights weakly respect the voters' ordering. [ABSTRACT FROM AUTHOR]

In this paper, we evaluate in the context of weighted (j, k)-simple games, the maximal degree of perturbations which may be allowed, in voters weights and/or in the quotas, without changing the structure of the game. For this purpose, we extend on (j, k)-simple games the notion of amplitude well known for ordinary simple games. Recall that, (j, k)-simple games provide a model of decision making in which each voter has j levels of approval (inputs), while k levels of approval are permitted as collective decision (outputs). Here, the j inputs are qualitatively ordered, same are the k outputs. Ordinary simple games correspond to the particular case j = k = 2 . Our results generalize those obtained by Freixas and Puente (Qüestiió 23(1):43–60, 1999) on ordinary simple games. We illustrate by computing the amplitude of some real world examples like the United Nations Security Council which is a (3, 2)-simple game. [ABSTRACT FROM AUTHOR]

The Nakamura number is an appropriate invariant of a simple game to study the existence of social equilibria and the possibility of cycles. For symmetric (quota) games its number can be obtained by an easy formula. For some subclasses of simple games the corresponding Nakamura number has also been characterized. However, in general, not much is known about lower and upper bounds depending on invariants of simple, complete or weighted games. Here, we survey such results and highlight connections with other game theoretic concepts. [ABSTRACT FROM AUTHOR]

This paper has a twofold scope. The first one is to clarify and put in evidence the isomorphic character of two theories developed in quite different fields: on one side, threshold logic, on the other side, simple games. One of the main purposes in both theories is to determine when a simple game is representable as a weighted game, which allows a very compact and easily comprehensible representation. Deep results were found in threshold logic in the sixties and seventies for this problem. However, game theory has taken the lead and some new results have been obtained for the problem in the past two decades. The second and main goal of this paper is to provide some new results on this problem and propose several open questions and conjectures for future research. The results we obtain depend on two significant parameters of the game: the number of types of equivalent players and the number of types of shift-minimal winning coalitions. [ABSTRACT FROM AUTHOR]

Consider a setting in which agents can take one of two ordered actions and in which the incentive to take the high action increases in the number of other agents taking it. Furthermore, assume that we do not know anything else about the game being played. What can we say about the details of the interaction between actions and incentives when we observe a set or a subset of all possible equilibria? In this paper, we study this question by exploring three nested classes of games: (a) binary games of strategic complements; (b) games in (a) that admit a network representation; and (c) games in (b) in which the network is complete. Our main results are the following: It has long been established in the literature that the set of pure strategy Nash equilibria of any binary game of strategic complements among a set, N, of agents can be seen as a lattice on the set of all subsets of N under the partial order defined by the set inclusion relation (C). If the game happens to be strict in the sense that agents are never indifferent among outcomes (games in (a)), then the resulting lattice of equilibria satisfies a straightforward sparseness condition. (1) We show that, in fact, for each such lattice, L, there is a game in (a), such that its set of equilibria is L (we say that such a game expresses L); (2) We show that there exists a game in (b), whose set of equilibria contains a given collection, C, of subsets of N, if and only C satisfies the sparseness condition, and the smallest game in (a) expressing C is trade robust; (3) We show that there exists a game on the complete graph (games in (c)), whose set of equilibria coincides with some collection, C, if and only if C is a chain satisfying the sparseness condition.

The Lisbon voting system of the Council of the European Union, which became effective in November 2014, cannot be represented as the intersection of six or fewer weighted games, i.e., its dimension is at least 7. This sets a new record for real-world voting bodies. A heuristic combination of different discrete optimization methods yields a representation as the intersection of 13,368 weighted games. Determination of the exact dimension is posed as a challenge to the community. The system's Boolean dimension is proven to be 3. [ABSTRACT FROM AUTHOR]

Consider a setting in which agents can take one of two ordered actions and in which the incentive to take the high action increases in the number of other agents taking it. Furthermore, assume that we do not know anything else about the game being played. What can we say about the details of the interaction between actions and incentives when we observe a set or a subset of all possible equilibria? In this paper, we study this question by exploring three nested classes of games: (a) binary games of strategic complements; (b) games in (a) that admit a network representation; and (c) games in (b) in which the network is complete. Our main results are the following: It has long been established in the literature that the set of pure strategy Nash equilibria of any binary game of strategic complements among a set, N, of agents can be seen as a lattice on the set of all subsets of N under the partial order defined by the set inclusion relation (⊆). If the game happens to be strict in the sense that agents are never indifferent among outcomes (games in (a)), then the resulting lattice of equilibria satisfies a straightforward sparseness condition. (1) We show that, in fact, for each such lattice, L, there is a game in (a), such that its set of equilibria is L (we say that such a game expresses L); (2) We show that there exists a game in (b), whose set of equilibria contains a given collection, C, of subsets of N, if and only C satisfies the sparseness condition, and the smallest game in (a) expressing C is trade robust; (3) We show that there exists a game on the complete graph (games in (c)), whose set of equilibria coincides with some collection, C, if and only if C is a chain satisfying the sparseness condition. [ABSTRACT FROM AUTHOR]

We investigate voting systems with two classes of voters, for which there is a hierarchy giving each member of the stronger class more influence or important than each member of the weaker class. We deduce for voting systems one important counting fact that allows determining how many of them are for a given number of voters. In fact, the number of these systems follows a Fibonacci sequence with a smooth polynomial variation on the number of voters. On the other hand, we classify by means of some parameters which of these systems are weighted. This result allows us to state an asymptotic conjecture which is opposed to what occurs for symmetric games. [ABSTRACT FROM AUTHOR]