Arrow Research search

Author name cluster

David Kempe

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.

18 papers
1 author row

Possible papers

18

AAAI Conference 2026 Conference Paper

An External Fairness Evaluation of LinkedIn Talent Search

  • Tina Behzad
  • Siddartha Devic
  • Vatsal Sharan
  • Aleksandra Korolova
  • David Kempe

We conduct an independent, third-party audit for bias of LinkedIn's Talent Search ranking system, focusing on potential ranking bias across two attributes: gender and race. To do so, we first construct a dataset of rankings produced by the system, collecting extensive Talent Search results across a diverse set of occupational queries. We then develop a robust labeling pipeline that infers the two demographic attributes of interest for the returned users. To evaluate potential biases in the collected dataset of real-world rankings, we utilize two exposure disparity metrics: deviation from group proportions and MinSkew@k. Our analysis reveals an under-representation of minority groups in early ranks across many queries. We further examine potential causes of this disparity, and discuss why they may be difficult or, in some cases, impossible to fully eliminate among the early ranks of queries. Beyond static metrics, we also investigate the concept of subgroup fairness over time, highlighting \emph{temporal disparities} in exposure and retention, which are often more difficult to audit for in practice. In employer recruiting platforms such as LinkedIn Talent Search, the persistence of a particular candidate over multiple days in the ranking can directly impact the probability that the given candidate is selected for opportunities. Our analysis reveals demographic disparities in this temporal stability, with some groups experiencing greater volatility in their ranked positions than others. We contextualize all our findings alongside LinkedIn’s published self-audits of its Talent Search system and reflect on the methodological constraints of a black-box external evaluation, including limited observability and noisy demographic inference. Our work contributes empirical insights and practical guidance for conducting third-party audits of modern socio-technical systems which go beyond the well-studied and standard algorithmic fairness guarantees of predictors.

PDF Details DOI

AAMAS Conference 2026 Conference Paper

Relationships and Connections between Definitions of Metric Proportional Representation

  • Yusuf Hakan Kalayci
  • David Kempe

We explore the rich landscape of proportional representation in metric committee selection and reveal notable equivalences and implications (up to approximation factors) among existing fairness notions. We distinguish between multi-representation and singlerepresentation guarantees. For multi-representation, we introduce an “umbrella” definition we call uniform core, which requires that the 𝑞-core notion [12] hold for every𝑞 simultaneously. We show that proportionally representative fairness [5] (also defined as mPJR [20]) and this umbrella definition are equivalent (up to a constant factor), thus connecting two initially different-looking notions. Additionally, we establish that this equivalence class implies a notion of proportionally representative committee [19]. We then investigate ordinal proportionality axioms, specifically the RankJR axiom family introduced by Brill and Peters [6], which also inspired the study of metric JR axioms but employs ordinal rankings in lieu of distances. We demonstrate that RankPJR implies mPJR (again, up to a constant factor); however, the converse direction does not hold. An immediate consequence of this analysis is that the output of the (ordinal) Expanding Approvals Rule satisfies all of the aforementioned representation axioms to within a constant factor. Turning to single-representation guarantees, we establish that three well-known notions, namely, Proportionally Fair Clustering [10], Individual Fairness [18], and the Approximate Core [23], are essentially equivalent.

PDF

AAMAS Conference 2025 Conference Paper

Full Proportional Justified Representation

  • Yusuf Hakan Kalayci
  • Jiasen Liu
  • David Kempe

