Author name cluster

Anson Kahng

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.

13 papers

2 author rows

AAMAS Conference 2025 Conference Paper

When to Stop Getting Tested: The Theory of Diagnostic Tests

Anson Kahng
Joseph Saber

We present and analyze a simple model for medical care in which patients may take relatively low-cost medical tests in order to update their beliefs about the probability that they have a particular disease. At any point, patients may leave the testing domain and either risk the effects of the disease or seek expensive treatment. We explore the question of when patients should stop getting tested. In particular, we study two variants of this game in which patients may take an infinite or finite number of tests. We numerically solve for optimal strategies in both the finite and infinite cases, and analytically derive optimal behavior for well-behaved subcases in the infinite setting. We also experimentally explore variants of our basic medical testing model.

PDF

IJCAI Conference 2024 Conference Paper

Sampling Winners in Ranked Choice Voting

Matthew Iceland
Anson Kahng
Joseph Saber

Ranked choice voting (RCV) is a voting rule that iteratively eliminates least-popular candidates until there is a single winner with a majority of all remaining votes. In this work, we explore three central questions about predicting the outcome of RCV on an election given a uniform sample of votes. First, in theory, how poorly can RCV sampling predict RCV outcomes? Second, can we use insights from the recently-proposed map of elections to better predict RCV outcomes? Third, is RCV the best rule to use on a sample to predict the outcome of RCV in real-world elections? We find that although RCV can do quite poorly in the worst case and it may be better to use other rules to predict RCV winners on synthetic data from the map of elections, RCV generally predicts itself well on real-world data, further contributing to its appeal as a theoretically-flawed but practicable voting process. We further supplement our work by exploring the effect of margin of victory (MoV) on sampling accuracy.

PDF Details DOI

AAAI Conference 2023 Conference Paper

Voting with Preference Intensities

Anson Kahng
Mohamad Latifian
Nisarg Shah

When an agent votes, she typically ranks the set of available alternatives. Occasionally, she may also wish to report the intensity of her preferences by indicating adjacent pairs of alternatives in her ranking between which her preference is acutely decisive; for instance, she may suggest that she likes alternative a more than b, but b much more than c. We design near-optimal voting rules which aggregate such preference rankings with intensities using the recently-popular distortion framework. We also show that traditional voting rules, which aggregate preference rankings while ignoring (or not eliciting) intensities, can incur significant welfare loss.

PDF Details DOI

AAAI Conference 2022 Conference Paper

Worst-Case Voting When the Stakes Are High

Anson Kahng
Gregory Kehne

We study the additive distortion of social choice functions in the implicit utilitarian model, and argue that it is a more appropriate metric than multiplicative distortion when an alternative that confers significant social welfare may exist (i. e. , when the stakes are high). We define a randomized analog of positional scoring rules, and present a rule which is asymptotically optimal within this class as the number of alternatives increases. We then show that the instance-optimal social choice function can be efficiently computed. Next, we take a beyond-worst-case view, bounding the additive distortion of prominent voting rules as a function of the best welfare attainable in an instance. Lastly, we evaluate the additive distortion of a range of rules on real-world election data.

PDF Details

AAAI Conference 2021 Conference Paper

District-Fair Participatory Budgeting

D Ellis Hershkowitz
Anson Kahng
Dominik Peters
Ariel D. Procaccia

Participatory budgeting is a method used by city governments to select public projects to fund based on residents’ votes. Many cities use participatory budgeting at a district level. Typically, a budget is divided among districts proportionally to their population, and each district holds an election over local projects and then uses its budget to fund the projects most preferred by its voters. However, district-level participatory budgeting can yield poor social welfare because it does not necessarily fund projects supported across multiple districts. On the other hand, decision making that only takes global social welfare into account can be unfair to districts: A social-welfare-maximizing solution might not fund any of the projects preferred by a district, despite the fact that its constituents pay taxes to the city. Thus, we study how to fairly maximize social welfare in a participatory budgeting setting with a single city-wide election. We propose a notion of fairness that guarantees each district at least as much welfare as it would have received in a district-level election. We show that, although optimizing social welfare subject to this notion of fairness is NP-hard, we can efficiently construct a lottery over welfare-optimal outcomes that is fair in expectation. Moreover, we show that, when we are allowed to slightly relax fairness, we can efficiently compute a fair solution that is welfare-maximizing, but which may overspend the budget.

PDF Details

JAIR Journal 2021 Journal Article

Liquid Democracy: An Algorithmic Perspective

Anson Kahng
Simon Mackenzie
Ariel D. Procaccia

We study liquid democracy, a collective decision making paradigm that allows voters to transitively delegate their votes, through an algorithmic lens. In our model, there are two alternatives, one correct and one incorrect, and we are interested in the probability that the majority opinion is correct. Our main question is whether there exist delegation mechanisms that are guaranteed to outperform direct voting, in the sense of being always at least as likely, and sometimes more likely, to make a correct decision. Even though we assume that voters can only delegate their votes to better-informed voters, we show that local delegation mechanisms, which only take the local neighborhood of each voter as input (and, arguably, capture the spirit of liquid democracy), cannot provide the foregoing guarantee. By contrast, we design a non-local delegation mechanism that does provably outperform direct voting under mild assumptions about voters.

PDF Details DOI

AAAI Conference 2020 Conference Paper

HirePeer: Impartial Peer-Assessed Hiring at Scale in Expert Crowdsourcing Markets

Yasmine Kotturi
Anson Kahng
Ariel Procaccia
Chinmay Kulkarni

