ﻻ يوجد ملخص باللغة العربية
In the committee selection problem, we are given $m$ candidates, and $n$ voters. Candidates can have different weights. A committee is a subset of candidates, and its weight is the sum of weights of its candidates. Each voter expresses an ordinal ranking over all possible committees. The only assumption we make on preferences is monotonicity: If $S subseteq S$ are two committees, then any voter weakly prefers $S$ to $S$. We study a general notion of group fairness via stability: A committee of given total weight $K$ is stable if no coalition of voters can deviate and choose a committee of proportional weight, so that all these voters strictly prefer the new committee to the existing one. Extending this notion to approximation, for parameter $c ge 1$, a committee $S$ of weight $K$ is said to be $c$-approximately stable if for any other committee $S$ of weight $K$, the fraction of voters that strictly prefer $S$ to $S$ is strictly less than $frac{c K}{K}$. When $c = 1$, this condition is equivalent to classical core stability. The question we ask is: Does a $c$-approximately stable committee of weight at most any given value $K$ always exist for constant $c$? It is relatively easy to show that there exist monotone preferences for which $c ge 2$. However, even for simple and widely studied preference structures, a non-trivial upper bound on $c$ has been elusive. In this paper, we show that $c = O(1)$ for all monotone preference structures. Our proof proceeds via showing an existence result for a randomized notion of stability, and iteratively rounding the resulting fractional solution.
In this paper, we study fairness in committee selection problems. We consider a general notion of fairness via stability: A committee is stable if no coalition of voters can deviate and choose a committee of proportional size, so that all these voter
We consider the problem of committee selection from a fixed set of candidates where each candidate has multiple quantifiable attributes. To select the best possible committee, instead of voting for a candidate, a voter is allowed to approve the prefe
We present a mechanism for computing asymptotically stable school optimal matchings, while guaranteeing that it is an asymptotic dominant strategy for every student to report their true preferences to the mechanism. Our main tool in this endeavor is
We make three different types of contributions to cost-sharing: First, we identify several new classes of combinatorial cost functions that admit incentive-compatible mechanisms achieving both a constant-factor approximation of budget-balance and a p
We identify the first static credible mechanism for multi-item additive auctions that achieves a constant factor of the optimal revenue. This is one instance of a more general framework for designing two-part tariff auctions, adapting the duality fra