Trustworthy Preference Completion in Social Choice

• URL: http://arxiv.org/abs/2012.07228v1
• Date: Mon, 14 Dec 2020 03:03:13 GMT
• Title: Trustworthy Preference Completion in Social Choice
• Authors: Lei Li, Minghe Xue, Huanhuan Chen, Xindong Wu
• Abstract summary: It is impractical to ask agents to provide linear orders over all alternatives, for these partial rankings it is necessary to conduct preference completion. A trust-based anchor-kNN algorithm is proposed to find $k$-nearest trustworthy neighbors of the agent with trust-oriented Kendall-Tau distances. A certain common voting rule for the first $k$ trustworthy neighboring agents based on certainty and conflict can be taken to conduct the trustworthy preference completion.
• Score: 36.91054060923998
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: As from time to time it is impractical to ask agents to provide linear orders over all alternatives, for these partial rankings it is necessary to conduct preference completion. Specifically, the personalized preference of each agent over all the alternatives can be estimated with partial rankings from neighboring agents over subsets of alternatives. However, since the agents' rankings are nondeterministic, where they may provide rankings with noise, it is necessary and important to conduct the trustworthy preference completion. Hence, in this paper firstly, a trust-based anchor-kNN algorithm is proposed to find $k$-nearest trustworthy neighbors of the agent with trust-oriented Kendall-Tau distances, which will handle the cases when an agent exhibits irrational behaviors or provides only noisy rankings. Then, for alternative pairs, a bijection can be built from the ranking space to the preference space, and its certainty and conflict can be evaluated based on a well-built statistical measurement Probability-Certainty Density Function. Therefore, a certain common voting rule for the first $k$ trustworthy neighboring agents based on certainty and conflict can be taken to conduct the trustworthy preference completion. The properties of the proposed certainty and conflict have been studied empirically, and the proposed approach has been experimentally validated compared to state-of-arts approaches with several data sets.

Related papers

• Eliciting Kemeny Rankings [6.971011179091351]
  We find approximation bounds for Kemeny rankings dependant on confidence intervals over estimated winning probabilities of arms. We formulate several adaptive sampling methods that use look-aheads to estimate how much confidence intervals might be tightened.
  arXiv  Detail & Related papers  (2023-12-18T19:14:42Z)
• Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
  We revisit the likelihood-based inference principle and propose to use likelihood ratios to construct valid confidence sequences. Our method is especially suitable for problems with well-specified likelihoods. We show how to provably choose the best sequence of estimators and shed light on connections to online convex optimization.
  arXiv  Detail & Related papers  (2023-11-08T00:10:21Z)
• Fairness in Ranking under Disparate Uncertainty [24.401219403555814]
  We argue that ranking can introduce unfairness if the uncertainty of the underlying relevance model differs between groups of options. We propose Equal-Opportunity Ranking (EOR) as a new fairness criterion for ranking. We show that EOR corresponds to a group-wise fair lottery among the relevant options even in the presence of disparate uncertainty.
  arXiv  Detail & Related papers  (2023-09-04T13:49:48Z)
• Pure Exploration under Mediators' Feedback [63.56002444692792]
  Multi-armed bandits are a sequential-decision-making framework, where, at each interaction step, the learner selects an arm and observes a reward. We consider the scenario in which the learner has access to a set of mediators, each of which selects the arms on the agent's behalf according to a and possibly unknown policy. We propose a sequential decision-making strategy for discovering the best arm under the assumption that the mediators' policies are known to the learner.
  arXiv  Detail & Related papers  (2023-08-29T18:18:21Z)
• Birds of a Feather Trust Together: Knowing When to Trust a Classifier via Adaptive Neighborhood Aggregation [30.34223543030105]
  We show how NeighborAgg can leverage the two essential information via an adaptive neighborhood aggregation. We also extend our approach to the closely related task of mislabel detection and provide a theoretical coverage guarantee to bound the false negative.
  arXiv  Detail & Related papers  (2022-11-29T18:43:15Z)
• Cautious Learning of Multiattribute Preferences [2.6151761714896122]
  This paper is dedicated to a cautious learning methodology for predicting preferences between alternatives characterized by binary attributes. By "cautious", we mean that the model learned to represent the multi-attribute preferences is general enough to be compatible with any strict weak order on the alternatives.
  arXiv  Detail & Related papers  (2022-06-15T07:54:16Z)
• Peer Selection with Noisy Assessments [43.307040330622186]
  We extend PeerNomination, the most accurate peer reviewing algorithm to date, into WeightedPeerNomination. We show analytically that a weighting scheme can improve the overall accuracy of the selection significantly.
  arXiv  Detail & Related papers  (2021-07-21T14:47:11Z)
• Learning Strategies in Decentralized Matching Markets under Uncertain Preferences [91.3755431537592]
  We study the problem of decision-making in the setting of a scarcity of shared resources when the preferences of agents are unknown a priori. Our approach is based on the representation of preferences in a reproducing kernel Hilbert space. We derive optimal strategies that maximize agents' expected payoffs.
  arXiv  Detail & Related papers  (2020-10-29T03:08:22Z)
• Necessarily Optimal One-Sided Matchings [49.0517583218216]
  We study the classical problem of matching $n$ agents to $n$ objects, where the agents have ranked preferences over the objects. Instead of asking the agents to report their complete preferences, our goal is to learn a desirable matching from partial preferences. We design efficient algorithms to check if a given matching is NPO or NRM, and to check whether such a matching exists given top-$k$ partial preferences.
  arXiv  Detail & Related papers  (2020-07-17T16:01:34Z)
• SetRank: A Setwise Bayesian Approach for Collaborative Ranking from Implicit Feedback [50.13745601531148]
  We propose a novel setwise Bayesian approach for collaborative ranking, namely SetRank, to accommodate the characteristics of implicit feedback in recommender system. Specifically, SetRank aims at maximizing the posterior probability of novel setwise preference comparisons. We also present the theoretical analysis of SetRank to show that the bound of excess risk can be proportional to $sqrtM/N$.
  arXiv  Detail & Related papers  (2020-02-23T06:40:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.