1,721,263 research outputs found
Manipulability of Single Transferable Vote
Full text linkFor many voting rules, it is NP-hard to compute a successful manipulation.
However, NP-hardness only bounds the worst-case complexity. Recent
theoretical results suggest that manipulation may often be easy in practice. We
study empirically the cost of manipulating the single transferable vote (STV) rule. This was one of the first rules shown to be NP-hard to manipulate. It also appears to be one of the harder rules to manipulate since it involves multiple rounds and since, unlike many other rules, it is NP-hard for a single agent to manipulate without weights on the votes or uncertainty about how the other agents have voted. In almost every election in our experiments, it was easy to compute how a single agent could manipulate the election or to prove that manipulation by a single agent was impossible. It remains an interesting open question if manipulation by a coalition of agents is hard to compute in practice
Aggregating partially ordered preferences
No full textPreferences are not always expressible via complete linear orders: some-
times it is more natural to allow for the presence of incomparable outcomes. This
may hold both in the agents' preference ordering and in the social order. In this
paper we consider this scenario and we study what properties it may have. In par-
ticular, we show that, despite the added expressivity and ability to resolve con
icts
provided by incomparability, classical impossibility results (such as Arrow's theorem,
Muller-Satterthwaite's theorem, and Gibbard-Satterthwaite's theorem) still hold. We
also prove some possibility results, generalizing Sen's theorem for majority voting.
To prove these results, we dene new notions of unanimity, monotonicity, dictator,
triple-wise value-restriction, and strategy-proofness, which are suitable and natural
generalizations of the classical ones for complete orders
Abstract Proof Checking: An Example Motivated by an Incompleteness Theorem
No full textWe demonstrate the use of abstraction in aiding the construction of an interesting and difficult example in a proof checking system. This experiment demonstrates that abstraction can make proofs easier to comprehend and to verify mechanically. To support such proof checking, we have developed a formal theory of abstraction and added facilities for using abstraction to the GETFOL proof checking system
A Framework for Combining Set Variable Representations
No full textSet and multiset variables are important modelling constructs in constraint programming. Several representations have been proposed for set and multiset variables, often based on combining together different representations. In this paper, we provide a formal framework with which we can study many existing combinations of representations and compare their strength. In addition, our framework opens the door to interesting new combinations, as well as to the construction of propagators with well defined properties. We illustrate the value of the framework via both theoretical and experimental results
Does a New Simple Gaussian Weighting Approach Perform Well in Text Categorization?
No full textA new approach to the Text Categorization problem is here presented. It is called Gaussian Weighting and it is a supervised learning algorithm that, during the training phase, estimates two very simple and easily computable statistics which are: the Presence \emph{P}, how much a term \emph{t} is present in a category \emph{c}; the Expressiveness \emph{E}, how much \emph{t} is present outside \emph{c} in the rest of the domain. Once the system has learned this information, a Gaussian function is shaped for each term of a category, in order to assign the term a weight that estimates the level of its importance for that particular category. We tested our learning method on the task of single-label classification using the Reuters-21578 benchmark. The outcome of the result was quite impressive: in different experimental setups, we reached a micro-averaged F1-measure of 0.89, with a peak of 0.899. Moreover, a macro-averaged Recall and Precision was calculated: the former reported a 0.72, the latter a 0.79. These results reach most of the state-of-the-art techniques of machine learning applied to Text Categorization, demonstrating that this new weighting scheme does perform well on this particular task
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
- …
