BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Sascha Kurz appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
This text contains some notes on the Griesmer bound. In particular, we give a geometric proof of the Griesmer bound for the generalized weights and show that a Solomon--Stiffler type construction attains it if the minimum distance is sufficiently large. We also determine the parameters of optimal binary codes for dimensions at most seven and the optimal ternary codes for dimensions at most five.
We consider locally recoverable codes (LRCs) and aim to determine the smallest possible length $n=n_q(k,d,r)$ of a linear $[n,k,d]_q$-code with locality $r$. For $k\le 7$ we exactly determine all values of $n_2(k,d,2)$ and for $k\le 6$ we exactly determine all values of $n_2(k,d,1)$. For the ternary field we also state a few numerical results. As a general result we prove that $n_q(k,d,r)$ equals the Griesmer bound if the minimum Hamming distance $d$ is sufficiently large and all other parameters are fixed.
We consider integers whose squares have just three decimal digits. Examples are e.g. given by $2108436491907081488939581538^2 = 4445504440405440505004450045555054500055550554550445444$ and $10100000000010401000000000101^2 = 102010000000210100200000110221001000002101002000000010201$. The aim of this paper is to summarize the current knowledge on squares with three digits, scattered around webpages and newsgroup postings, and to add a few new insights. While we will mostly focus on the base $B=10$, several results are presented for general values of $B$. The used mathematical tools are completely elementary. However, we give complete proofs of all statements or explicitly state them as conjectures.
We exhibit the hidden beauty of weighted voting and voting power by applying a generalization of the Penrose-Banzhaf index to social choice rules. Three players who have multiple votes in a committee decide between three options by plurality rule, Borda's rule, antiplurality rule, or one of the scoring rules in between. A priori influence on outcomes is quantified in terms of how players' probabilities to be pivotal for the committee decision compare to a dictator. The resulting numbers are represented in triangles that map out structurally equivalent voting weights. Their geometry and color variation reflect fundamental differences between voting rules, such as their inclusiveness and transparency.
The Public Good index is a power index for simple games introduced by Holler and later axiomatized by Holler and Packel, so that some authors also speak of the Holler--Packel index. A generalization to the class of games with transferable utility was given by Holler and Li. Here we generalize the underlying ideas to games with several levels of approval in the input and output -- so-called $(j,k)$ simple games. Corresponding axiomatizations are also provided.
Service rate is an important, recently introduced, performance metric associated with distributed coded storage systems. Among other interpretations, it measures the number of users that can be simultaneously served by the storage system. We introduce a geometric approach to address this problem. One of the most significant advantages of this approach over the existing approaches is that it allows one to derive bounds on the service rate of a code without explicitly knowing the list of all possible recovery sets. To illustrate the power of our geometric approach, we derive upper bounds on the service rates of the first order Reed-Muller codes and simplex codes. Then, we show how these upper bounds can be achieved. Furthermore, utilizing the proposed geometric technique, we show that given the service rate region of a code, a lower bound on the minimum distance of the code can be obtained.
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 notions can be exponential in the number of voters. For complete simple games it was only recently shown 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.
Constant dimension codes are used for error control in random linear network coding, so that constructions for these codes with large cardinality have achieved wide attention in the last decade. Here, we improve the so-called linkage construction. Known upper bounds for constant dimension codes containing lifted MRD codes are generalized.
We consider a fashion discounter distributing its many branches with integral multiples from a set of available lot-types. For the problem of approximating the branch and size dependent demand using those lots we propose a tailored exact column generation approach assisted by fast algorithms for intrinsic subproblems, which turns out to be very efficient on our real-world instances as well as on random instances.
Constant dimension codes are e.g. used for error correction and detection in random linear network coding, so that constructions for these codes have achieved wide attention. Here, we improve over 150 lower bounds by describing better constructions for subspace distance 4.
In this article, the effective lengths of all $q^r$-divisible linear codes over $\mathbb{F}_q$ with a non-negative integer $r$ are determined. For that purpose, the $S_q(r)$-adic expansion of an integer $n$ is introduced. It is shown that there exists a $q^r$-divisible $\mathbb{F}_q$-linear code of effective length $n$ if and only if the leading coefficient of the $S_q(r)$-adic expansion of $n$ is non-negative. Furthermore, the maximum weight of a $q^r$-divisible code of effective length $n$ is at most $σq^r$, where $σ$ denotes the cross-sum of the $S_q(r)$-adic expansion of $n$. This result has applications in Galois geometries. A recent theorem of N{ă}stase and Sissokho on the maximum size of a partial spread follows as a corollary. Furthermore, we get an improvement of the Johnson bound for constant dimension subspace codes.
Minimal codewords have applications in decoding linear codes and in cryptography. We study the number of minimal codewords in binary linear codes that arise by appending a unit matrix to the adjacency matrix of a graph.
In this work private information retrieval (PIR) codes are studied. In a $k$-PIR code, $s$ information bits are encoded in such a way that every information bit has $k$ mutually disjoint recovery sets. The main problem under this paradigm is to minimize the number of encoded bits given the values of $s$ and $k$, where this value is denoted by $P(s,k)$. The main focus of this work is to analyze $P(s,k)$ for a large range of parameters of $s$ and $k$. In particular, we improve upon several of the existing results on this value.
The Grassmannian $\mathcal{G}_q(n,k)$ is the set of all $k$-dimensional subspaces of the vector space $\mathbb{F}_q^n$. Kötter and Kschischang showed that codes in Grassmannian space can be used for error-correction in random network coding. On the other hand, these codes are $q$-analogs of codes in the Johnson scheme, i.e., constant dimension codes. These codes of the Grassmannian $\mathcal{G}_q(n,k)$ also form a family of $q$-analogs of block designs and they are called subspace designs. In this paper, we examine one of the last families of $q$-analogs of block designs which was not considered before. This family, called subspace packings, is the $q$-analog of packings, and was considered recently for network coding solution for a family of multicast networks called the generalized combination networks. A subspace packing $t$-$(n,k,λ)_q$ is a set $\mathcal{S}$ of $k$-subspaces from $\mathcal{G}_q(n,k)$ such that each $t$-subspace of $\mathcal{G}_q(n,t)$ is contained in at most $λ$ elements of $\mathcal{S}$. The goal of this work is to consider the largest size of such subspace packings. We derive a sequence of lower and upper bounds on the maximum size of such packings, analyse these bounds, and identify the important problems for further research in this area.
The minimum distance of all binary linear codes with dimension at most eight is known. The smallest open case for dimension nine is length $n=46$ with known bounds $19\le d\le 20$. Here we present a $[46,9,20]_2$ code and show its uniqueness. Interestingly enough, this unique optimal code is asymmetric, i.e., it has a trivial automorphism group. Additionally, we show the non-existence of $[47,10,20]_2$ and $[85,9,40]_2$ codes.
A committee's decisions on more than two alternatives much depend on the adopted voting method, and so does the distribution of power among the committee members. We investigate how different aggregation methods such as plurality runoff, Borda count, or Copeland rule map asymmetric numbers of seats, shares, voting weights, etc. to influence on outcomes when preferences vary. A generalization of the Penrose-Banzhaf power index is proposed and applied to the IMF Executive Board's election of a Managing Director, extending a priori voting power analysis from binary simple voting games to choice in weighted committees.
We study the minimum number of minimal codewords in linear codes from the point of view of projective geometry. We derive bounds and in some cases determine the exact values. We also present an extension to minimal subcode supports.
A simple game $(N,v)$ is given by a set $N$ of $n$ players and a partition of~$2^N$ into a set~$\mathcal{L}$ of losing coalitions~$L$ with value $v(L)=0$ that is closed under taking subsets and a set $\mathcal{W}$ of winning coalitions $W$ with $v(W)=1$. Simple games with $α= \min_{p\geq 0}\max_{W\in {\cal W}, L\in {\cal L}} \frac{p(L)}{p(W)}<1$ are exactly the weighted voting games. We show that $α\leq \frac{1}{4}n$ for every simple game $(N,v)$, confirming the conjecture of Freixas and Kurz (IJGT, 2014). For complete simple games, Freixas and Kurz conjectured that $α=O(\sqrt{n})$. We prove this conjecture up to a $\ln n$ factor. We also prove that for graphic simple games, that is, simple games in which every minimal winning coalition has size~2, computing $α$ is \NP-hard, but polynomial-time solvable if the underlying graph is bipartite. Moreover, we show that for every graphic simple game, deciding if $α<a$ is polynomial-time solvable for every fixed $a>0$.
It is shown that there does not exist a binary projective triply-even code of length $59$. This settles the last open length for projective triply-even binary codes. Therefore, projective triply-even binary codes exist precisely for lengths $15$, $16$, $30$, $31$, $32$, $45$--$51$, and $\ge 60$.
The International Monetary Fund is one of the largest international organizations using a weighted voting system. The weights of its 188 members are determined by a fixed amount of basic votes plus some extra votes for so-called Special Drawing Rights (SDR). On January 26, 2016, the conditions for the SDRs were increased at the 14th General Quota Review, which drastically changed the corresponding voting weights. However, since the share of voting weights in general is not equal to the influence, of a committee member on the committees overall decision, so-called power indices were introduced. So far the power distribution of the IMF was only computed by either approximation procedures or smaller games than then entire Board of Governors consisting of 188 members. We improve existing algorithms, based on dynamic programming, for the computation of power indices and provide the exact results for the IMF Board of Governors before and after the increase of voting weights. Tuned low-level details of the algorithms allow the repeated routine with sparse computational resources and can of course be applied to other large voting bodies. It turned out that the Banzhaf power shares are rather sensitive to changes of the quota.
This paper studies the complexity of computing a representation of a simple game as the intersection (union) of weighted majority games, as well as, the dimension or the codimension. We also present some examples with linear dimension and exponential codimension with respect to the number of players.
A partial $(k-1)$-spread in $\operatorname{PG}(n-1,q)$ is a collection of $(k-1)$-dimensional subspaces with trivial intersection, i.e., each point is covered at most once. So far the maximum size of a partial $(k-1)$-spread in $\operatorname{PG}(n-1,q)$ was known for the cases $n\equiv 0\pmod k$, $n\equiv 1\pmod k$ and $n\equiv 2\pmod k$ with the additional requirements $q=2$ and $k=3$. We completely resolve the case $n\equiv 2\pmod k$ for the binary case $q=2$.
Voting is a commonly applied method for the aggregation of the preferences of multiple agents into a joint decision. If preferences are binary, i.e., "yes" and "no", every voting system can be described by a (monotone) Boolean function $χ\colon\{0,1\}^n\rightarrow \{0,1\}$. However, its naive encoding needs $2^n$ bits. The subclass of threshold functions, which is sufficient for homogeneous agents, allows a more succinct representation using $n$ weights and one threshold. For heterogeneous agents, one can represent $χ$ as an intersection of $k$ threshold functions. Taylor and Zwicker have constructed a sequence of examples requiring $k\ge 2^{\frac{n}{2}-1}$ and provided a construction guaranteeing $k\le {n\choose {\lfloor n/2\rfloor}}\in 2^{n-o(n)}$. The magnitude of the worst-case situation was thought to be determined by Elkind et al.~in 2008, but the analysis unfortunately turned out to be wrong. Here we uncover a relation to coding theory that allows the determination of the minimum number $k$ for a subclass of voting systems. As an application, we give a construction for $k\ge 2^{n-o(n)}$, i.e., there is no gain from a representation complexity point of view.
The number of essentially different square polyominoes of order n and minimum perimeter p(n) is enumerated.
We examine the determinants of the EU budget expenditures allocation among different countries. In line with earlier literature, we consider two alternative explanations for the EU budget distribution: political power vs. needs view. Extending the original data set from Kauppi and Widgrén (2004), we analyze the robustness of their predictions when applying a different measure of power and more sophisticated econometric techniques. We conclude that the nucleolus is a good alternative to the Shapley-Shubik index in distributive situations such as the case of EU budget allocation. Our results also show that when explaining budget shares, the relative weight of political power based on the nucleolus is lower than the predictions of previous studies based on the Shapley-Shubik index.
We study the optimal control problem of minimizing the convergence time in the discrete Hegselmann--Krause model of opinion dynamics. The underlying model is extended with a set of strategic agents that can freely place their opinion at every time step. Indeed, if suitably coordinated, the strategic agents can significantly lower the convergence time of an instance of the Hegselmann--Krause model. We give several lower and upper worst-case bounds for the convergence time of a Hegselmann--Krause system with a given number of strategic agents, while still leaving some gaps for future research.
Opinion dynamics is nowadays a very common field of research. In this article we formulate and then study a novel, namely strategic perspective on such dynamics: There are the usual normal agents that update their opinions, for instance according the well-known bounded confidence mechanism. But, additionally, there is at least one strategic agent. That agent uses opinions as freely selectable strategies to get control on the dynamics: The strategic agent of our benchmark problem tries, during a campaign of a certain length, to influence the ongoing dynamics among normal agents with strategically placed opinions (one per period) in such a way, that, by the end of the campaign, as much as possible normals end up with opinions in a certain interval of the opinion space. Structurally, such a problem is an optimal control problem. That type of problem is ubiquitous. Resorting to advanced and partly non-standard methods for computing optimal controls, we solve some instances of the campaign problem. But even for a very small number of normal agents, just one strategic agent, and a ten-period campaign length, the problem turns out to be extremely difficult. Explicitly we discuss moral and political concerns that immediately arise, if someone starts to analyze the possibilities of an optimal opinion control.
It is shown that the maximal size of a $2$-arc in the projective Hjelmslev plane over $\mathbb{Z}_{25}$ is $21$, and the $(21,2)$-arc is unique up to isomorphism. Furthermore, all maximal $(20,2)$-arcs in the affine Hjelmslev plane over $\mathbb{Z}_{25}$ are classified up to isomorphism.
We consider 3-regular planar matchstick graphs, i.e. those which have a planar embedding such that all edge lengths are equal, with given girth g. For girth 3 it is known that such graphs exist if and only if the number of vertices n is an even integer larger or equal to 8. Here we prove that such graphs exist for girth g=4 if and only if n is even and at least 20. We provide an example for girth g=5 consisting of 180 vertices.
We perform an exhaustive search for the minimum 4-regular unit distance graph resulting in a lower bound of 34 vertices.
We consider a fashion discounter that supplies any of its many branches with an integral multiple of lots whose size assortment structure stems from a set of many applicable lot-types. We design a column generation algorithm for the optimal approximation of the branch and size dependent demand by a supply using a bounded number of lot-types.
We consider point sets in $\mathbb{Z}_n^2$ where no three points are on a line - also called caps or arcs. For the determination of caps with maximum cardinality and complete caps with minimum cardinality we provide integer linear programming formulations and identify some values for small $n$.
Important decisions are likely made by groups of agents. Thus group decision making is very common in practice. Very transparent group aggregating rules are given by weighted voting, where each agent is assigned a weight. Here a proposal is accepted if the sum of the weights of the supporting agents meets or exceeds a given quota. We study a more general class of binary voting systems -- complete simple games -- and propose an algorithm to determine which sub classes, parameterized by the agent's type composition, are weighted.
We apply competitive analysis onto the problem of minimizing the number of queries to an oracle to completely reconstruct a given monotone Boolean function. Besides lower and upper bounds on the competitivity we determine optimal deterministic online algorithms for the smallest problem instances.
For several years, students visit us on different occasions at the university. But how to bridge from the school curriculum to the contents of the university mathematics? And how to find a focal point at which an active contribute, despite the lack of knowledge, in view of limited time is possible? Our approach: Translate,under guidance, everyday life optimization problems into the language of mathematics, i.e. using variables, target functions, equations and inequalities. These so-called integer linear programming models are then solved by standard software. In this report we wnat to tell about the lessons we have learned.
Fashion discounters face the problem of ordering the right amount of pieces in each size of a product. The product is ordered in pre-packs containing a certain size-mix of a product. For this so-called lot-type design problem, a stochastic mixed integer linear programm was developed, in which price cuts serve as recourse action for oversupply. Our goal is to answer the question, whether the resulting supply strategy leads to a supply that is significantly more consistent with the demand for sizes compared to the original manual planning. Since the total profit is influenced by too many factors unrelated to sizes (like the popularity of the product, the weather or a changing economic situation), we suggest a comparison method which excludes many outer effects by construction. We apply the method to a real-world field study: The improvements in the size distributions of the supply are significant.
We study criteria attesting that a given graph can not be embedded in the plane so that neighboring vertices are at unit distance apart and the straight line edges do not cross.
We consider a setting where one has to organize one or several group activities for a set of agents. Each agent will participate in at most one activity, and her preferences over activities depend on the number of participants in the activity. The goal is to assign agents to activities based on their preferences. We put forward a general model for this setting, which is a natural generalization of anonymous hedonic games. We then focus on a special case of our model, where agents' preferences are binary, i.e., each agent classifies all pairs of the form "(activity, group size)" into ones that are acceptable and ones that are not. We formulate several solution concepts for this scenario, and study them from the computational point of view, providing hardness results for the general case as well as efficient algorithms for settings where agents' preferences satisfy certain natural constraints.
Hegselmann and Krause introduced a discrete-time model of opinion dynamics with agents having limit confidence. It is well known that the dynamics reaches a stable state in a polynomial number of time steps. However, the gap between the known lower and upper bounds for the worst case is still immense. In this paper exact values for the maximum time, needed to reach consensus or to discover that consensus is impossible, are determined for small number of agents using an integer linear programming approach.
We consider point sets in the $m$-dimensional affine space $\mathbb{F}_q^m$ where each squared Euclidean distance of two points is a square in $\mathbb{F}_q$. It turns out that the situation in $\mathbb{F}_q^m$ is rather similar to the one of integral distances in Euclidean spaces. Therefore we expect the results over finite fields to be useful for the Euclidean case. We completely determine the automorphism group of these spaces which preserves integral distances. For some small parameters $m$ and $q$ we determine the maximum cardinality $\mathcal{I}(m,q)$ of integral point sets in $\mathbb{F}_q^m$. We provide upper bounds and lower bounds on $\mathcal{I}(m,q)$. If we map integral distances to edges in a graph, we can define a graph $\mathfrak{G}_{m,q}$ with vertex set $\mathbb{F}_q^m$. It turns out that $\mathfrak{G}_{m,q}$ is strongly regular for some cases.
We study open sets $\mathcal{P}$ in normed spaces $X$ attaining a large volume while avoiding pairs of points at integral distance. The proposed task is to find sharp inequalities for the maximum possible $d$-dimensional volume. This problem can be viewed as an opposite to known problems on point sets with pairwise integral or rational distances.
Motivated by integral point sets in the Euclidean plane, we consider integral point sets in affine planes over finite fields. An integral point set is a set of points in the affine plane $\mathbb{F}_q^2$ over a finite field $\mathbb{F}_q$, where the formally defined squared Euclidean distance of every pair of points is a square in $\mathbb{F}_q$. It turns out that integral point sets over $\mathbb{F}_q$ can also be characterized as affine point sets determining certain prescribed directions, which gives a relation to the work of Blokhuis. Furthermore, in one important sub-case integral point sets can be restated as cliques in Paley graphs of square order. In this article we give new results on the automorphisms of integral point sets and classify maximal integral point sets over $\mathbb{F}_q$ for $q\leq 47$. Furthermore, we give two series of maximal integral point sets and prove their maximality.
Motivated by integral point sets in the Euclidean plane, we consider integral point sets in affine planes over finite fields. An integral point set is a set of points in the affine plane $\mathbb{F}_q^2$ over a finite field $\mathbb{F}_q$, where the formally defined squared Euclidean distance of every pair of points is a square in $\mathbb{F}_q$. It turns out that integral point sets over $\mathbb{F}_q$ can also be characterized as affine point sets determining certain prescribed directions, which gives a relation to the work of Blokhuis. Furthermore, in one important sub-case integral point sets can be restated as cliques in Paley graphs of square order. In this article we give new results on the automorphisms of integral point sets and classify maximal integral point sets over $\mathbb{F}_q$ for $q\le 47$. Furthermore, we give two series of maximal integral point sets and prove their maximality.
We consider the well-known one dimensional cutting stock problem (1CSP). Based on the pattern structure of the classical ILP formulation of Gilmore and Gomory, we can decompose the infinite set of 1CSP instances, with a fixed demand n, into a finite number of equivalence classes. We show up a strong relation to weighted simple games. Studying the integer round-up property we computationally show that all 1CSP instances with $n\le 9$ are proper IRUP, while we give examples of a proper non-IRUP instances with $n=10$. A gap larger than 1 occurs for $n=11$. The worst known gap is raised from 1.003 to 1.0625. The used algorithmic approaches are based on exhaustive enumeration and integer linear programming. Additionally we give some theoretical bounds showing that all 1CSP instances with some specific parameters have the proper IRUP.
Power index research has been a very active field in the last decades. Will this continue or are all the important questions solved? We argue that there are still many opportunities to conduct useful research with and on power indices. Positive and normative questions keep calling for theoretical and empirical attention. Technical and technological improvements are likely to boost applicability.
A graph $G=(V,E)$ is called a unit-distance graph in the plane if there is an injective embedding of $V$ in the plane such that every pair of adjacent vertices are at unit distance apart. If additionally the corresponding edges are non-crossing and all vertices have the same degree $r$ we talk of a regular matchstick graph. Due to Euler's polyhedron formula we have $r\le 5$. The smallest known $4$-regular matchstick graph is the so called Harborth graph consisting of $52$ vertices. In this article we prove that no finite $5$-regular matchstick graph exists.
We describe several algorithms for the generation of integer Heronian triangles with diameter at most $n$. Two of them have running time $\mathcal{O}\left(n^{2+\varepsilon}\right)$. We enumerate all integer Heronian triangles for $n\le 600000$ and apply the complete list on some related problems.
We give an elementary proof of a conjecture by Hegselmann and Krause in opinion dynamics, concerning a symmetric bounded confidence interval model: If there is a truth and all individuals take each other seriously by a positive amount bounded away from zero, then all truth seekers will converge to the truth. Here truth seekers are the individuals which are attracted by the truth by a positive amount. In the absence of truth seekers it was already shown by Hegselmann and Krause that the opinions of the individuals converge.
It is shown that the maximum size of a binary subspace code of packet length $v=6$, minimum subspace distance $d=4$, and constant dimension $k=3$ is $M=77$; in Finite Geometry terms, the maximum number of planes in $\operatorname{PG}(5,2)$ mutually intersecting in at most a point is $77$. Optimal binary $(v,M,d;k)=(6,77,4;3)$ subspace codes are classified into $5$ isomorphism types, and a computer-free construction of one isomorphism type is provided. The construction uses both geometry and finite fields theory and generalizes to any $q$, yielding a new family of $q$-ary $(6,q^6+2q^2+2q+1,4;3)$ subspace codes.
The design of fair voting rules has been addressed quite often in the literature. Still, the so-called inverse problem is not entirely resolved. We summarize some achievements in this direction and formulate explicit open questions and conjectures.
We consider so-called squaring the square-puzzles where a given square (or rectangle) should be dissected into smaller squares. For a specific instance of such problems we demonstrate that a mathematically rigorous solution can be quite involved. As an alternative to exhaustive enumeration using tailored algorithms we describe the general approach of formulating the problem as an integer linear program.
For the classical power indices there is a disproportion between power and relative weights, in general. We introduce two new indices, based on weighted representations, which are proportional to suitable relative weights and which also share several important properties of the classical power indices. Imposing further restrictions on the set of representations may lead to a whole family of such indices.
We consider the problem of approximating the branch and size dependent demand of a fashion discounter with many branches by a distributing process being based on the branch delivery restricted to integral multiples of lots from a small set of available lot-types. We propose a formalized model which arises from a practical cooperation with an industry partner. Besides an integer linear programming formulation we provide an appropriate primal heuristic for this problem.
Manfred Holler introduced the Public Good index as a proposal to divide a public good among players. In its unnormalized version, i.e., the raw measure, it counts the number of times that a player belongs to a minimal winning coalition. Unlike the Banzhaf index, it does not count the remaining winning coalitions in which the player is crucial. Holler noticed that his index does not satisfy local monotonicity, a fact that can be seen either as a major drawback or as an advantage.
Some distinguished types of voters, as vetoers, passers or nulls, as well as some others, play a significant role in voting systems because they are either the most powerful or the least powerful voters in the game independently of the measure used to evaluate power. In this paper we are concerned with the design of voting systems with at least one type of these extreme voters and with few types of equivalent voters, with this purpose in mind we enumerate these special classes of games and find out that its number always follows a Fibonacci sequence with smooth polynomial variations. As a consequence we find several families of games with the same asymptotic exponential behavior excepting of a multiplicative factor which is the golden number or its square. From a more general point of view, our studies are related with the design of voting structures with a predetermined importance ranking.
We present the Integrated Size and Price Optimization Problem (ISPO) for a fashion discounter with many branches. Based on a two-stage stochastic programming model with recourse, we develop an exact algorithm and a production-compliant heuristic that produces small optimality gaps. In a field study we show that a distribution of supply over branches and sizes based on ISPO solutions is significantly better than a one-stage optimization of the distribution ignoring the possibility of optimal pricing.
Several power indices have been introduced in the literature in order to measure the influence of individual committee members on the aggregated decision. Here we ask the inverse question and aim to design voting rules for a committee such that a given desired power distribution is met as closely as possible. We present an exact algorithm for a large class of different power indices based on integer linear programming. With respect to negative approximation results we generalize the approach of Alon and Edelman who studied power distributions for the Banzhaf index, where most of the power is concentrated on few coordinates. It turned out that each Banzhaf vector of an n-member committee that is near to such a desired power distribution, has to be also near to the Banzhaf vector of a k-member committee. We show that such Alon-Edelman type results are possible for other power indices like e.g. the Public Good index or the Coleman index to prevent actions, while they are principally impossible for e.g. the Johnston index.
Incorporating fairness criteria in optimization problems comes at a certain cost, which is measured by the so-called price of fairness. Here we consider the allocation of indivisible goods. For envy-freeness as fairness criterion it is known from literature that the price of fairness can increase linearly in terms of the number of agents. For the constructive lower bound a quadratic number of items was used. In practice this might be inadequately large. So we introduce the price of fairness in terms of both the number of agents and items, i.e., key parameters which generally may be considered as common and available knowledge. It turned out that the price of fairness increases sublinear if the number of items is not too much larger than the number of agents. For the special case of coincide of both counts exact asymptotics could be determined. Additionally an efficient integer programming formulation is given.
This paper is a twofold contribution. First, it contributes to the problem of enumerating some classes of simple games and in particular provides the number of weighted games with minimum and the number of weighted games for the dual class as well. Second, we focus on the special case of bipartite complete games with minimum, and we compare and rank these games according to the behavior of some efficient power indices of players of type 1 (or of type 2). The main result of this second part establishes all allowable rankings of these games when the Shapley-Shubik power index is used on players of type 1.
Classical power index analysis considers the individual's ability to influence the aggregated group decision by changing its own vote, where all decisions and votes are assumed to be binary. In many practical applications we have more options than either "yes" or "no". Here we generalize three important power indices to continuous convex policy spaces. This allows the analysis of a collection of economic problems like e.g. tax rates or spending that otherwise would not be covered in binary models.
We study minimum integer representations of weighted games, i.e., representations where the weights are integers and every other integer representation is at least as large in each component. Those minimum integer representations, if the exist at all, are linked with some solution concepts in game theory. Closing existing gaps in the literature, we prove that each weighted game with two types of voters admits a (unique) minimum integer representation, and give new examples for more than two types of voters without a minimum integer representation. We characterize the possible weights in minimum integer representations and give examples for $t\ge 4$ types of voters without a minimum integer representation preserving types, i.e., where we additionally require that the weights are equal within equivalence classes of voters.
We study open point sets in Euclidean spaces $\mathbb{R}^d$ without a pair of points an integral distance apart. By a result of Furstenberg, Katznelson, and Weiss such sets must be of Lebesgue upper density zero. We are interested in how large such sets can be in $d$-dimensional volume. We determine the lower and upper bounds for the volumes of the sets in terms of the number of their connected components and dimension, and also give some exact values. Our problem can be viewed as a kind of inverse to known problems on sets with pairwise rational or integral distances.
Power indices are mappings that quantify the influence of the members of a voting body on collective decisions a priori. Their nonlinearity and discontinuity makes it difficult to compute inverse images, i.e., to determine a voting system which induces a power distribution as close as possible to a desired one. This paper considers approximations and exact solutions to this inverse problem for the Penrose-Banzhaf index, which are obtained by enumeration and integer linear programming techniques. They are compared to the results of three simple solution heuristics. The heuristics perform well in absolute terms but can be improved upon very considerably in relative terms. The findings complement known asymptotic results for large voting bodies and may improve termination criteria for local search algorithms.
Gvozdeva, Hemaspaandra, and Slinko (2011) have introduced three hierarchies for simple games in order to measure the distance of a given simple game to the class of (roughly) weighted voting games. Their third class $\mathcal{C}_α$ consists of all simple games permitting a weighted representation such that each winning coalition has a weight of at least 1 and each losing coalition a weight of at most $α$. For a given game the minimal possible value of $α$ is called its critical threshold value. We continue the work on the critical threshold value, initiated by Gvozdeva et al., and contribute some new results on the possible values for a given number of voters as well as some general bounds for restricted subclasses of games. A strong relation beween this concept and the cost of stability, i.e. the minimum amount of external payment to ensure stability in a coalitional game, is uncovered.
Voters from m disjoint constituencies (regions, federal states, etc.) are represented in an assembly which contains one delegate from each constituency and applies a weighted voting rule. All agents are assumed to have single-peaked preferences over an interval; each delegate's preferences match his constituency's median voter; and the collective decision equals the assembly's Condorcet winner. We characterize the asymptotic behavior of the probability of a given delegate determining the outcome (i.e., being the weighted median of medians) in order to address a contentious practical question: which voting weights w_1, ..., w_m ought to be selected if constituency sizes differ and all voters are to have a priori equal influence on collective decisions? It is shown that if ideal point distributions have identical median M and are suitably continuous, the probability for a given delegate i's ideal point λ_i being the Condorcet winner becomes asymptotically proportional to i's voting weight w_i times λ_i's density at M as $m\to \infty$. Indirect representation of citizens is approximately egalitarian for weights proportional to the square root of constituency sizes if all individual ideal points are i.i.d. In contrast, weights that are linear in-- or, better, induce a Shapley value linear in-- size are egalitarian when preferences are sufficiently strongly affiliated within constituencies.
Weighted voting games are frequently used in decision making. Each voter has a weight and a proposal is accepted if the weight sum of the supporting voters exceeds a quota. One line of research is the efficient computation of so-called power indices measuring the influence of a voter. We treat the inverse problem: Given an influence vector and a power index, determine a weighted voting game such that the distribution of influence among the voters is as close as possible to the given target value. We present exact algorithms and computational results for the Shapley-Shubik and the (normalized) Banzhaf power index.
We combine the parametric Barvinok algorithm with a generation algorithm for a finite list of suitably chosen discrete sub-cases on the enumeration of complete simple games, i.e. a special subclass of monotone Boolean functions. Recently, Freixas et al. have proven an enumeration formula for complete simple games with two types of voters. We will provide a shorter proof and an enumeration formula for complete simple games with two shift-minimal winning coalitions.
We propose the new Top-Dog-Index, a measure for the branch-dependent historic deviation of the supply data of apparel sizes from the sales data of a fashion discounter. A common approach is to estimate demand for sizes directly from the sales data. This approach may yield information for the demand for sizes if aggregated over all branches and products. However, as we will show in a real-world business case, this direct approach is in general not capable to provide information about each branch's individual demand for sizes: the supply per branch is so small that either the number of sales is statistically too small for a good estimate (early measurement) or there will be too much unsatisfied demand neglected in the sales data (late measurement). Moreover, in our real-world data we could not verify any of the demand distribution assumptions suggested in the literature. Our approach cannot estimate the demand for sizes directly. It can, however, individually measure for each branch the scarcest and the amplest sizes, aggregated over all products. This measurement can iteratively be used to adapt the size distributions in the pre-pack orders for the future. A real-world blind study shows the potential of this distribution free heuristic optimization approach: The gross yield measured in percent of gross value was almost one percentage point higher in the test-group branches than in the control-group branches.