ترغب بنشر مسار تعليمي؟ اضغط هنا

Approximately Stable Committee Selection

180   0   0.0 ( 0 )
 نشر من قبل Kangning Wang
 تاريخ النشر 2019
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English




اسأل ChatGPT حول البحث

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 s strictly prefer the new committee to the existing one. Our main contribution is to extend this definition to stability of a distribution (or lottery) over committees. We consider two canonical voter preference models: the Approval Set setting where each voter approves a set of candidates and prefers committees with larger intersection with this set; and the Ranking setting where each voter ranks committees based on how much she likes her favorite candidate in a committee. Our main result is to show that stable lotteries always exist for these canonical preference models. Interestingly, given preferences of voters over committees, the procedure for computing an approximately stable lottery is the same for both models and therefore extends to the setting where some voters have the former preference structure and others have the latter. Our existence proof uses the probabilistic method and a new large deviation inequality that may be of independent interest.
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 rred attributes of a given candidate. Though attribute based preference is addressed in several contexts, committee selection problem with attribute approval of voters has not been attempted earlier. A committee formed on attribute preferences is more likely to be a better representative of the qualities desired by the voters and is less likely to be susceptible to collusion or manipulation. In this work, we provide a formal study of the different aspects of this problem and define properties of weak unanimity, strong unanimity, simple justified representations and compound justified representation, that are required to be satisfied by the selected committee. We show that none of the existing vote/approval aggregation rules satisfy these new properties for attribute aggregation. We describe a greedy approach for attribute aggregation that satisfies the first three properties, but not the fourth, i.e., compound justified representation, which we prove to be NP-complete. Furthermore, we prove that finding a committee with justified representation and the highest approval voting score is NP-complete.
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 differential privacy: we give an algorithm that coordinates a stable matching using differentially private signals, which lead to our truthfulness guarantee. This is the first setting in which it is known how to achieve nontrivial truthfulness guarantees for students when computing school optimal matchings, assuming worst- case preferences (for schools and students) in large markets.
144 - Tim Roughgarden 2006
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 olylogarithmic approximation of the social cost formulation of efficiency. Second, we prove a new, optimal lower bound on the approximate efficiency of every budget-balanced Moulin mechanism for Steiner tree or SSRoB cost functions. This lower bound exposes a latent approximation hierarchy among different cost-sharing problems. Third, we show that weakening the definition of incentive-compatibility to strategyproofness can permit exponentially more efficient approximately budget-balanced mechanisms, in particular for set cover cost-sharing problems.
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 mework of Cai et al [CDW16]. Given a (not necessarily incentive compatible) auction format $A$ satisfying certain technical conditions, our framework augments the auction with a personalized entry fee for each bidder, which must be paid before the auction can be accessed. These entry fees depend only on the prior distribution of bidder types, and in particular are independent of realized bids. Our framework can be used with many common auction formats, such as simultaneous first-price, simultaneous second-price, and simultaneous all-pay auctions. If all-pay auctions are used, we prove that the resulting mechanism is credible in the sense that the auctioneer cannot benefit by deviating from the stated mechanism after observing agent bids. If second-price auctions are used, we obtain a truthful $O(1)$-approximate mechanism with fixed entry fees that are amenable to tuning via online learning techniques. Our results for first price and all-pay are the first revenue guarantees of non-truthful mechanisms in multi-dimensional environments; an open question in the literature [RST17].
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا