Author name cluster

Benny Kimelfeld

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

11 papers

1 author row

AIJ Journal 2025 Journal Article

Approval-based committee voting under incomplete information

Aviram Imber
Jonas Israel
Markus Brill
Benny Kimelfeld

We investigate approval-based committee voting with incomplete information about the approval preferences of voters. We consider several models of incompleteness where each voter partitions the set of candidates into approved , disapproved , and unknown candidates, possibly with ordinal preference constraints among candidates in the latter category. This captures scenarios where voters have not evaluated all candidates and/or it is unknown where voters draw the threshold between approved and disapproved candidates. We study the complexity of some fundamental computational problems for a number of classic approval-based committee voting rules including Proportional Approval Voting and Chamberlin–Courant. These problems include determining whether a given set of candidates is a possible or necessary winning committee and whether a given candidate is possibly or necessarily a member of the winning committee. We also consider proportional representation axioms and the problem of deciding whether a given committee is possibly or necessarily representative.

Details DOI

AAAI Conference 2024 Conference Paper

Accelerating the Global Aggregation of Local Explanations

Alon Mor
Yonatan Belinkov
Benny Kimelfeld

Local explanation methods highlight the input tokens that have a considerable impact on the outcome of classifying the document at hand. For example, the Anchor algorithm applies a statistical analysis of the sensitivity of the classifier to changes in the token. Aggregating local explanations over a dataset provides a global explanation of the model. Such aggregation aims to detect words with the most impact, giving valuable insights about the model, like what it has learned in training and which adversarial examples expose its weaknesses. However, standard aggregation methods bear a high computational cost: a naive implementation applies a costly algorithm to each token of each document, and hence, it is infeasible for a simple user running in the scope of a short analysis session. We devise techniques for accelerating the global aggregation of the Anchor algorithm. Specifically, our goal is to compute a set of top-k words with the highest global impact according to different aggregation functions. Some of our techniques are lossless and some are lossy. We show that for a very mild loss of quality, we are able to accelerate the computation by up to 30 times, reducing the computation from hours to minutes. We also devise and study a probabilistic model that accounts for noise in the Anchor algorithm and diminishes the bias toward words that are frequent yet low in impact.

PDF Details DOI

AAAI Conference 2024 Conference Paper

Spatial Voting with Incomplete Voter Information

Aviram Imber
Jonas Israel
Markus Brill
Hadas Shachnai
Benny Kimelfeld

We consider spatial voting where candidates are located in the Euclidean d-dimensional space, and each voter ranks candidates based on their distance from the voter's ideal point. We explore the case where information about the location of voters' ideal points is incomplete: for each dimension, we are given an interval of possible values. We study the computational complexity of finding the possible and necessary winners for positional scoring rules. Our results show that we retain tractable cases of the classic model where voters have partial-order preferences. Moreover, we show that there are positional scoring rules under which the possible-winner problem is intractable for partial orders, but tractable in the one-dimensional spatial setting. We also consider approval voting in this setting. We show that for up to two dimensions, the necessary-winner problem is tractable, while the possible-winner problem is hard for any number of dimensions.

PDF Details DOI

AAAI Conference 2022 Conference Paper

Approval-Based Committee Voting under Incomplete Information

Aviram Imber
Jonas Israel
Markus Brill
Benny Kimelfeld

We investigate approval-based committee voting with incomplete information about the approval preferences of voters. We consider several models of incompleteness where each voter partitions the set of candidates into approved, disapproved, and unknown candidates, possibly with ordinal preference constraints among candidates in the latter category. This captures scenarios where voters have not evaluated all candidates and/or it is unknown where voters draw the threshold between approved and disapproved candidates. We study the complexity of some fundamental computational problems for a number of classic approval-based committee voting rules including Proportional Approval Voting and Chamberlin–Courant. These problems include that of determining whether a given set of candidates is a possible or necessary winning committee and whether it forms a committee that possibly or necessarily satisfies representation axioms. We also consider the problem whether a given candidate is possibly or necessarily a member of the winning committee.

PDF Details

AAMAS Conference 2021 Conference Paper

