ﻻ يوجد ملخص باللغة العربية
We consider the algorithmic question of choosing a subset of candidates of a given size $k$ from a set of $m$ candidates, with knowledge of voters ordinal rankings over all candidates. We consider the well-known and classic scoring rule for achieving diverse representation: the Chamberlin-Courant (CC) or $1$-Borda rule, where the score of a committee is the average over the voters, of the rank of the best candidate in the committee for that voter; and its generalization to the average of the top $s$ best candidates, called the $s$-Borda rule. Our first result is an improved analysis of the natural and well-studied greedy heuristic. We show that greedy achieves a $left(1 - frac{2}{k+1}right)$-approximation to the maximization (or satisfaction) version of CC rule, and a $left(1 - frac{2s}{k+1}right)$-approximation to the $s$-Borda score. Our result improves on the best known approximation algorithm for this problem. We show that these bounds are almost tight. For the dissatisfaction (or minimization) version of the problem, we show that the score of $frac{m+1}{k+1}$ can be viewed as an optimal benchmark for the CC rule, as it is essentially the best achievable score of any polynomial-time algorithm even when the optimal score is a polynomial factor smaller (under standard computational complexity assumptions). We show that another well-studied algorithm for this problem, called the Banzhaf rule, attains this benchmark. We finally show that for the $s$-Borda rule, when the optimal value is small, these algorithms can be improved by a factor of $tilde Omega(sqrt{s})$ via LP rounding. Our upper and lower bounds are a significant improvement over previous results, and taken together, not only enable us to perform a finer comparison of greedy algorithms for these problems, but also provide analytic justification for using such algorithms in practice.
We study online pricing algorithms for the Bayesian selection problem with production constraints and its generalization to the laminar matroid Bayesian online selection problem. Consider a firm producing (or receiving) multiple copies of different p
We study two notions of stability in multiwinner elections that are based on the Condorcet criterion. The first notion was introduced by Gehrlein: A committee is stable if each committee member is preferred to each non-member by a (possibly weak) maj
A patient seller aims to sell a good to an impatient buyer (i.e., one who discounts utility over time). The buyer will remain in the market for a period of time $T$, and her private value is drawn from a publicly known distribution. What is the reven
A preference profile is single-peaked on a tree if the candidate set can be equipped with a tree structure so that the preferences of each voter are decreasing from their top candidate along all paths in the tree. This notion was introduced by Demang
The probabilistic serial (PS) rule is one of the most prominent randomized rules for the assignment problem. It is well-known for its superior fairness and welfare properties. However, PS is not immune to manipulative behaviour by the agents. We exam