In multiwinner approval voting, selecting a proportionally representative committee based on the voters’ approval ballots is an essential task. The notion of justified representation (JR) demands that any large “cohesive” group of voters should be proportionally “represented”. Different specific definitions of justified representation define “cohesiveness” in different ways; two common ways are the following: (C1) the coalition unanimously approves a subset of candidates whose size is proportional to its share of the electorate, and (C2) each voter in the coalition approves at least a fixed fraction of a candidate subset proportional to the coalition’s size. Similarly, among others, the following two concrete definitions of “representation” have been considered: (R1) the coalition’s collective utility from the winning set exceeds that of any proportionally sized alternative, and (R2) for any proportionally sized alternative, at least one member of the coalition derives less utility from it than from the winning set. Three of the four possible combinations have been extensively studied and used to define extensions of Justified Representation: • (C1)-(R1): Proportional Justified Representation (PJR) • (C1)-(R2): Extended Justified Representation (EJR) • (C2)-(R2): Full Justified Representation (FJR) All three have merits, but also drawbacks. PJR is the weakest notion, and perhaps not sufficiently demanding; EJR may not be compatible with perfect representation; and it is open whether a committee satisfying FJR can be found efficiently. We study the combination (C2)-(R1), which we call Full Proportional Justified Representation (FPJR). We investigate FPJR’s properties and find that it shares advantages with PJR over EJR; specifically, several desirable proportionality axioms — such as priceability and perfect representation — imply FPJR and PJR but not EJR. Next, we show that efficient rules like the greedy Monroe rule and the method of equal shares satisfy FPJR, thus matching one of the key advantages of EJR over FJR. However, the Proportional Approval Voting (PAV) rule may violate FPJR, so neither of EJR and FPJR implies the other.

PDF

AAMAS Conference 2025 Conference Paper

k - ApprovalVeto: A Spectrum of Voting Rules Balancing Metric Distortion and Minority Protection

  • Fatih Erdem Kizilkaya
  • David Kempe

In the context of single-winner ranked-choice elections between 𝑚 candidates, we explore the tradeoff between two principles that are essential to constitutional democracies: the majority principle (maximizing the social welfare) and the minority principle (safeguarding minority groups from overly bad outcomes). To measure the social welfare, we use the well-established framework of metric distortion subject to various objectives: utilitarian (i. e. , total cost), 𝛼-percentile (e. g. , median cost for 𝛼 = 1/2), and egalitarian (i. e. , max cost). To measure the protection of minorities, we introduce the 𝑘-Droop minority criterion, which requires that if a sufficiently large (parametrized by 𝑘) coalition 𝑇 of voters ranks all candidates in 𝑆 at the bottom (in any order), then none of the candidates in 𝑆 should win. The parameter 𝑘 allows the criterion to interpolate between the minimal requirement that the winner must not be ranked last by a strict majority (when 𝑘 = 1) and the strongest protection from bottom choices (when 𝑘 = 𝑚 − 1). The highest 𝑘 for which the criterion is satisfied provides a well-defined measure of minority protection (ranging from 0 to 𝑚 − 1). Our main contribution is the analysis of a recently proposed class of voting rules called 𝑘-ApprovalVeto, offering a comprehensive range of trade-offs between the two principles. This class spans between PluralityVeto (for 𝑘 = 1) — a simple rule achieving optimal metric distortion — and VoteByVeto (for 𝑘 = 𝑚) which picks a candidate from the proportional veto core. We show that 𝑘-ApprovalVeto has minority protection at least 𝑘 − 1, and thus, it accommodates any desired level of minority protection via the parameter 𝑘. However, this comes at the price of lower social welfare. For the utilitarian objective, the metric distortion becomes 2 · min(𝑘 + 1, 𝑚) − 1, i. e. , increases linearly in 𝑘. For the 𝛼-percentile objective, the metric distortion is the optimal value of 5 for 𝛼 ≥ 𝑘/(𝑘 + 1) and unbounded for 𝛼 < 𝑘/(𝑘 + 1), i. e. , the range of 𝛼 for which the rule achieves optimal distortion becomes smaller. For the egalitarian objective, the metric distortion is the optimal value of 3 for all values of 𝑘.

PDF

AAAI Conference 2024 Conference Paper

Proportional Representation in Metric Spaces and Low-Distortion Committee Selection

  • Yusuf Kalayci
  • David Kempe
  • Vikram Kher