Computing the Extremal Possible Ranks with Incomplete Preferences

Aviram Imber
Benny Kimelfeld

Various voting rules are based on ranking the candidates by scores induced by aggregating voter preferences. A winner (respectively, unique winner) is a candidate who receives a score not smaller than (respectively, strictly greater than) the remaining candidates. Examples of such rules include the positional scoring rules and the Bucklin, Copeland, and Maximin rules. When voter preferences are known in an incomplete manner as partial orders, a candidate can be a possible/necessary winner based on the possibilities of completing the partial votes. Past research has studied in depth the computational problems of determining the possible and necessary winners and unique winners. These problems are all special cases of reasoning about the range of possible positions of a candidate under different tiebreakers. We investigate the complexity of determining this range, and particularly the extremal positions. Among our results, we establish that finding each of the minimal and maximal positions is NP-hard for each of the above rules, including all positional scoring rules, pure or not. Hence, none of the tractable variants of necessary/possible winner determination remain tractable for extremal position determination. Tractability can be retained when reasoning about the top-𝑘 positions for a fixed 𝑘. Yet, exceptional is Maximin where it is tractable to decide whether the maximal rank is 𝑘 for 𝑘 = 1 (necessary winning) but it becomes intractable for all 𝑘 > 1.

PDF

AAMAS Conference 2021 Conference Paper

Probabilistic Inference of Winners in Elections by Independent Random Voters

Aviram Imber
Benny Kimelfeld

