English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the inverse power index problem for weighted voting games: theproblem of finding a weighted voting game in which the power of the players isas close as possible to a certain target distribution. Our goal is to findalgorithms that solve this problem exactly. Thereto, we study varioussubclasses of simple games, and their associated representation methods. Wesurvey algorithms and impossibility results for the synthesis problem, i.e.,converting a representation of a simple game into another representation.  We contribute to the synthesis problem by showing that it is impossible tocompute in polynomial time the list of ceiling coalitions (also known asshift-maximal losing coalitions) of a game from its list of roof coalitions(also known as shift-minimal winning coalitions), and vice versa.  Then, we proceed by studying the problem of enumerating the set of weightedvoting games. We present first a naive algorithm for this, running in doublyexponential time. Using our knowledge of the synthesis problem, we then improveon this naive algorithm, and we obtain an enumeration algorithm that runs inquadratic exponential time (that is, O(2^(n^2) p(n)) for a polynomial p).Moreover, we show that this algorithm runs in output-polynomial time, making itthe best possible enumeration algorithm up to a polynomial factor.  Finally, we propose an exact anytime algorithm for the inverse power indexproblem that runs in exponential time. This algorithm is straightforward andgeneral: it computes the error for each game enumerated, and outputs the gamethat minimizes this error. By the genericity of our approach, our algorithm canbe used to find a weighted voting game that optimizes any exponential timecomputable function. We implement our algorithm for the case of the normalizedBanzhaf index, and we perform experiments in order to study performance anderror convergence.

Solving Weighted Voting Game Design Problems Optimally: Representations, Synthesis, and Enumeration