Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMaximizing Welfare with Incentive-Aware Evaluation Mechanisms
149
0
0.0
(
0
)
Added by
Nika Haghtalab
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Motivated by applications such as college admission and insurance rate determination, we propose an evaluation problem where the inputs are controlled by strategic individuals who can modify their features at a cost. A learner can only partially observe the features, and aims to classify individuals with respect to a quality score. The goal is to design an evaluation mechanism that maximizes the overall quality score, i.e., welfare, in the population, taking any strategic updating into account. We further study the algorithmic aspect of finding the welfare maximizing evaluation mechanism under two specific settings in our model. When scores are linear and mechanisms use linear scoring rules on the observable features, we show that the optimal evaluation mechanism is an appropriate projection of the quality score. When mechanisms must use linear thresholds, we design a polynomial time algorithm with a (1/4)-approximation guarantee when the underlying feature distribution is sufficiently smooth and admits an oracle for finding dense regions. We extend our results to settings where the prior distribution is unknown and must be learned from samples.
rate research
Read More
A common objective in mechanism design is to choose the outcome (for example, allocation of resources) that maximizes the sum of the agents valuations, without introducing incentives for agents to misreport their preferences. The class of Groves mechanisms achieves this; however, these mechanisms require the agents to make payments, thereby reducing the agents total welfare. In this paper we introduce a measure for comparing two mechanisms with respect to the final welfare they generate. This measure induces a partial order on mechanisms and we study the question of finding minimal elements with respect to this partial order. In particular, we say a non-deficit Groves mechanism is welfare undominated if there exists no other non-deficit Groves mechanism that always has a smaller or equal sum of payments. We focus on two domains: (i) auctions with multiple identical units and unit-demand bidders, and (ii) mechanisms for public project problems. In the first domain we analytically characterize all welfare undominated Groves mechanisms that are anonymous and have linear payment functions, by showing that the family of optimal-in-expectation linear redistribution mechanisms, which were introduced in [6] and include the Bailey-Cavallo mechanism [1,2], coincides with the family of welfare undominated Groves mechanisms that are anonymous and linear in the setting we study. In the second domain we show that the classic VCG (Clarke) mechanism is welfare undominated for the class of public project problems with equal participation costs, but is not undominated for a more general class.
Mobile crowdsensing has shown a great potential to address large-scale data sensing problems by allocating sensing tasks to pervasive mobile users. The mobile users will participate in a crowdsensing platform if they can receive satisfactory reward. In this paper, to effectively and efficiently recruit sufficient number of mobile users, i.e., participants, we investigate an optimal incentive mechanism of a crowdsensing service provider. We apply a two-stage Stackelberg game to analyze the participation level of the mobile users and the optimal incentive mechanism of the crowdsensing service provider using backward induction. In order to motivate the participants, the incentive is designed by taking into account the social network effects from the underlying mobile social domain. For example, in a crowdsensing-based road traffic information sharing application, a user can get a better and accurate traffic report if more users join and share their road information. We derive the analytical expressions for the discriminatory incentive as well as the uniform incentive mechanisms. To fit into practical scenarios, we further formulate a Bayesian Stackelberg game with incomplete information to analyze the interaction between the crowdsensing service provider and mobile users, where the social structure information (the social network effects) is uncertain. The existence and uniqueness of the Bayesian Stackelberg equilibrium are validated by identifying the best response strategies of the mobile users. Numerical results corroborate the fact that the network effects tremendously stimulate higher mobile participation level and greater revenue of the crowdsensing service provider. In addition, the social structure information helps the crowdsensing service provider to achieve greater revenue gain.
While microtask crowdsourcing provides a new way to solve large volumes of small tasks at a much lower price compared with traditional in-house solutions, it suffers from quality problems due to the lack of incentives. On the other hand, providing incentives for microtask crowdsourcing is challenging since verifying the quality of submitted solutions is so expensive that will negate the advantage of microtask crowdsourcing. We study cost-effective incentive mechanisms for microtask crowdsourcing in this paper. In particular, we consider a model with strategic workers, where the primary objective of a worker is to maximize his own utility. Based on this model, we analyze two basic mechanisms widely adopted in existing microtask crowdsourcing applications and show that, to obtain high quality solutions from workers, their costs are constrained by some lower bounds. We then propose a cost-effective mechanism that employs quality-aware worker training as a tool to stimulate workers to provide high quality solutions. We prove theoretically that the proposed mechanism, when properly designed, can obtain high quality solutions with an arbitrarily low cost. Beyond its theoretical guarantees, we further demonstrate the effectiveness of our proposed mechanisms through a set of behavioral experiments.
Mobile Crowdsensing has shown a great potential to address large-scale problems by allocating sensing tasks to pervasive Mobile Users (MUs). The MUs will participate in a Crowdsensing platform if they can receive satisfactory reward. In this paper, in order to effectively and efficiently recruit sufficient MUs, i.e., participants, we investigate an optimal reward mechanism of the monopoly Crowdsensing Service Provider (CSP). We model the rewarding and participating as a two-stage game, and analyze the MUs participation level and the CSPs optimal reward mechanism using backward induction. At the same time, the reward is designed taking the underlying social network effects amid the mobile social network into account, for motivating the participants. Namely, one MU will obtain additional benefits from information contributed or shared by local neighbours in social networks. We derive the analytical expressions for the discriminatory reward as well as uniform reward with complete information, and approximations of reward incentive with incomplete information. Performance evaluation reveals that the network effects tremendously stimulate higher mobile participation level and greater revenue of the CSP. In addition, the discriminatory reward enables the CSP to extract greater surplus from this Crowdsensing service market.
We consider the problem of allocating a set of divisible goods to $N$ agents in an online manner, aiming to maximize the Nash social welfare, a widely studied objective which provides a balance between fairness and efficiency. The goods arrive in a sequence of $T$ periods and the value of each agent for a good is adversarially chosen when the good arrives. We first observe that no online algorithm can achieve a competitive ratio better than the trivial $O(N)$, unless it is given additional information about the agents values. Then, in line with the emerging area of algorithms with predictions, we consider a setting where for each agent, the online algorithm is only given a prediction of her monopolist utility, i.e., her utility if all goods were given to her alone (corresponding to the sum of her values over the $T$ periods). Our main result is an online algorithm whose competitive ratio is parameterized by the multiplicative errors in these predictions. The algorithm achieves a competitive ratio of $O(log N)$ and $O(log T)$ if the predictions are perfectly accurate. Moreover, the competitive ratio degrades smoothly with the errors in the predictions, and is surprisingly robust: the logarithmic competitive ratio holds even if the predictions are very inaccurate. We complement this positive result by showing that our bounds are essentially tight: no online algorithm, even if provided with perfectly accurate predictions, can achieve a competitive ratio of $O(log^{1-epsilon} N)$ or $O(log^{1-epsilon} T)$ for any constant $epsilon>0$.
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
