Publications
You can also find my articles on my Google Scholar profile.
2024
- Proportional Aggregation of Preferences for Sequential Decision Making.
Nikhil Chandak, Shashwat Goel, Dominik Peters.
AAAI Conference on Artificial Intelligence (AAAI), (in print), 2024.
Outstanding Paper Award (Top 3 out of 12000+) Abstract | Arxiv | Video | Bibtex
We study the problem of fair sequential decision making given voter preferences. In each round, a decision rule must choose a decision from a set of alternatives where each voter reports which of these alternatives they approve. Instead of going with the most popular choice in each round, we aim for proportional representation. We formalize this aim using axioms based on Proportional Justified Representation (PJR), which were proposed in the literature on multi-winner voting and were recently adapted to multi-issue decision making. The axioms require that every group of α% of the voters, if it agrees in every round (i.e., approves a common alternative), then those voters must approve at least α% of the decisions. A stronger version of the axioms requires that every group of α% of the voters that agrees in a β fraction of rounds must approve β⋅α% of the decisions. We show that three attractive voting rules satisfy axioms of this style. One of them (Sequential Phragmén) makes its decisions online, and the other two satisfy strengthened versions of the axioms but make decisions semi-online (Method of Equal Shares) or fully offline (Proportional Approval Voting). The first two are polynomial-time computable, and the latter is based on an NP-hard optimization, but it admits a polynomial-time local search algorithm that satisfies the same axiomatic properties. We present empirical results for these rules based on synthetic data and U.S. political elections. We also run experiments using the moral machine dataset about ethical dilemmas. We train preference models on user responses from different countries and let the models cast votes. We find that aggregating these votes using our rules leads to a more equal utility distribution across demographics than making decisions using a single global preference model.
@article{chandak2023proportional,
title={Proportional Aggregation of Preferences for Sequential Decision Making},
author={Chandak, Nikhil and Goel, Shashwat and Peters, Dominik},
journal={arXiv preprint arXiv:2306.14858},
year={2023}
}
2023
- Informed Steiner Trees: Sampling and Pruning for Multi-Goal Path Finding in High Dimensions.
Nikhil Chandak, Kenny Chour, Sivakumar Rathinam, R. Ravi.
IEEE Transactions on Automation Science and Engineering (T-ASE), 2023.
ICAPS PlanRobo Workshop 2023. Abstract | Arxiv | Code | Video | Bibtex
We interleave sampling based motion planning methods with pruning ideas from minimum spanning tree algorithms to develop a new approach for solving a Multi-Goal Path Finding (MGPF) problem in high dimensional spaces. The approach alternates between sampling points from selected regions in the search space and de-emphasizing regions that may not lead to good solutions for MGPF. Our approach provides an asymptotic, 2-approximation guarantee for MGPF. We also present extensive numerical results to illustrate the advantages of our proposed approach over uniform sampling in terms of the quality of the solutions found and computation speed.