We introduce a novel definition for a small set R of k points being "representative" of a larger set in a metric space. Given a set V (e.g., documents or voters) to represent, and a set C of possible representatives, our criterion requires that for any subset S comprising a theta fraction of V, the average distance of S to their best theta*k points in R should not be more than a factor gamma compared to their average distance to the best theta*k points among all of C. This definition is a strengthening of proportional fairness and core fairness, but - different from those notions - requires that large cohesive clusters be represented proportionally to their size. Since there are instances for which - unless gamma is polynomially large - no solutions exist, we study this notion in a resource augmentation framework, implicitly stating the constraints for a set R of size k as though its size were only k/alpha, for alpha > 1. Furthermore, motivated by the application to elections, we mostly focus on the "ordinal" model, where the algorithm does not learn the actual distances; instead, it learns only for each point v in V and each candidate pairs c, c' which of c, c' is closer to v. Our main result is that the Expanding Approvals Rule (EAR) of Aziz and Lee is (alpha, gamma) representative with gamma <= 1 + 6.71 * (alpha)/(alpha-1). Our results lead to three notable byproducts. First, we show that the EAR achieves constant proportional fairness in the ordinal model, giving the first positive result on metric proportional fairness with ordinal information. Second, we show that for the core fairness objective, the EAR achieves the same asymptotic tradeoff between resource augmentation and approximation as the recent results of Li et al., which used full knowledge of the metric. Finally, our results imply a very simple single-winner voting rule with metric distortion at most 44.

PDF Details DOI

AAMAS Conference 2022 Conference Paper

Networked Restless Multi-Armed Bandits for Mobile Interventions

  • Han-Ching Ou
  • Christoph Siebenbrunner
  • Jackson Killian
  • Meredith B. Brooks
  • David Kempe
  • Yevgeniy Vorobeychik
  • Milind Tambe

Motivated by a broad class of mobile intervention problems, we propose and study restless multi-armed bandits (RMABs) with network effects. In our model, arms are partially recharging and connected through a graph, so that pulling one arm also improves the state of neighboring arms, significantly extending the previously studied setting of fully recharging bandits with no network effects. In mobile interventions, network effects may arise due to regular population movements (such as commuting between home and work). We show that network effects in RMABs induce strong reward coupling that is not accounted for by existing solution methods. We propose a new solution approach for networked RMABs, exploiting concavity properties which arise under natural assumptions on the structure of intervention effects. We provide sufficient conditions for optimality of our approach in idealized settings and demonstrate that it empirically outperforms state-of-the art baselines in three mobile intervention domains using real-world graphs.

PDF

IJCAI Conference 2022 Conference Paper

Plurality Veto: A Simple Voting Rule Achieving Optimal Metric Distortion

  • Fatih Erdem Kizilkaya
  • David Kempe

The metric distortion framework posits that n voters and m candidates are jointly embedded in a metric space such that voters rank candidates that are closer to them higher. A voting rule's purpose is to pick a candidate with minimum total distance to the voters, given only the rankings, but not the actual distances. As a result, in the worst case, each deterministic rule picks a candidate whose total distance is at least three times larger than that of an optimal one, i. e. , has distortion at least 3. A recent breakthrough result showed that achieving this bound of 3 is possible; however, the proof is non-constructive, and the voting rule itself is a complicated exhaustive search. Our main result is an extremely simple voting rule, called Plurality Veto, which achieves the same optimal distortion of 3. Each candidate starts with a score equal to his number of first-place votes. These scores are then gradually decreased via an n-round veto process in which a candidate drops out when his score reaches zero. One after the other, voters decrement the score of their bottom choice among the standing candidates, and the last standing candidate wins. We give a one-paragraph proof that this voting rule achieves distortion 3. This rule is also immensely practical, and it only makes two queries to each voter, so it has low communication overhead. We also show that a straightforward extension can be used to give a constructive proof of the more general Ranking-Matching Lemma of Gkatzelis et al. We also generalize Plurality Veto into a class of randomized voting rules in the following way: Plurality veto is run only for k < n rounds; then, a candidate is chosen with probability proportional to his residual score. This general rule interpolates between Random Dictatorship (for k=0) and Plurality Veto (for k=n-1), and k controls the variance of the output. We show that for all k, this rule has expected distortion at most 3.

PDF Details DOI

IJCAI Conference 2021 Conference Paper

Altruism Design in Networked Public Goods Games

  • Sixie Yu
  • David Kempe
  • Yevgeniy Vorobeychik

Many collective decision-making settings feature a strategic tension between agents acting out of individual self-interest and promoting a common good. These include wearing face masks during a pandemic, voting, and vaccination. Networked public goods games capture this tension, with networks encoding strategic interdependence among agents. Conventional models of public goods games posit solely individual self-interest as a motivation, even though altruistic motivations have long been known to play a significant role in agents' decisions. We introduce a novel extension of public goods games to account for altruistic motivations by adding a term in the utility function that incorporates the perceived benefits an agent obtains from the welfare of others, mediated by an altruism graph. Most importantly, we view altruism not as immutable, but rather as a lever for promoting the common good. Our central algorithmic question then revolves around the computational complexity of modifying the altruism network to achieve desired public goods game investment profiles. We first show that the problem can be solved using linear programming when a principal can fractionally modify the altruism network. While the problem becomes in general intractable if the principal's actions are all-or-nothing, we exhibit several tractable special cases.

