Finding Optimal Solutions for Voting Game Design Problems
Authors: B. de Keijzer, T. B. Klos, Y. Zhang
JAIR 2014 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We implement this algorithm to find a weighted voting game with a normalized Banzhaf power distribution closest to a target power index, and perform experiments to obtain some insights about the set of weighted voting games. We remark that our algorithm is applicable to optimizing any exponential-time computable function, the distance of the normalized Banzhaf index to a target power index is merely taken as an example. ... In Section 5, we report on some experiments we performed with an implementation of our main algorithm, and Section 6 concludes the paper. |
| Researcher Affiliation | Academia | Bart de Keijzer EMAIL Web Algorithmics and Data Mining, Sapienza Universit a di Roma, Rome, Italy; Tomas B. Klos EMAIL Algorithmics; Delft University of Technology, Delft, The Netherlands; Yingqian Zhang EMAIL Department of Econometrics; Erasmus University Rotterdam, Rotterdam, The Netherlands |
| Pseudocode | Yes | Algorithm 1 gives the pseudocode for this enumeration method. The array element games[i] will be the list of canonical weighted voting games that have i minimal winning coalitions; the rank-i games. The value of i can not exceed n n/2 by Sperner s Theorem. The games are represented as lists of minimal winning coalitions. The algorithm iterates from every new game found, starting with the game in games[0], with zero minimal winning coalitions. |
| Open Source Code | No | The paper does not provide a direct link to a source code repository, an explicit statement of code release for the methodology described, or mention of code in supplementary materials. |
| Open Datasets | No | For n between 1 and 7, we computed for 1000 random instances the average optimal error. That is, the average error that is attained out of 1000 random instances (i.e., uniform random vectors in the (n 1)-dimensional unit-simplex restricted to the non-increasingness constraint) when the algorithm is allowed to run to completion on these instances. The paper uses generated 'random instances' rather than a specific, pre-existing public dataset, and no access information for any dataset is provided. |
| Dataset Splits | No | The paper uses generated 'random instances' and does not describe the use of any traditional datasets with training, test, or validation splits. No specific dataset split information is provided. |
| Hardware Specification | No | The paper does not explicitly describe the hardware (e.g., specific CPU or GPU models, memory, or cloud resources) used to run its experiments. |
| Software Dependencies | No | The programming language we used is C. Execution of the algorithm involves solving a large number of linear programs. To to this, we made use of the GNU Linear Programming Toolkit (see Makhorin, 2004). The paper mentions 'C' and 'GNU Linear Programming Toolkit' but does not specify version numbers for these software components. |
| Experiment Setup | Yes | Our implementation solves the normalized Banzhaf index weighted voting game design problem. This means that for each weighted voting game that is output by our enumeration algorithm, we must invoke a procedure for computing the normalized Banzhaf index. The algorithm used for this is simply the naive brute-force approach. (In our experiments, the runtime with Banzhaf computation (to three decimal places) is only different from the runtime without it for four players or more. Up to eight players, including computation of the Banzhaf indices never increases the runtime by more than 0.6%.) ... For n between 1 and 7, we computed for 1000 random instances the average optimal error. ... The error function we used is the square root of the sum of squared errors. |