Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTruthful Information Elicitation from Hybrid Crowds
299
0
0.0
(
0
)
Added by
Sikai Ruan
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Suppose a decision maker wants to predict weather tomorrow by eliciting and aggregating information from crowd. How can the decision maker incentivize the crowds to report their information truthfully? Many truthful peer prediction mechanisms have been proposed for homogeneous agents, whose types are drawn from the same distribution. However, in many situations, the population is a hybrid crowd of different types of agents with different forms of information, and the decision maker has neither the identity of any individual nor the proportion of each types of agents in the crowd. Ignoring the heterogeneity among the agent may lead to inefficient of biased information, which would in turn lead to suboptimal decisions. In this paper, we propose the first framework for information elicitation from hybrid crowds, and two mechanisms to motivate agents to report their information truthfully. The first mechanism combines two mechanisms via linear transformations and the second is based on mutual information. With two mechanisms, the decision maker can collect high quality information from hybrid crowds, and learns the expertise of agents.
rate research
Read More
We consider two-alternative elections where voters preferences depend on a state variable that is not directly observable. Each voter receives a private signal that is correlated to the state variable. Voters may be contingent with different preferences in different states; or predetermined with the same preference in every state. In this setting, even if every voter is a contingent voter, agents voting according to their private information need not result in the adoption of the universally preferred alternative, because the signals can be systematically biased. We present an easy-to-deploy mechanism that elicits and aggregates the private signals from the voters, and outputs the alternative that is favored by the majority. In particular, voters truthfully reporting their signals forms a strong Bayes Nash equilibrium (where no coalition of voters can deviate and receive a better outcome).
We consider the problem of fitting a linear model to data held by individuals who are concerned about their privacy. Incentivizing most players to truthfully report their data to the analyst constrains our design to mechanisms that provide a privacy guarantee to the participants; we use differential privacy to model individuals privacy losses. This immediately poses a problem, as differentially private computation of a linear model necessarily produces a biased estimation, and existing approaches to design mechanisms to elicit data from privacy-sensitive individuals do not generalize well to biased estimators. We overcome this challenge through an appropriate design of the computation and payment scheme.
We provide the first separation in the approximation guarantee achievable by truthful and non-truthful combinatorial auctions with polynomial communication. Specifically, we prove that any truthful mechanism guaranteeing a $(frac{3}{4}-frac{1}{240}+varepsilon)$-approximation for two buyers with XOS valuations over $m$ items requires $exp(Omega(varepsilon^2 cdot m))$ communication, whereas a non-truthful algorithm by Dobzinski and Schapira [SODA 2006] and Feige [2009] is already known to achieve a $frac{3}{4}$-approximation in $poly(m)$ communication. We obtain our separation by proving that any {simultaneous} protocol ({not} necessarily truthful) which guarantees a $(frac{3}{4}-frac{1}{240}+varepsilon)$-approximation requires communication $exp(Omega(varepsilon^2 cdot m))$. The taxation complexity framework of Dobzinski [FOCS 2016] extends this lower bound to all truthful mechanisms (including interactive truthful mechanisms).
We consider a fundamental dynamic allocation problem motivated by the problem of $textit{securities lending}$ in financial markets, the mechanism underlying the short selling of stocks. A lender would like to distribute a finite number of identical copies of some scarce resource to $n$ clients, each of whom has a private demand that is unknown to the lender. The lender would like to maximize the usage of the resource $mbox{---}$ avoiding allocating more to a client than her true demand $mbox{---}$ but is constrained to sell the resource at a pre-specified price per unit, and thus cannot use prices to incentivize truthful reporting. We first show that the Bayesian optimal algorithm for the one-shot problem $mbox{---}$ which maximizes the resources expected usage according to the posterior expectation of demand, given reports $mbox{---}$ actually incentivizes truthful reporting as a dominant strategy. Because true demands in the securities lending problem are often sensitive information that the client would like to hide from competitors, we then consider the problem under the additional desideratum of (joint) differential privacy. We give an algorithm, based on simple dynamics for computing market equilibria, that is simultaneously private, approximately optimal, and approximately dominant-strategy truthful. Finally, we leverage this private algorithm to construct an approximately truthful, optimal mechanism for the extensive form multi-round auction where the lender does not have access to the true joint distributions between clients requests and demands.
We consider the problem of purchasing data for machine learning or statistical estimation. The data analyst has a budget to purchase datasets from multiple data providers. She does not have any test data that can be used to evaluate the collected data and can assign payments to data providers solely based on the collected datasets. We consider the problem in the standard Bayesian paradigm and in two settings: (1) data are only collected once; (2) data are collected repeatedly and each days data are drawn independently from the same distribution. For both settings, our mechanisms guarantee that truthfully reporting ones dataset is always an equilibrium by adopting techniques from peer prediction: pay each provider the mutual information between his reported data and other providers reported data. Depending on the data distribution, the mechanisms can also discourage misreports that would lead to inaccurate predictions. Our mechanisms also guarantee individual rationality and budget feasibility for certain underlying distributions in the first setting and for all distributions in the second setting.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