PDF Details DOI

NeurIPS Conference 2021 Conference Paper

Fairness in Ranking under Uncertainty

  • Ashudeep Singh
  • David Kempe
  • Thorsten Joachims

Fairness has emerged as an important consideration in algorithmic decision making. Unfairness occurs when an agent with higher merit obtains a worse outcome than an agent with lower merit. Our central point is that a primary cause of unfairness is uncertainty. A principal or algorithm making decisions never has access to the agents' true merit, and instead uses proxy features that only imperfectly predict merit (e. g. , GPA, star ratings, recommendation letters). None of these ever fully capture an agent's merit; yet existing approaches have mostly been defining fairness notions directly based on observed features and outcomes. Our primary point is that it is more principled to acknowledge and model the uncertainty explicitly. The role of observed features is to give rise to a posterior distribution of the agents' merits. We use this viewpoint to define a notion of approximate fairness in ranking. We call an algorithm $\phi$-fair (for $\phi \in [0, 1]$) if it has the following property for all agents $x$ and all $k$: if agent $x$ is among the top $k$ agents with respect to merit with probability at least $\rho$ (according to the posterior merit distribution), then the algorithm places the agent among the top $k$ agents in its ranking with probability at least $\phi \rho$. We show how to compute rankings that optimally trade off approximate fairness against utility to the principal. In addition to the theoretical characterization, we present an empirical analysis of the potential impact of the approach in simulation studies. For real-world validation, we applied the approach in the context of a paper recommendation system that we built and fielded at the KDD 2020 conference.

PDF Details

AAAI Conference 2020 Conference Paper

An Analysis Framework for Metric Voting based on LP Duality

  • David Kempe

Distortion-based analysis has established itself as a fruitful framework for comparing voting mechanisms. m voters and n candidates are jointly embedded in an (unknown) metric space, and the voters submit rankings of candidates by nondecreasing distance from themselves. Based on the submitted rankings, the social choice rule chooses a winning candidate; the quality of the winner is the sum of the (unknown) distances to the voters. The rule’s choice will in general be suboptimal, and the worst-case ratio between the cost of its chosen candidate and the optimal candidate is called the rule’s distortion. It was shown in prior work that every deterministic rule has distortion at least 3, while the Copeland rule and related rules guarantee distortion at most 5; a very recent result gave a rule with distortion 2 + √ 5 ≈ 4. 236. We provide a framework based on LP-duality and flow interpretations of the dual which provides a simpler and more unified way for proving upper bounds on the distortion of social choice rules. We illustrate the utility of this approach with three examples. First, we show that the Ranked Pairs and Schulze rules have distortion Θ( √ n). Second, we give a fairly simple proof of a strong generalization of the upper bound of 5 on the distortion of Copeland, to social choice rules with short paths from the winning candidate to the optimal candidate in generalized weak preference graphs. A special case of this result recovers the recent 2 + √ 5 guarantee. Finally, our framework naturally suggests a combinatorial rule that is a strong candidate for achieving distortion 3, which had also been proposed in recent work. We prove that the distortion bound of 3 would follow from any of three combinatorial conjectures we formulate.

PDF Details

AAAI Conference 2020 Conference Paper

Communication, Distortion, and Randomness in Metric Voting

  • David Kempe