Expert crowdsourcing (e. g. , Upwork. com) provides promising beneﬁts such as productivity improvements for employers, and ﬂexible working arrangements for workers. Yet to realize these beneﬁts, a key persistent challenge is effective hiring at scale. Current approaches, such as reputation systems and standardized competency tests, develop weaknesses such as score inﬂation over time, thus degrading market quality. This paper presents HirePeer, a novel alternative approach to hiring at scale that leverages peer assessment to elicit honest assessments of fellow workers’ job application materials, which it then aggregates using an impartial ranking algorithm. This paper reports on three studies that investigate both the costs and the beneﬁts to workers and employers of impartial peer-assessed hiring. We ﬁnd, to solicit honest assessments, algorithms must be communicated in terms of their impartial effects. Second, in practice, peer assessment is highly accurate, and impartial rank aggregation algorithms incur a small accuracy cost for their impartiality guarantee. Third, workers report ﬁnding peer-assessed hiring useful for receiving targeted feedback on their job materials.

PDF Details

IJCAI Conference 2020 Conference Paper

Proportionality in Approval-Based Elections With a Variable Number of Winners

Rupert Freeman
Anson Kahng
David M. Pennock

We study proportionality in approval-based multiwinner elections with a variable number of winners, where both the size and identity of the winning committee are informed by voters' opinions. While proportionality has been studied in multiwinner elections with a fixed number of winners, it has not been considered in the variable number of winners setting. The measure of proportionality we consider is average satisfaction (AS), which intuitively measures the number of agreements on average between sufficiently large and cohesive groups of voters and the output of the voting rule. First, we show an upper bound on AS that any deterministic rule can provide, and that straightforward adaptations of deterministic rules from the fixed number of winners setting do not achieve better than a 1/2 approximation to AS even for large numbers of candidates. We then prove that a natural randomized rule achieves a 29/32 approximation to AS.

PDF Details DOI

ICML Conference 2020 Conference Paper

Strategyproof Mean Estimation from Multiple-Choice Questions

Anson Kahng
Gregory Kehne
Ariel D. Procaccia

Given n values possessed by n agents, we study the problem of estimating the mean by truthfully eliciting agents’ answers to multiple-choice questions about their values. We consider two natural candidates for estimation error: mean squared error (MSE) and mean absolute error (MAE). We design a randomized estimator which is asymptotically optimal for both measures in the worst case. In the case where prior distributions over the agents’ values are known, we give an optimal, polynomial-time algorithm for MSE, and show that the task of computing an optimal estimate for MAE is #P-hard. Finally, we demonstrate empirically that knowledge of prior distributions gives a significant edge.

Details

NeurIPS Conference 2019 Conference Paper

Paradoxes in Fair Machine Learning

Paul Goelz
Anson Kahng
Ariel Procaccia

Equalized odds is a statistical notion of fairness in machine learning that ensures that classification algorithms do not discriminate against protected groups. We extend equalized odds to the setting of cardinality-constrained fair classification, where we have a bounded amount of a resource to distribute. This setting coincides with classic fair division problems, which allows us to apply concepts from that literature in parallel to equalized odds. In particular, we consider the axioms of resource monotonicity, consistency, and population monotonicity, all three of which relate different allocation instances to prevent paradoxes. Using a geometric characterization of equalized odds, we examine the compatibility of equalized odds with these axioms. We empirically evaluate the cost of allocation rules that satisfy both equalized odds and axioms of fair division on a dataset of FICO credit scores.

PDF Details

ICML Conference 2019 Conference Paper

Statistical Foundations of Virtual Democracy

Anson Kahng
Min Kyung Lee
Ritesh Noothigattu
Ariel D. Procaccia
Christos-Alexandros Psomas

Virtual democracy is an approach to automating decisions, by learning models of the preferences of individual people, and, at runtime, aggregating the predicted preferences of those people on the dilemma at hand. One of the key questions is which aggregation method – or voting rule – to use; we offer a novel statistical viewpoint that provides guidance. Specifically, we seek voting rules that are robust to prediction errors, in that their output on people’s true preferences is likely to coincide with their output on noisy estimates thereof. We prove that the classic Borda count rule is robust in this sense, whereas any voting rule belonging to the wide family of pairwise-majority consistent rules is not. Our empirical results further support, and more precisely measure, the robustness of Borda count.

Details

AAAI Conference 2018 Conference Paper

Liquid Democracy: An Algorithmic Perspective

Anson Kahng
Simon Mackenzie
Ariel Procaccia

We study liquid democracy, a collective decision making paradigm that allows voters to transitively delegate their votes, through an algorithmic lens. In our model, there are two alternatives, one correct and one incorrect, and we are interested in the probability that the majority opinion is correct. Our main question is whether there exist delegation mechanisms that are guaranteed to outperform direct voting, in the sense of being always at least as likely, and sometimes more likely, to make a correct decision. Even though we assume that voters can only delegate their votes to better-informed voters, we show that local delegation mechanisms, which only take the local neighborhood of each voter as input (and, arguably, capture the spirit of liquid democracy), cannot provide the foregoing guarantee. By contrast, we design a nonlocal delegation mechanism that does provably outperform direct voting under mild assumptions about voters.

PDF Details

AAAI Conference 2018 Conference Paper

Ranking Wily People Who Rank Each Other

Anson Kahng
Yasmine Kotturi
Chinmay Kulkarni
David Kurokawa
Ariel Procaccia

We study rank aggregation algorithms that take as input the opinions of players over their peers, represented as rankings, and output a social ordering of the players (which reﬂects, e. g. , relative contribution to a project or ﬁt for a job). To prevent strategic behavior, these algorithms must be impartial, i. e. , players should not be able to inﬂuence their own position in the output ranking. We design several randomized algorithms that are impartial and closely emulate given (nonimpartial) rank aggregation rules in a rigorous sense. Experimental results further support the efﬁcacy and practicability of our algorithms.

PDF Details