1,721,103 research outputs found
Manipulating the Quota in Weighted Voting Games
No full textWeighted voting games provide a popular model of decision making in multiagent systems. Such games are described by a set of players, a list of players' weights, and a quota; a coalition of the players is said to be winning if the total weight of its members meets or exceeds the quota. The power of a player in such games is traditionally identified with her Shapley--Shubik index or her Banzhaf index, two classical power measures that reflect the player's marginal contributions under different coalition formation scenarios. In this paper, we investigate by how much the central authority can change a player's power, as measured by these indices, by modifying the quota. We provide tight upper and lower bounds on the changes in the individual player's power that can result from a change in quota. We also study how the choice of quota can affect the relative power of the players. From the algorithmic perspective, we provide an efficient algorithm for determining whether there is a value of the quota that makes a given player a {\em dummy}, i.e., reduces his power (as measured by both indices) to 0. On the other hand, we show that checking which of the two values of the quota makes this player more powerful is computationally hard, namely, complete for the complexity class PP, which is believed to be significantly more powerful than NP
Constrained coalition formation
No full textThe conventional model of coalition formation considers every possible subset of agents as a potential coalition. However, in many real-world applications, there are inherent constraints on feasible coalitions: for instance, certain agents may be prohibited from being in the same coalition, or the coalition structure may be required to consist of coalitions of the same size. In this paper, we present the first systematic study of constrained coalition formation (CCF). We propose a general framework for this problem, and identify an important class of CCF settings, where the constraints specify which groups of agents should/should not work together. We describe a procedure that transforms such constraints into a structured input that allows coalition formation algorithms to identify, without any redundant computations, all the feasible coalitions. We then use this procedure to develop an algorithm for generating an optimal (welfare-maximizing) constrained coalition structure, and show that it outperforms existing state-of-the-art approaches by several orders of magnitude
The Complexity of Nearly Single-Peaked Consistency
No full textManipulation, bribery, and control are well-studied ways of changing the outcome of an election. Many voting systems are in the general case computationally resistant to some of these manipulative actions. However when restricted to single-peaked electorates, these problems
suddenly become easy to solve. Recently, Faliszewski, Hemaspaandra, and Hemaspaandra [FHH11] studied the complexity of dishonest behavior in nearly single-peaked electorates. These are electorates that are not single-peaked but close to it according to some distance
measure.
In this paper we introduce several new distance measures regarding single-peakedness. We prove that determining whether a given profile is nearly single-peaked is in many cases NPcomplete. Furthermore, we explore the relations between several notions of nearly singlepeakedness
Porovnání výkonu ILP řešičů a logických řešičů na problému úplatků
No full textInteger Linear Programming (ILP) has proven to be a powerful tool for solving hard problems, particularly in computational social choice, where it has been used to address variants of the bribery problem. This problem involves finding the smallest change that results in a desired outcome after opinions diffuse through a society. The ILP solution for this problem has been shown to be experimentally limited to small instances of the problem. Research has shown that such problems can be encoded using logical formulas in Presburger Arithmetic (PrA) matching the complexity of the ILP algo- rithm. Therefore, a practical analysis of the PrA-based approach is called for. In this project, we randomly generate instances with prescribed election parameters and model them as ILP instances and PrA formulas. We use solvers such as GUROBI, GLPK, and Z3 to solve these instances and con- duct a comparative study to evaluate the performance of both approaches under different parameters, such as the number of voter types and diffusion steps. Our results show that the ILP approach is more robust than the PrA approach in practice. 1Celočíselné lineární programování (ILP) se ukázalo být mocným nástro- jem pro řešení obtížných problémů, zejména v oblasti výpočetní sociální volby, kde byl použit k řešení variant problému úplatků. V tomto prob- lému jde o nalezení nejmenší změny, která vede ke kýženému výsledku po- tom, co ve společnosti proběhne proces šíření názorů. Předchozí experimenty ukazují, že řešení tohoto problému pomocí ILP je omezené pouze na malé instance. Novější výsledky ukazují, že tentýž problém lze vyjádřit pomocí logických formulí v Presburgerově aritmetice (PrA) a lze tak dosáhnout složi- tosti podobné algoritmu ILP. Proto se nabízí provést praktickou analýzu přístupu založeného na PrA. V tomto projektu jsme vygenerovali náhodné instance s předepsanými parametry voleb a modelovali je jako instance ILP a PrA. Následně jsme takto získané instance vyřešili pomocí řešičů jako jsou např. GUROBI, GLPK a Z3 a provedli jsme srovnávací studii k vyhodnocení výkonnosti obou přístupů vzhledem k různých parametrům, jako jsou např. počet typů voličů a difúzních kroků. Naše výsledky ukazují, že přístup skrze ILP je v praxi robustnější než přístup PrA. 1Informatický ústav Univerzity KarlovyComputer Science Institute of Charles UniversityFaculty of Mathematics and PhysicsMatematicko-fyzikální fakult
Hiding in Social Networks
Full text linkLink archiwalny https://depotuw.ceon.pl/handle/item/217415209
Performance Comparison of ILP versus Logical Solvers on Bribery-type Problems
No full textInteger Linear Programming (ILP) has proven to be a powerful tool for solving hard problems, particularly in computational social choice, where it has been used to address variants of the bribery problem. This problem involves finding the smallest change that results in a desired outcome after opinions diffuse through a society. The ILP solution for this problem has been shown to be experimentally limited to small instances of the problem. Research has shown that such problems can be encoded using logical formulas in Presburger Arithmetic (PrA) matching the complexity of the ILP algo- rithm. Therefore, a practical analysis of the PrA-based approach is called for. In this project, we randomly generate instances with prescribed election parameters and model them as ILP instances and PrA formulas. We use solvers such as GUROBI, GLPK, and Z3 to solve these instances and con- duct a comparative study to evaluate the performance of both approaches under different parameters, such as the number of voter types and diffusion steps. Our results show that the ILP approach is more robust than the PrA approach in practice.
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Full text linkWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
- …