In distortion-based analysis of social choice rules over metric spaces, voters and candidates are jointly embedded in a metric space. Voters rank candidates by non-decreasing distance. The mechanism, receiving only this ordinal (comparison) information, must select a candidate approximately minimizing the sum of distances from all voters to the chosen candidate. It is known that while the Copeland rule and related rules guarantee distortion at most 5, the distortion of many other standard voting rules, such as Plurality, Veto, or k-approval, grows unboundedly in the number n of candidates. An advantage of Plurality, Veto, or k-approval with small k is that they require less communication from the voters; all deterministic social choice rules known to achieve constant distortion require voters to transmit their complete rankings of all candidates. This motivates our study of the tradeoff between the distortion and the amount of communication in deterministic social choice rules. We show that any one-round deterministic voting mechanism in which each voter communicates only the candidates she ranks in a given set of k positions must have distortion at least 2n−k k; we give a mechanism achieving an upper bound of O(n/k), which matches the lower bound up to a constant. For more general communication-bounded voting mechanisms, in which each voter communicates b bits of information about her ranking, we show a slightly weaker lower bound of Ω(n/b) on the distortion. For randomized mechanisms, Random Dictatorship achieves expected distortion strictly smaller than 3, almost matching a lower bound of 3 − 2 n for any randomized mechanism that only receives each voter’s top choice. We close this gap, by giving a simple randomized social choice rule which only uses each voter’s first choice, and achieves expected distortion 3 − 2 n.

PDF Details

JMLR Journal 2018 Journal Article

Approximate Submodularity and its Applications: Subset Selection, Sparse Approximation and Dictionary Selection

  • Abhimanyu Das
  • David Kempe

We introduce the submodularity ratio as a measure of how "close" to submodular a set function $f$ is. We show that when $f$ has submodularity ratio $\gamma$, the greedy algorithm for maximizing $f$ provides a $(1-e^{-\gamma})$-approximation. Furthermore, when $\gamma$ is bounded away from 0, the greedy algorithm for minimum submodular cover also provides essentially an $O(\log n)$ approximation for a universe of $n$ elements. As a main application of this framework, we study the problem of selecting a subset of $k$ random variables from a large set, in order to obtain the best linear prediction of another variable of interest. We analyze the performance of widely used greedy heuristics; in particular, by showing that the submodularity ratio is lower-bounded by the smallest $2k$-sparse eigenvalue of the covariance matrix, we obtain the strongest known approximation guarantees for the Forward Regression and Orthogonal Matching Pursuit algorithms. As a second application, we analyze greedy algorithms for the dictionary selection problem, and significantly improve the previously known guarantees. Our theoretical analysis is complemented by experiments on real-world and synthetic data sets; in particular, we focus on an analysis of how tight various spectral parameters and the submodularity ratio are in terms of predicting the performance of the greedy algorithms. [abs] [ pdf ][ bib ] &copy JMLR 2018. ( edit, beta )

PDF Details

AAAI Conference 2018 Conference Paper

On the Distortion of Voting With Multiple Representative Candidates

  • Yu Cheng
  • Shaddin Dughmi
  • David Kempe

We study positional voting rules when candidates and voters are embedded in a common metric space, and cardinal preferences are naturally given by distances in the metric space. In a positional voting rule, each candidate receives a score from each ballot based on the ballot’s rank order; the candidate with the highest total score wins the election. The cost of a candidate is his sum of distances to all voters, and the distortion of an election is the ratio between the cost of the elected candidate and the cost of the optimum candidate. We consider the case when candidates are representative of the population, in the sense that they are drawn i. i. d. from the population of the voters, and analyze the expected distortion of positional voting rules. Our main result is a clean and tight characterization of positional voting rules that have constant expected distortion (independent of the number of candidates and the metric space). Our characterization result immediately implies constant expected distortion for Borda Count and elections in which each voter approves a constant fraction of all candidates. On the other hand, we obtain super-constant expected distortion for Plurality, Veto, and approving a constant number of candidates. These results contrast with previous results on voting with metric preferences: When the candidates are chosen adversarially, all of the preceding voting rules have distortion linear in the number of candidates or voters. Thus, the model of representative candidates allows us to distinguish voting rules which seem equally bad in the worst case.

PDF Details

NeurIPS Conference 2017 Conference Paper

A General Framework for Robust Interactive Learning

  • Ehsan Emamjomeh-Zadeh
  • David Kempe

