The give-up problem for blocked regional lists with multi-winners

The current electoral law for the Italian Parliament prescribes blocked, linearly ordered lists of candidates for each party within each constituency. The peculiarity of the Italian electoral system is that a party can present the same candidate in different constituencies. There are several seats at stake in each constituency; these seats are allocated to the parties proportionally to the total number of votes they get. If the blocked list mechanism-which assigns the seats obtained by a party in a constituency to the first candidates of the corresponding ordered list-causes some candidates to win in more than one constituency, they may retain only one of the seats, giving up all the remaining ones. Thus, the problem arises for a party to find a suitable “schedule of give-ups” that produces the final set of winners for that party. In order to do this, we assume that such decision is centralized and based on some models of global (inter-regional) preferences over the set of candidates. In this paper, we introduce two classes of models to formulate the “give-up problem”, i.e., utility and ordinal models, and we show that for both of them some natural formulations of the problem can be efficiently solved by network flows techniques.     

Thresholds of the Divisor Methods

We give an algorithm which permits calculating the maximum and minimum vote shares that allow a party to obtain h seats, that is, the threshold of exclusion and the threshold of representation. These have already been studied for some methods (such as d'Hondt or Sainte-Laguë), and are here generalized to any divisor method, and to any number of seats. The thresholds depend on the size of the constituency, the number of parties running in the constituency, and the divisor method used. Finally, we give some consequences, including a characterization of the d'Hondt method.     

Error minimization methods in biproportional apportionment

One of the most active research lines in the area of electoral systems to date deals with the Biproportional Apportionment Problem, which arises in those proportional systems where seats must be allocated to parties within territorial constituencies. A matrix of the vote counts of the parties within the constituencies is given, and one has to convert the vote matrix into an integer matrix of seats ??as proportional as possible?? to it, subject to the constraints that each constituency be granted its pre-specified number of seats, each party be allotted the total number of seats it is entitled to on the basis of its national vote count, and a zero-vote zero-seat condition be satisfied. The matrix of seats must simultaneously meet the integrality and the proportionality requirement, and this not infrequently gives rise to self-contradictory procedures in the electoral laws of some countries. Here we discuss a class of methods for Biproportional Apportionment characterized by an ??error minimization?? approach. If the integrality requirement is relaxed, fractional seat allocations (target shares) can be obtained so as to achieve proportionality at least in theory. In order to restore integrality, one then looks for integral apportionments that are as close as possible to the ideal ones in a suitable metric. This leads to the formulation of constrained optimization problems called ??best approximation problems?? which are solvable in polynomial time through the use of network flow techniques. These error minimization methods can be viewed as an alternative to the classical axiomatic approach introduced by Balinski and Demange (in Math Oper Res 14:700?C719, 1989a; Math Program 45:193?C210, 1989b). We provide an empirical comparison between these two approaches with a real example from the Italian Elections and a theoretical discussion about the axioms that are not necessarily satisfied by the error minimization methods.     

A note on matrices of zeros and ones

Gale and Ryser have given a necessary and sufficient condition for the existence of a matrix of zeros and ones with specified row and column sums. Though in general it appears quite difficult to compute the number of such matrices, it is shown in this note that it is possible to obtain a quite elementary and easily used formula in a large number of interesting cases.     

Constructing integral matrices with given line sums

D. Gale, in 1957 and H.J. Ryser, in 1963, independently proved the famous Gale–Ryser theorem on the existence of (0, 1)–matrices with prescribed row and column sums. Around the same time, in 1968, Mirsky solved the more general problem of finding conditions for the existence of a nonnegative integral matrix with entries less than or equal to p and prescribed row and column sums. Using the results of Mirsky, Brualdi shows that a modified version of the domination condition of Gale–Ryser is still necessary and sufficient for the existence of a matrix under the same constraints. In this article we prove another extension of Gale–Ryser’s domination condition. Furthermore we present a method to build nonnegative integral matrices with entries less than or equal to p and prescribed row and column sums.     

Constructive extensions of two results on graphic sequences

A list of nonnegative integers is graphic if it is the list of vertex degrees of a graph. Erd?s-Gallai characterized graphic lists, and Gale and Ryser, independently, provided one for a bipartite graph, given two lists of nonnegative integers. We give a constructive proof of an extension of these two results.     

Properties of (0, 1)-matrices with no triangles

We study (0, 1)-matrices which contain no triangles (submatrices of order 3 with row and column sums 2) previously studied by Ryser. Let the row intersection of row i and row j of some matrix, when regarded as a vector, have a 1 in a given column if both row i and row j do and a zero otherwise. For matrices with no triangles, columns sums ?2, we find that the number of linearly independent row intersections is equal to the number of distinct columns. We then study the extremal (0, 1)-matrices with no triangles, column sums ?2, distinct columns, i.e., those of size mx(^m₂). The number of columns of column sum l is m ? l + 1 and they form a (l ? 1)-tree. The ((^m₂)) columns have a unique SDR of pairs of rows with 1's. Also, these matrices have a fascinating inductive buildup. We finish with an algorithm for constructing these matrices.     

Dyadic sets S: a dichotomy for indecomposable S-matrices

Dyadic sets S (see [3]) give rise to S-matrices, which are important in the investigation of modules over finite-dimensional algebras. If S admits only finitely many isoclasses of indecomposable S-matrices, “most” of the indecomposables can be described by means of a reduction to a well known special case. We determine the “missing” indecomposables.     

On matching numbers of tree and bipartite degree sequences

We study the possible values of the matching number among all trees with a given degree sequence as well as all bipartite graphs with a given bipartite degree sequence. For tree degree sequences, we obtain closed formulas for the possible values. For bipartite degree sequences, we show the existence of realizations with a restricted structure, which allows to derive an analogue of the Gale–Ryser Theorem characterizing bipartite degree sequences. More precisely, we show that a bipartite degree sequence has a realization with a certain matching number if and only if a cubic number of inequalities similar to those in the Gale–Ryser Theorem are satisfied. For tree degree sequences as well as for bipartite degree sequences, the possible values of the matching number form intervals.     

Dynamic adjustment: an electoral method for relaxed double proportionality

We describe an electoral system for distributing seats in a parliament. It gives proportionality for the political parties and close to proportionality for constituencies. The system suggested here is a version of the system used in Sweden and other Nordic countries with permanent seats in each constituency and adjustment seats to give proportionality on the national level. In the national election of 2010 the current Swedish system failed to give proportionality between parties. We examine here one possible cure for this unwanted behavior. The main difference compared to the current Swedish system is that the number of adjustment seats is not fixed, but rather dynamically determined to be as low as possible and still insure proportionality between parties.     

On the inverse M-matrix problem for (0,1)-matrices

A graph-theoretic approach is used to characterize (0,1)-matrices which are inverses of M-matrices. Our main results show that a (0,1)-matrix is an inverse of an M-matrix if and only if its graph induces a partial order on its set of vertices and does not contain a certain specific subgraph.     

Some Consequences of a Three-Party Split in a UK General Election

The British electoral system is unique in Europe in being of the first-past-the-post variety. The apparent emergence of a strong third party renders any prediction exercise a good deal more difficult, although some political commentators appear oblivious to that fact. It would appear that a transition matrix approach is capable of providing the deeper insights needed to explore the consequences of alternative voting-behaviour patterns. Unfortunately data of this form are not currently collected, but it is possible to postulate that transition matrices of a particular form could be of interest to the three parties. By associating such transition probabilities with the 1983 results for each of the 633 mainland constituencies, one can derive interesting relationships between the number of seats secured by each party.A range of computer analyses was performed, and this article sets out some of the more interesting results, some of which came as something of a surprise.     

Modeling social services performance: a four-stage DEA approach to evaluate fundraising efficiency,capacity building,service quality,and effectiveness in the nonprofit sector

The Swedish electoral system exhibits significant levels of proportionality compared with the systems used in other countries. However, it has several deficiencies that could be corrected. Therefore, this paper (a) evaluates the current Swedish electoral system by identifying the imbalances in the representation of political parties and the sizes of the electoral constituencies that can occur and (b) presents two proposals for improvement that seek to correct the previously identified deficiencies. The first proposal consists of a slight modification of the current system that applies when parties get more seats than they proportionally deserve according to their global number of votes, as occurred in the 2010 election. In this case, the proposal includes a criterion so that the overrepresented parties return their excess seats. The second proposal relies on the implementation of biproportional allotments and on the replacement of the electoral thresholds of 4 % of the total votes nationwide and 12 % of the votes in a given constituency by a new threshold based on a reduction in the number of votes of the parties. The application of any of these proposals to the Swedish election held in 2010 reveals that the deficiencies in the representation of political parties are eliminated. Furthermore, the second proposal also corrects the deficiencies in the sizes of the electoral constituencies for Sweden.     

Matrices with a transitive graph and inverse M-matrices

The relationship between inverse M-matrices and matrices whose graph is transitive is studied. The results are applied to obtain a new proof of the characterization, due to M. Lewin and M. Neumann, of (0,1) inverse M-matrices.     

Parametric vs. divisor methods of apportionment

This paper formulates a new criterion that distinguishes the set of parametric methods within the set of all the divisor methods of apportionment. The criterion—that a method transfer seats as it “should”—asks that as population (or the votes of parties in a PR system) is shifted more and more from one state to another state (from one party to another party) at some point the first state (or party) is apportioned one less seat, the second state (or party) one more seat, and the remaining apportionments are as they were. It goes on to examine several properties of parametric methods.     

Properties of (0, 1)-matrices without certain configurations

We generalize results of Ryser on (0, 1)-matrices without triangles, 3 × 3 submatrices with row and column sums 2. The extremal case of matrices without triangles was previously studied by the author. Let the row intersection of row i and row j (i ≠ j) of some matrix, when regarded as a vector, have a 1 in a given column if both row i and row j do not 0 otherwise. For matrices satisfying some conditions on forbidden configurations and column sums ? 2, we find that the number of linearly independent row intersections is equal to the number of distinct columns. The extremal matrices with m rows and $\text{(}\text{m}\text{2}\text{)}$ distinct columns have a unique SDR of pairs of rows with 1's. A triangle bordered with a column of 0's and its (0, 1)-complement are also considered as forbidden configurations. Similar results are obtained and the extremal matrices are closely related to the extremal matrices without triangles.     

A generalization of Ryser's theorem on term rank

In his work on classes of (0, 1)-matrices with given row and column sum vectors, Herbert Ryser proved that the maximum term rank possible in a normalized class, ρ, can be realized by a matrix having ρ (independent) 1's in positions (1, ρ), (2, ρ − 1), … , (ρ, 1). We study the positions occupied by sets of t ρ independent 1's.     

On the spectral radius of (0,1)-matrices

We determine the maximum spectral radius for (0,1)-matrices with k² andk²+1 1's, respectively, and for symmetric (0,1)-matrices with zero trace and $\text{e=}\text{k}\text{2}$1's (graphs with e edges). In all cases, equality is characterized.     

Ordering of nested square roots of 2 according to the Gray code

In this paper, we discuss some relations between zeros of Lucas–Lehmer polynomials and the Gray code. We study nested square roots of 2 applying a “binary code” that associates bits 0 and 1 to “plus” and “minus” signs in the nested form. This gives the possibility to obtain an ordering for the zeros of Lucas–Lehmer polynomials, which take the form of nested square roots of 2.     

On permanents and the zeros of rook polynomials

The concept of rook polynomial of a “chessboard” may be generalized to the rook polynomial of an arbitrary rectangular matrix. A conjecture that the rook polynomials of “chessboards” have only real zeros is thus carried over to the rook polynomials of nonnegative matrices. This paper proves these conjectures, and establishes interlacing properties for the zeros of the rook polynomials of a positive matrix and the matrix obtained by striking any one row or any one column.