Source author record

Chinmay Sonar

Chinmay Sonar appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computer Science and Game Theory Computational Geometry Data Structures and Algorithms

Catalog footprint

What is connected

3works

3topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

Multiwinner Elections under Minimax Chamberlin-Courant Rule in Euclidean Space

We consider multiwinner elections in Euclidean space using the minimax Chamberlin-Courant rule. In this setting, voters and candidates are embedded in a $d$-dimensional Euclidean space, and the goal is to choose a committee of $k$ candidates so that the rank of any voter's most preferred candidate in the committee is minimized. (The problem is also equivalent to the ordinal version of the classical $k$-center problem.) We show that the problem is NP-hard in any dimension $d \geq 2$, and also provably hard to approximate. Our main results are three polynomial-time approximation schemes, each of which finds a committee with provably good minimax score. In all cases, we show that our approximation bounds are tight or close to tight. We mainly focus on the $1$-Borda rule but some of our results also hold for the more general $r$-Borda.

preprint2021arXiv

Equitable Division of a Path

We study fair resource allocation under a connectedness constraint wherein a set of indivisible items are arranged on a path and only connected subsets of items may be allocated to the agents. An allocation is deemed fair if it satisfies equitability up to one good (EQ1), which requires that agents' utilities are approximately equal. We show that achieving EQ1 in conjunction with well-studied measures of economic efficiency (such as Pareto optimality, non-wastefulness, maximum egalitarian or utilitarian welfare) is computationally hard even for binary additive valuations. On the algorithmic side, we show that by relaxing the efficiency requirement, a connected EQ1 allocation can be computed in polynomial time for any given ordering of agents, even for general monotone valuations. Interestingly, the allocation computed by our algorithm has the highest egalitarian welfare among all allocations consistent with the given ordering. On the other hand, if efficiency is required, then tractability can still be achieved for binary additive valuations with interval structure. On our way, we strengthen some of the existing results in the literature for other fairness notions such as envy-freeness up to one good (EF1), and also provide novel results for negatively-valued items or chores.

preprint2020arXiv

On the complexity of Winner Verification and Candidate Winner for Multiwinner Voting Rules

The Chamberlin-Courant and Monroe rules are fundamental and well-studied rules in the literature of multi-winner elections. The problem of determining if there exists a committee of size k that has a Chamberlin-Courant (respectively, Monroe) score of at most r is known to be NP-complete. We consider the following natural problems in this setting: a) given a committee S of size k as input, is it an optimal k-sized committee, and b) given a candidate c and a committee size k, does there exist an optimal k-sized committee that contains c? In this work, we resolve the complexity of both problems for the Chamberlin-Courant and Monroe voting rules in the settings of rankings as well as approval ballots. We show that verifying if a given committee is optimal is coNP-complete whilst the latter problem is complete for $Θ_{2}^{P}$. We also demonstrate efficient algorithms for the second problem when the input consists of single-peaked rankings. Our contribution fills an essential gap in the literature for these important multi-winner rules.