We propose a general framework for interactively learning models, such as (binary or non-binary) classifiers, orderings/rankings of items, or clusterings of data points. Our framework is based on a generalization of Angluin's equivalence query model and Littlestone's online learning model: in each iteration, the algorithm proposes a model, and the user either accepts it or reveals a specific mistake in the proposal. The feedback is correct only with probability p > 1/2 (and adversarially incorrect with probability 1 - p), i. e. , the algorithm must be able to learn in the presence of arbitrary noise. The algorithm's goal is to learn the ground truth model using few iterations. Our general framework is based on a graph representation of the models and user feedback. To be able to learn efficiently, it is sufficient that there be a graph G whose nodes are the models, and (weighted) edges capture the user feedback, with the property that if s, s* are the proposed and target models, respectively, then any (correct) user feedback s' must lie on a shortest s-s* path in G. Under this one assumption, there is a natural algorithm, reminiscent of the Multiplicative Weights Update algorithm, which will efficiently learn s* even in the presence of noise in the user's feedback. From this general result, we rederive with barely any extra effort classic results on learning of classifiers and a recent result on interactive clustering; in addition, we easily obtain new interactive learning algorithms for ordering/ranking.

PDF Details

NeurIPS Conference 2016 Conference Paper

Learning Influence Functions from Incomplete Observations

  • Xinran He
  • Ke Xu
  • David Kempe
  • Yan Liu

We study the problem of learning influence functions under incomplete observations of node activations. Incomplete observations are a major concern as most (online and real-world) social networks are not fully observable. We establish both proper and improper PAC learnability of influence functions under randomly missing observations. Proper PAC learnability under the Discrete-Time Linear Threshold (DLT) and Discrete-Time Independent Cascade (DIC) models is established by reducing incomplete observations to complete observations in a modified graph. Our improper PAC learnability result applies for the DLT and DIC models as well as the Continuous-Time Independent Cascade (CIC) model. It is based on a parametrization in terms of reachability features, and also gives rise to an efficient and practical heuristic. Experiments on synthetic and real-world datasets demonstrate the ability of our method to compensate even for a fairly large fraction of missing observations.

PDF Details

AAAI Conference 2012 Conference Paper

Security Games with Limited Surveillance

  • Bo An
  • David Kempe
  • Christopher Kiekintveld
  • Eric Shieh
  • Satinder Singh
  • Milind Tambe
  • Yevgeniy Vorobeychik

Randomized first-mover strategies of Stackelberg games are used in several deployed applications to allocate limited resources for the protection of critical infrastructure. Stackelberg games model the fact that a strategic attacker can surveil and exploit the defender’s strategy, and randomization guards against the worst effects by making the defender less predictable. In accordance with the standard game-theoretic model of Stackelberg games, past work has typically assumed that the attacker has perfect knowledge of the defender’s randomized strategy and will react correspondingly. In light of the fact that surveillance is costly, risky, and delays an attack, this assumption is clearly simplistic: attackers will usually act on partial knowledge of the defender’s strategies. The attacker’s imperfect estimate could present opportunities and possibly also threats to a strategic defender. In this paper, we therefore begin a systematic study of security games with limited surveillance. We propose a natural model wherein an attacker forms or updates a belief based on observed actions, and chooses an optimal response. We investigate the model both theoretically and experimentally. In particular, we give mathematical programs to compute optimal attacker and defender strategies for a fixed observation duration, and show how to use them to estimate the attacker’s observation durations. Our experimental results show that the defender can achieve significant improvement in expected utility by taking the attacker’s limited surveillance into account, validating the motivation of our work.

PDF Details

AAAI Conference 2010 Conference Paper

Urban Security: Game-Theoretic Resource Allocation in Networked Domains

  • Jason Tsai
  • Zhengyu Yin
  • Jun-young Kwak
  • David Kempe
  • Christopher Kiekintveld
  • Milind Tambe

Law enforcement agencies frequently must allocate limited resources to protect targets embedded in a network, such as important buildings in a city road network. Since intelligent attackers may observe and exploit patterns in the allocation, it is crucial that the allocations be randomized. We cast this problem as an attacker-defender Stackelberg game: the defender’s goal is to obtain an optimal mixed strategy for allocating resources. The defender’s strategy space is exponential in the number of resources, and the attacker’s exponential in the network size. Existing algorithms are therefore useless for all but the smallest networks. We present a solution approach based on two key ideas: (i) A polynomial-sized game model obtained via an approximation of the strategy space, solved efficiently using a linear program; (ii) Two efficient techniques that map solutions from the approximate game to the original, with proofs of correctness under certain assumptions. We present in-depth experimental results, including an evaluation on part of the Mumbai road network.

PDF Details
v2026.09.13