You have just completed your registration at OpenAire.
Before you can login to the site, you will need to activate your account.
An e-mail will be sent to you with the proper instructions.
Important!
Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version
of the site upon release.
Schulze's rule is used in the elections of a large number of organizations including Wikimedia and Debian. Part of the reason for its popularity is the large number of axiomatic properties, like monotonicity and Condorcet consistency, which it satisfies. We identify a potential shortcoming of Schulze's rule: it is computationally vulnerable to manipulation. In particular, we prove that computing an unweighted coalitional manipulation (UCM) is polynomial for any number of manipulators. This re...
We give an analog of the Myhill-Nerode methods from formal language theory for hypergraphs and use it to derive the following results for two NP-hard hypergraph problems: * We provide an algorithm for testing whether a hypergraph has cutwidth at most k that runs in linear time for constant k. In terms of parameterized complexity theory, the problem is fixed-parameter linear parameterized by k. * We show that it is not expressible in monadic second-order logic whether a hypergraph has bounded ...
The probabilistic serial (PS) rule is a prominent randomized rule for assigning indivisible goods to agents. Although it is well known for its good fairness and welfare properties, it is not strategyproof. In view of this, we address several fundamental questions regarding equilibria under PS. Firstly, we show that Nash deviations under the PS rule can cycle. Despite the possibilities of cycles, we prove that a pure Nash equilibrium is guaranteed to exist under the PS rule. We then show that ...
Social networks are increasingly being used to conduct polls. We introduce a simple model of such social polling. We suppose agents vote sequentially, but the order in which agents choose to vote is not necessarily fixed. We also suppose that an agent's vote is influenced by the votes of their friends who have already voted. Despite its simplicity, this model provides useful insights into a number of areas including social polling, sequential voting, and manipulation. We prove that the number...
The probabilistic serial (PS) rule is one of the most prominent randomized rules for the assignment problem. It is well-known for its superior fairness and welfare properties. However, PS is not immune to manipulative behaviour by the agents. We initiate the study of the computational complexity of an agent manipulating the PS rule. We show that computing an expected utility better response is NP- hard. On the other hand, we present a polynomial-time algorithm to compute a lexicographic best ...
We study computational aspects of three prominent voting rules that use approval ballots to elect multiple winners. These rules are satisfaction approval voting, proportional approval voting, and reweighted approval voting. We first show that computing the winner for proportional approval voting is NP-hard, closing a long standing open problem. As none of the rules are strategyproof, even for dichotomous preferences, we study various strategic aspects of the rules. In particular, we examine t...
We consider the largest number of minimal separators a graph on n vertices can have at most. We give a new proof that this number is in $O( ((1+\sqrt{5})/2)^n n )$. We prove that this number is in $\omega( 1.4521^n )$, improving on the previous best lower bound of $\Omega(3^{n/3}) \subseteq \omega( 1.4422^n )$. This gives also an improved lower bound on the number of potential maximal cliques in a graph. We would like to emphasize that our proofs are short, simple, and elementary.
We show a method resulting in the improvement of several polynomial-space, exponential-time algorithms. An instance of the problem Max (r,2)-CSP, or simply Max 2-CSP, is parametrized by the domain size r (often 2), the number of variables n (vertices in the constraint graph G), and the number of constraints m (edges in G). When G is cubic, and omitting sub-exponential terms here for clarity, we give an algorithm running in time r^((1/5)n) = r^((2/15)m); the previous best was r^((1/4)n) = r^((...
We present a first theoretical analysis of the power of polynomial-time preprocessing for important combinatorial problems from various areas in AI. We consider problems from Constraint Satisfaction, Global Constraints, Satisfiability, Nonmonotonic and Bayesian Reasoning under structural restrictions. All these problems involve two tasks: (i) identifying the structure in the input as required by the restriction, and (ii) using the identified structure to solve the reasoning task efficiently. ...
Local Search is one of the fundamental approaches to combinatorial optimization and it is used throughout AI. Several local search algorithms are based on searching the k-exchange neighborhood. This is the set of solutions that can be obtained from the current solution by exchanging at most k elements. As a rule of thumb, the larger k is, the better are the chances of finding an improved solution. However, for inputs of size n, a na\"ive brute-force search of the k-exchange neighborhood requi...
No project research data found
No project statistics found
Scientific Results
Chart is loading... It may take a bit of time. Please be patient and don't reload the page.
PUBLICATIONS BY ACCESS MODE
Chart is loading... It may take a bit of time. Please be patient and don't reload the page.
Publications in Repositories
Chart is loading... It may take a bit of time. Please be patient and don't reload the page.