We investigate the problem of computing the probability of winning in an election where voter attendance is uncertain. More precisely, we study the setting where, in addition to a total ordering of the candidates, each voter is associated with a probability of attending the poll, and the attendances of different voters are probabilistically independent. We show that the probability of winning can be computed in polynomial time for the plurality and veto rules. However, it is computationally hard (#P-hard) for various other rules, including 𝑘-approval and 𝑘-veto for 𝑘 > 1, Borda, Condorcet, and Maximin. For some of these rules, it is even hard to find a multiplicative approximation since it is already hard to determine whether this probability is nonzero. In contrast, we devise a fully polynomial-time randomized approximation scheme (FPRAS) for the complement probability, namely the probability of losing, for every positional scoring rule (with polynomial scores), as well as for the Condorcet rule.

PDF

TCS Journal 2020 Journal Article

Counting and enumerating preferred database repairs

Benny Kimelfeld
Ester Livshits
Liat Peterfreund

In its traditional definition, a repair of an inconsistent database is a consistent database that differs from the inconsistent one in a “minimal way. ” Often, repairs are not equally legitimate, as it is desired to prefer one over another; for example, one fact is regarded more reliable than another, or a more recent fact should be preferred to an earlier one. Motivated by these considerations, researchers have introduced and investigated the framework of preferred repairs, in the context of denial constraints and subset repairs. There, a priority relation between facts is lifted towards a priority relation between consistent databases, and repairs are restricted to the ones that are optimal in the lifted sense. Three notions of lifting (and preferred repairs) have been proposed: Pareto, global, and completion. In this article, we investigate the complexity of three problems on preferred repairs. The first is the problem of deciding whether the priority relation contains enough information to clean the database unambiguously, or in other words, whether there is exactly one preferred repair. We show that the different lifting semantics entail highly different complexities for this problem. Then, we study the ability to quantify ambiguity, by investigating two classes of problems. The first is that of counting the preferred repairs. We establish a dichotomy in data complexity for the entire space of (sets of) functional dependencies for all three notions. The second class of problems is that of enumerating (i. e. , generating) the preferred repairs. We devise enumeration algorithms with efficiency guarantees on the delay between generated repairs, even for constraints represented as general conflict graphs or hypergraphs.

Details DOI

AAAI Conference 2019 Conference Paper

Approximate Inference of Outcomes in Probabilistic Elections

Batya Kenig
Benny Kimelfeld

We study the complexity of estimating the probability of an outcome in an election over probabilistic votes. The focus is on voting rules expressed as positional scoring rules, and two models of probabilistic voters: the uniform distribution over the completions of a partial voting profile (consisting of a partial ordering of the candidates by each voter), and the Repeated Insertion Model (RIM) over the candidates, including the special case of the Mallows distribution. Past research has established that, while exact inference of the probability of winning is computationally hard (#P-hard), an additive polynomial-time approximation (additive FPRAS) is attained by sampling and averaging. There is often, though, a need for multiplicative approximation guarantees that are crucial for important measures such as conditional probabilities. Unfortunately, a multiplicative approximation of the probability of winning cannot be efficient (under conventional complexity assumptions) since it is already NP-complete to determine whether this probability is nonzero. Contrastingly, we devise multiplicative polynomial-time approximations (multiplicative FPRAS) for the probability of the complement event, namely, losing the election.

PDF Details

AAAI Conference 2019 Conference Paper

Building Causal Graphs from Medical Literature and Electronic Medical Records

Galia Nordon
Gideon Koren
Varda Shalev
Benny Kimelfeld
Uri Shalit
Kira Radinsky

Large repositories of medical data, such as Electronic Medical Record (EMR) data, are recognized as promising sources for knowledge discovery. Effective analysis of such repositories often necessitate a thorough understanding of dependencies in the data. For example, if the patient age is ignored, then one might wrongly conclude a causal relationship between cataract and hypertension. Such confounding variables are often identified by causal graphs, where variables are connected by causal relationships. Current approaches to automatically building such graphs are based on text analysis over medical literature; yet, the result is typically a large graph of low precision. There are statistical methods for constructing causal graphs from observational data, but they are less suitable for dealing with a large number of covariates, which is the case in EMR data. Consequently, confounding variables are often identified by medical domain experts via a manual, expensive, and time-consuming process. We present a novel approach for automatically constructing causal graphs between medical conditions. The first part is a novel graph-based method to better capture causal relationships implied by medical literature, especially in the presence of multiple causal factors. Yet even after using these advanced text-analysis methods, the text data still contains many weak or uncertain causal connections. Therefore, we construct a second graph for these terms based on an EMR repository of over 1. 5M patients. We combine the two graphs, leaving only edges that have both medical-text-based and observational evidence. We examine several strategies to carry out our approach, and compare the precision of the resulting graphs using medical experts. Our results show a significant improvement in the precision of any of our methods compared to the state of the art.

PDF Details

IJCAI Conference 2018 Conference Paper

Computational Social Choice Meets Databases

Benny Kimelfeld
Phokion G. Kolaitis
Julia Stoyanovich

We develop a novel framework that aims to create bridges between the computational social choice and the database management communities. This framework enriches the tasks currently supported in computational social choice with relational database context, thus making it possible to formulate sophisticated queries about voting rules, candidates, voters, issues, and positions. At the conceptual level, we give rigorous semantics to queries in this framework by introducing the notions of necessary answers and possible answers to queries. At the technical level, we embark on an investigation of the computational complexity of the necessary answers. In particular, we establish a number of results about the complexity of the necessary answers of conjunctive queries involving the plurality rule that contrast sharply with earlier results about the complexity of the necessary winners under the plurality rule.

PDF Details

AAAI Conference 2018 Conference Paper

Probabilistic Inference Over Repeated Insertion Models

Batya Kenig
Lovro Ilijasić
Haoyue Ping
Benny Kimelfeld
Julia Stoyanovich

Distributions over rankings are used to model user preferences in various settings including political elections and electronic commerce. The Repeated Insertion Model (RIM) gives rise to various known probability distributions over rankings, in particular to the popular Mallows model. However, probabilistic inference on RIM is computationally challenging, and provably intractable in the general case. In this paper we propose an algorithm for computing the marginal probability of an arbitrary partially ordered set over RIM. We analyze the complexity of the algorithm in terms of properties of the model and the partial order, captured by a novel measure termed the “cover width”. We also conduct an experimental study of the algorithm over serial and parallelized implementations. Building upon the relationship between inference with rank distributions and counting linear extensions, we investigate the inference problem when restricted to partial orders that lend themselves to efﬁcient counting of their linear extensions.

PDF Details