Mechanism Design for Crowdsourcing: An Optimal 1-1/e Competitive Budget-Feasible Mechanism for Large Markets

Authors

Nima Anari, Gagan Goel, Afshin Nikzad

Type: Article

Publication Date: 2014-10-01

Citations: 75

DOI: https://doi.org/10.1109/focs.2014.36

Ask PDF

Abstract

In this paper we consider a mechanism design problem in the context of large-scale crowdsourcing markets such as Amazon's Mechanical Turk mturk, ClickWorker clickworker, CrowdFlower crowdflower. In these markets, there is a requester who wants to hire workers to accomplish some tasks. Each worker is assumed to give some utility to the requester on getting hired. Moreover each worker has a minimum cost that he wants to get paid for getting hired. This minimum cost is assumed to be private information of the workers. The question then is -- if the requester has a limited budget, how to design a direct revelation mechanism that picks the right set of workers to hire in order to maximize the requester's utility? We note that although the previous work (Singer (2010) chen et al. (2011)) has studied this problem, a crucial difference in which we deviate from earlier work is the notion of large-scale markets that we introduce in our model. Without the large market assumption, it is known that no mechanism can achieve a competitive ratio better than 0.414 and 0.5 for deterministic and randomized mechanisms respectively (while the best known deterministic and randomized mechanisms achieve an approximation ratio of 0.292 and 0.33 respectively). In this paper, we design a budget-feasible mechanism for large markets that achieves a competitive ratio of 1 - 1/e ≃ 0.63. Our mechanism can be seen as a generalization of an alternate way to look at the proportional share mechanism, which is used in all the previous works so far on this problem. Interestingly, we can also show that our mechanism is optimal by showing that no truthful mechanism can achieve a factor better than 1 - 1/e, thus, fully resolving this setting. Finally we consider the more general case of submodular utility functions and give new and improved mechanisms for the case when the market is large.

Locations

arXiv (Cornell University)
View PDF

Ask a Question About This Paper

Summary

None

2025-04-30

Alfin Luluk Kamalia , Nina Queena Hadi Putri

None

2025-05-13

None

2022-06-15

None

2025-05-13

None

2025-04-30

None

2025-05-20

None

2025-04-30

None

2024-06-01

None

2025-05-21

None

2025-02-28

None

2022-12-03

None

2025-05-20

None

2025-05-01

None

2025-05-13

None

2014-07-02

None

2025-05-16

None

2025-05-15

None

2024-08-12

None

2023-06-27

None

2011-08-01

Double or Nothing: Multiplicative Incentive Mechanisms for Crowdsourcing

2014-08-06

Nihar B. Shah , Dengyong Zhou

Crowdsourcing has gained immense popularity in machine learning applications for obtaining large amounts of labeled data. Crowdsourcing is cheap and fast, but suffers from the problem of low-quality data. To … Crowdsourcing has gained immense popularity in machine learning applications for obtaining large amounts of labeled data. Crowdsourcing is cheap and fast, but suffers from the problem of low-quality data. To address this fundamental challenge in crowdsourcing, we propose a simple payment mechanism to incentivize workers to answer only the questions that they are sure of and skip the rest. We show that surprisingly, under a mild and natural no-free-lunch requirement, this mechanism is the one and only incentive-compatible payment mechanism possible. We also show that among all possible incentive-compatible mechanisms (that may or may not satisfy no-free-lunch), our mechanism makes the smallest possible payment to spammers. We further extend our results to a more general setting in which workers are required to provide a quantized confidence for each question. Interestingly, this unique mechanism takes a multiplicative form. The simplicity of the mechanism is an added benefit. In preliminary experiments involving over 900 worker-task pairs, we observe a significant drop in the error rates under this unique mechanism for the same or lower monetary expenditure.

Budget-Feasible Mechanism Design for Non-monotone Submodular Objectives: Offline and Online

2022-01-19

Georgios Amanatidis , Pieter Kleer , Guido Schäfer

The framework of budget-feasible mechanism design studies procurement auctions where the auctioneer (buyer) aims to maximize his valuation function subject to a hard budget constraint. We study the problem of … The framework of budget-feasible mechanism design studies procurement auctions where the auctioneer (buyer) aims to maximize his valuation function subject to a hard budget constraint. We study the problem of designing truthful mechanisms that have good approximation guarantees and never pay the participating agents (sellers) more than the budget. We focus on the case of general (non-monotone) submodular valuation functions and derive the first truthful, budget-feasible, and O(1)-approximation mechanisms that run in polynomial time in the value query model, for both offline and online auctions. Prior to our work, the only O(1)-approximation mechanism known for non-monotone submodular objectives required an exponential number of value queries. At the heart of our approach lies a novel greedy algorithm for non-monotone submodular maximization under a knapsack constraint. Our algorithm builds two candidate solutions simultaneously (to achieve a good approximation), yet ensures that agents cannot jump from one solution to the other (to implicitly enforce truthfulness). The fact that in our mechanism the agents are not ordered according to their marginal value per cost allows us to appropriately adapt these ideas to the online setting as well. To further illustrate the applicability of our approach, we also consider the case where additional feasibility constraints are present, for example, at most k agents can be selected. We obtain O(p)-approximation mechanisms for both monotone and non-monotone submodular objectives, when the feasible solutions are independent sets of a p-system. With the exception of additive valuation functions, no mechanisms were known for this setting prior to our work. Finally, we provide lower bounds suggesting that, when one cares about nontrivial approximation guarantees in polynomial time, our results are, asymptotically, the best possible.

View PDF Chat

Coverage, Matching, and Beyond: New Results on Budgeted Mechanism Design

2016-01-01

Georgios Amanatidis , Georgios Birmpas , Evangelos Markakis

View PDF Chat

On Budget-Feasible Mechanism Design for Symmetric Submodular Objectives

2017-01-01

Georgios Amanatidis , Georgios Birmpas , Evangelos Markakis

View PDF Chat

Mechanism Design with Predicted Task Revenue for Bike Sharing Systems

2019-01-01

Hongtao Lv , Chaoli Zhang , Zhenzhe Zheng +3 more

Bike sharing systems have been widely deployed around the world in recent years. A core problem in such systems is to reposition the bikes so that the distribution of bike … Bike sharing systems have been widely deployed around the world in recent years. A core problem in such systems is to reposition the bikes so that the distribution of bike supply is reshaped to better match the dynamic bike demand. When the bike-sharing company or platform is able to predict the revenue of each reposition task based on historic data, an additional constraint is to cap the payment for each task below its predicted revenue. In this paper, we propose an incentive mechanism called {\em TruPreTar} to incentivize users to park bicycles at locations desired by the platform toward rebalancing supply and demand. TruPreTar possesses four important economic and computational properties such as truthfulness and budget feasibility. Furthermore, we prove that even when the payment budget is tight, the total revenue still exceeds or equals the budget. Otherwise, TruPreTar achieves 2-approximation as compared to the optimal (revenue-maximizing) solution, which is close to the lower bound of at least $\sqrt{2}$ that we also prove. Using an industrial dataset obtained from a large bike-sharing company, our experiments show that TruPreTar is effective in rebalancing bike supply and demand and, as a result, generates high revenue that outperforms several benchmark mechanisms.

View PDF Chat

Mechanism Design with Predicted Task Revenue for Bike Sharing Systems

2020-04-03

Hongtao Lv , Chaoli Zhang , Zhenzhe Zheng +3 more

Bike sharing systems have been widely deployed around the world in recent years. A core problem in such systems is to reposition the bikes so that the distribution of bike … Bike sharing systems have been widely deployed around the world in recent years. A core problem in such systems is to reposition the bikes so that the distribution of bike supply is reshaped to better match the dynamic bike demand. When the bike-sharing company or platform is able to predict the revenue of each reposition task based on historic data, an additional constraint is to cap the payment for each task below its predicted revenue. In this paper, we propose an incentive mechanism called TruPreTar to incentivize users to park bicycles at locations desired by the platform toward rebalancing supply and demand. TruPreTar possesses four important economic and computational properties such as truthfulness and budget feasibility. Furthermore, we prove that even when the payment budget is tight, the total revenue still exceeds or equals the budget. Otherwise, TruPreTar achieves 2-approximation as compared to the optimal (revenue-maximizing) solution, which is close to the lower bound of at least √2 that we also prove. Using an industrial dataset obtained from a large bike-sharing company, our experiments show that TruPreTar is effective in rebalancing bike supply and demand and, as a result, generates high revenue that outperforms several benchmark mechanisms.

View PDF Chat

FL-Market: Trading Private Models in Federated Learning

2021-01-01

Shuyuan Zheng , Yang Cao , Masatoshi Yoshikawa +2 more

The difficulty in acquiring a sufficient amount of training data is a major bottleneck for machine learning (ML) based data analytics. Recently, commoditizing ML models has been proposed as an … The difficulty in acquiring a sufficient amount of training data is a major bottleneck for machine learning (ML) based data analytics. Recently, commoditizing ML models has been proposed as an economical and moderate solution to ML-oriented data acquisition. However, existing model marketplaces assume that the broker can access data owners' private training data, which may not be realistic in practice. In this paper, to promote trustworthy data acquisition for ML tasks, we propose FL-Market, a locally private model marketplace that protects privacy not only against model buyers but also against the untrusted broker. FL-Market decouples ML from the need to centrally gather training data on the broker's side using federated learning, an emerging privacy-preserving ML paradigm in which data owners collaboratively train an ML model by uploading local gradients (to be aggregated into a global gradient for model updating). Then, FL-Market enables data owners to locally perturb their gradients by local differential privacy and thus further prevents privacy risks. To drive FL-Market, we propose a deep learning-empowered auction mechanism for intelligently deciding the local gradients' perturbation levels and an optimal aggregation mechanism for aggregating the perturbed gradients. Our auction and aggregation mechanisms can jointly maximize the global gradient's accuracy, which optimizes model buyers' utility. Our experiments verify the effectiveness of the proposed mechanisms.

View PDF Chat

Simple and Efficient Budget Feasible Mechanisms for Monotone Submodular Valuations

2018-01-01

Pooya Jalaly Khalilabadi , Éva Tardos

View PDF Chat

Truthful Multi-unit Procurements with Budgets

2014-01-01

Hau Chan , Jing Chen

We study procurement games where each seller supplies multiple units of his item, with a cost per unit known only to him. The buyer can purchase any number of units … We study procurement games where each seller supplies multiple units of his item, with a cost per unit known only to him. The buyer can purchase any number of units from each seller, values different combinations of the items differently, and has a budget for his total payment. For a special class of procurement games, the {\em bounded knapsack} problem, we show that no universally truthful budget-feasible mechanism can approximate the optimal value of the buyer within $\ln n$, where $n$ is the total number of units of all items available. We then construct a polynomial-time mechanism that gives a $4(1+\ln n)$-approximation for procurement games with {\em concave additive valuations}, which include bounded knapsack as a special case. Our mechanism is thus optimal up to a constant factor. Moreover, for the bounded knapsack problem, given the well-known FPTAS, our results imply there is a provable gap between the optimization domain and the mechanism design domain. Finally, for procurement games with {\em sub-additive valuations}, we construct a universally truthful budget-feasible mechanism that gives an $O(\frac{\log^2 n}{\log \log n})$-approximation in polynomial time with a demand oracle.

View PDF Chat

Tight Revenue Gaps among Multi-Unit Mechanisms

2021-07-18

Yaonan Jin , Shunhua Jiang , Pinyan Lu +1 more

This paper considers Bayesian revenue maximization in the k-unit setting, where a monopolist seller has k copies of an indivisible item and faces n unit-demand buyers (whose value distributions can … This paper considers Bayesian revenue maximization in the k-unit setting, where a monopolist seller has k copies of an indivisible item and faces n unit-demand buyers (whose value distributions can be non-identical). Four basic mechanisms among others have been widely employed in practice and widely studied in the literature: Myerson Auction, Sequential Posted-Pricing, (k + 1)-th Price Auction with Anonymous Reserve, and Anonymous Pricing. Regarding a pair of mechanisms, we investigate the largest possible ratio between the two revenues (a.k.a. the revenue gap), over all possible value distributions of the buyers. Divide these four mechanisms into two groups: (i) the discriminating mechanism group, Myerson Auction and Sequential Posted-Pricing, and (ii) the anonymous mechanism group, Anonymous Reserve and Anonymous Pricing. Within one group, the involved two mechanisms have an asymptotically tight revenue gap of 1 + Θ(1 / √k). In contrast, any two mechanisms from the different groups have an asymptotically tight revenue gap of Θ(łog k).

View PDF Chat

Budget Feasible Mechanisms for Procurement Auctions with Divisible Agents

2022-01-01

Sophie Klumper , Guido Schäfer

View PDF Chat

Parallel Contests for Crowdsourcing Reviews: Existence and Quality of Equilibria

2022-09-19

Georgios Birmpas , Lyudmila Kovalchuk , Philip Lazos +1 more

Part of the design of many blockchains and cryptocurrencies includes a treasury, which periodically allocates collected funds to various projects that could be beneficial to their ecosystem. These projects are … Part of the design of many blockchains and cryptocurrencies includes a treasury, which periodically allocates collected funds to various projects that could be beneficial to their ecosystem. These projects are then voted on and selected by the users of the respective cryptocurrency. To better inform the users' choices, the proposals can be reviewed, in distributed fashion. Motivated by these intricacies, we study the problem of crowdsourcing reviews for different proposals, in parallel. During the reviewing phase, every reviewer can select the proposals to write reviews for, as well as the quality of each review. The quality levels follow certain very coarse community guidelines (since the review of the reviews has to be robust enough, even though it is also crowdsourced) and can have values such as 'excellent' or 'good'. Based on these scores and the distribution of reviews, every reviewer will receive some reward for their efforts. In this paper, we consider a simple and intuitive reward scheme and show that it always has pure Nash equilibria, under two different scenarios. In addition, we show that these equilibria guarantee constant factor approximations for two natural metrics: the total quality of all reviews, as well as the fraction of proposals that received at least one review, compared to the optimal outcome.

View PDF Chat

Optimal Budget-Feasible Mechanisms for Additive Valuations

2019-06-17

Nick Gravin , Yaonan Jin , Pinyan Lu +1 more

In this paper, we obtain the tight approximation guarantees for budget-feasible mechanisms with an additive buyer. We propose a new simple randomized mechanism with an approximation ratio of $2$, improving … In this paper, we obtain the tight approximation guarantees for budget-feasible mechanisms with an additive buyer. We propose a new simple randomized mechanism with an approximation ratio of $2$, improving the previous best known result of $3$. Our bound is tight with respect to either the optimal offline benchmark or its fractional relaxation. We also present a simple deterministic mechanism with the tight approximation guarantee of $3$ against the fractional optimum, improving the best known result of $(\sqrt2 + 2)$ against the weaker integral benchmark.

View PDF Chat

Two-Stage Auction Mechanism for Long-Term Participation in Crowdsourcing

2022-02-25

Timothy Shin Heng Mak , Albert Y. S. Lam

Crowdsourcing has become an important tool to collect data for various artificial intelligence applications, and auction can be an effective way to allocate work and determine reward in a crowdsourcing … Crowdsourcing has become an important tool to collect data for various artificial intelligence applications, and auction can be an effective way to allocate work and determine reward in a crowdsourcing platform. In this article, we focus on the crowdsourcing of small tasks such as image labeling and voice recording, where we face a number of challenges. First, workers have different limits on the amount of work they would be willing to do, and they may also misreport these limits in their bid for the work. Second, if the auction is repeated over time, unsuccessful workers may dropout of the system, reducing competition and diversity. To tackle these issues, we first extend the results of the celebrated Myerson’s optimal auction mechanism for a single-parameter bid to the case where the bid consists of the unit cost of work, the maximum amount of work one is willing to do, and the actual work completed. We show that a simple payment mechanism is sufficient to ensure a dominant strategy from the workers, and that this dominant strategy is robust to the true utility function of the workers. Second, we propose a novel, flexible work allocation mechanism, which allows the requester to balance between cost efficiency and equality. While cost minimization is obviously important, encouraging equality in the allocation of work increases the diversity of the workforce as well as promotes a long-term participation on the crowdsourcing platform. Our main results are proved analytically and validated through simulations.

View PDF Chat

Power of Bonus in Pricing for Crowdsourcing

2022-06-02

Suho Shin , Ho‐Yong Choi , Yung Yi +1 more

We consider a simple form of pricing for a crowdsourcing system, where pricing policy is published a priori, and workers then decide their task acceptance. Such a pricing form is … We consider a simple form of pricing for a crowdsourcing system, where pricing policy is published a priori, and workers then decide their task acceptance. Such a pricing form is widely adopted in practice for its simplicity, e.g., Amazon Mechanical Turk, although additional sophistication to pricing rule can enhance budget efficiency. With the goal of designing efficient and simple pricing rules, we study the impact of the following two design features in pricing policies: (i) personalization tailoring policy worker-by-worker and (ii) bonus payment to qualified task completion. In the Bayesian setting, where the only prior distribution of workers' profiles is available, we first study the Price of Agnosticism (PoA) that quantifies the utility gap between personalized and common pricing policies. We show that PoA is bounded within a constant factor under some mild conditions, and the impact of bonus is essential in common pricing. These analytic results imply that complex personalized pricing can be replaced by simple common pricing once it is equipped with a proper bonus payment. To provide insights on efficient common pricing, we then study the efficient mechanisms of bonus payment for several profile distribution regimes which may exist in practice. We provide primitive experiments on Amazon Mechanical Turk, which support our analytical findings[5].

View PDF Chat

Bayesian Budget Feasibility with Posted Pricing

2016-04-11

Eric Balkanski , Jason D. Hartline

We consider the problem of budget feasible mechanism design proposed by Singer, but in a Bayesian setting. A principal has a public value for hiring a subset of the agents … We consider the problem of budget feasible mechanism design proposed by Singer, but in a Bayesian setting. A principal has a public value for hiring a subset of the agents and a budget, while the agents have private costs for being hired. We consider both additive and submodular value functions of the principal. We show that there are simple, practical, ex post budget balanced posted pricing mechanisms that approximate the value obtained by the Bayesian optimal mechanism that is budget balanced only in expectation. A main motivating application for this work is crowdsourcing, e.g., on Mechanical Turk, where workers are drawn from a large population and posted pricing is standard. Our analysis methods relate to contention resolution schemes in submodular optimization of Vondràk et al. and the correlation gap analysis of Yan.

View PDF Chat

Tight Revenue Gaps among Multi-Unit Mechanisms

2021-01-01

Yaonan Jin , Shunhua Jiang , Pinyan Lu +1 more

This paper considers Bayesian revenue maximization in the $k$-unit setting, where a monopolist seller has $k$ copies of an indivisible item and faces $n$ unit-demand buyers (whose value distributions can … This paper considers Bayesian revenue maximization in the $k$-unit setting, where a monopolist seller has $k$ copies of an indivisible item and faces $n$ unit-demand buyers (whose value distributions can be non-identical). Four basic mechanisms among others have been widely employed in practice and widely studied in the literature: {\sf Myerson Auction}, {\sf Sequential Posted-Pricing}, {\sf $(k + 1)$-th Price Auction with Anonymous Reserve}, and {\sf Anonymous Pricing}. Regarding a pair of mechanisms, we investigate the largest possible ratio between the two revenues (a.k.a.\ the revenue gap), over all possible value distributions of the buyers. Divide these four mechanisms into two groups: (i)~the discriminating mechanism group, {\sf Myerson Auction} and {\sf Sequential Posted-Pricing}, and (ii)~the anonymous mechanism group, {\sf Anonymous Reserve} and {\sf Anonymous Pricing}. Within one group, the involved two mechanisms have an asymptotically tight revenue gap of $1 + \Theta(1 / \sqrt{k})$. In contrast, any two mechanisms from the different groups have an asymptotically tight revenue gap of $\Theta(\log k)$.

Optimal Budget-Feasible Mechanisms for Additive Valuations

2019-01-01

Nick Gravin , Yaonan Jin , Pinyan Lu +1 more

In this paper, we show a tight approximation guarantee for budget-feasible mechanisms with an additive buyer. We propose a new simple randomized mechanism with approximation ratio of $2$, improving the … In this paper, we show a tight approximation guarantee for budget-feasible mechanisms with an additive buyer. We propose a new simple randomized mechanism with approximation ratio of $2$, improving the previous best known result of $3$. Our bound is tight with respect to either the optimal offline benchmark, or its fractional relaxation. We also present a simple deterministic mechanism with the tight approximation guarantee of $3$ against the fractional optimum, improving the best known result of $(2+ \sqrt{2})$ for the weaker integral benchmark.

View PDF Chat

Optimization with Demand Oracles

2018-12-11

Ashwinkumar Badanidiyuru , Shahar Dobzinski , Sigal Oren

View PDF Chat

Power of Bonus in Pricing for Crowdsourcing

2021-12-14

Suho Shin , Ho‐Yong Choi , Yung Yi +1 more

View PDF Chat

Optimal Budget-Feasible Mechanisms for Additive Valuations

2020-10-16

Nick Gravin , Yaonan Jin , Pinyan Lu +1 more

In this article, we show a tight approximation guarantee for budget-feasible mechanisms with an additive buyer. We propose a new simple randomized mechanism with approximation ratio of 2, improving the … In this article, we show a tight approximation guarantee for budget-feasible mechanisms with an additive buyer. We propose a new simple randomized mechanism with approximation ratio of 2, improving the previous best known result of 3. Our bound is tight with respect to either the optimal offline benchmark or its fractional relaxation. We also present a simple deterministic mechanism with the tight approximation guarantee of 3 against the fractional optimum, improving the best known result of (2+ √ 2) for the weaker integral benchmark.

View PDF Chat

Budget Feasible Mechanisms on Matroids

2016-01-01

Stefano Leonardi , Gianpiero Monaco , Piotr Sankowski +1 more

Motivated by many practical applications, in this paper we study {\em budget feasible mechanisms} where the goal is to procure independent sets from matroids. More specifically, we are given a … Motivated by many practical applications, in this paper we study {\em budget feasible mechanisms} where the goal is to procure independent sets from matroids. More specifically, we are given a matroid $\mathcal{M}=(E,\mathcal{I})$ where each ground (indivisible) element is a selfish agent. The cost of each element (i.e., for selling the item or performing a service) is only known to the element itself. There is a buyer with a budget having additive valuations over the set of elements $E$. The goal is to design an incentive compatible (truthful) budget feasible mechanism which procures an independent set of the matroid under the given budget that yields the largest value possible to the buyer. Our result is a deterministic, polynomial-time, individually rational, truthful and budget feasible mechanism with $4$-approximation to the optimal independent set. Then, we extend our mechanism to the setting of matroid intersections in which the goal is to procure common independent sets from multiple matroids. We show that, given a polynomial time deterministic blackbox that returns $\alpha-$approximation solutions to the matroid intersection problem, there exists a deterministic, polynomial time, individually rational, truthful and budget feasible mechanism with $(3\alpha +1)-$approximation to the optimal common independent set.

View PDF Chat

Deterministic Budget-Feasible Clock Auctions

2021-01-01

Eric Balkanski , Pranav Garimidi , Vasilis Gkatzelis +2 more

We revisit the well-studied problem of budget-feasible procurement, where a buyer with a strict budget constraint seeks to acquire services from a group of strategic providers (the sellers). During the … We revisit the well-studied problem of budget-feasible procurement, where a buyer with a strict budget constraint seeks to acquire services from a group of strategic providers (the sellers). During the last decade, several strategyproof budget-feasible procurement auctions have been proposed, aiming to maximize the value of the buyer, while eliciting each seller's true cost for providing their service. These solutions predominantly take the form of randomized sealed-bid auctions: they ask the sellers to report their private costs and then use randomization to determine which subset of services will be procured and how much each of the chosen providers will be paid, ensuring that the total payment does not exceed budget. Our main result in this paper is a novel method for designing budget-feasible auctions, leading to solutions that outperform the previously proposed auctions in multiple ways. First, our solutions take the form of descending clock auctions, and thus satisfy a list of properties, such as obvious strategyproofness, group strategyproofness, transparency, and unconditional winner privacy; this makes these auctions much more likely to be used in practice. Second, in contrast to previous results that heavily depend on randomization, our auctions are deterministic. As a result, we provide an affirmative answer to one of the main open questions in this literature, asking whether a deterministic strategyproof auction can achieve a constant approximation when the buyer's valuation function is submodular over the set of services. In addition, we also provide the first deterministic budget-feasible auction that matches the approximation bound of the best-known randomized auction for the class of subadditive valuations. Finally, using our method, we improve the best-known approximation factor for monotone submodular valuations, which has been the focus of most of the prior work.

Liquid Price of Anarchy

2015-11-03

Yossi Azar , Michal Feldman , Nick Gravin +1 more

Incorporating budget constraints into the analysis of auctions has become increasingly important, as they model practical settings more accurately. The social welfare function, which is the standard measure of efficiency … Incorporating budget constraints into the analysis of auctions has become increasingly important, as they model practical settings more accurately. The social welfare function, which is the standard measure of efficiency in auctions, is inadequate for settings with budgets, since there may be a large disconnect between the value a bidder derives from obtaining an item and what can be liquidated from her. The Liquid Welfare objective function has been suggested as a natural alternative for settings with budgets. Simple auctions, like simultaneous item auctions, are evaluated by their performance at equilibrium using the Price of Anarchy (PoA) measure -- the ratio of the objective function value of the optimal outcome to the worst equilibrium. Accordingly, we evaluate the performance of simultaneous item auctions in budgeted settings by the Liquid Price of Anarchy (LPoA) measure -- the ratio of the optimal Liquid Welfare to the Liquid Welfare obtained in the worst equilibrium. Our main result is that the LPoA for mixed Nash equilibria is bounded by a constant when bidders are additive and items can be divided into sufficiently many discrete parts. Our proofs are robust, and can be extended to achieve similar bounds for simultaneous second price auctions as well as Bayesian Nash equilibria. For pure Nash equilibria, we establish tight bounds on the LPoA for the larger class of fractionally-subadditive valuations. To derive our results, we develop a new technique in which some bidders deviate (surprisingly) toward a non-optimal solution. In particular, this technique does not fit into the smoothness framework.

Online knapsack problem and budgeted truthful bipartite matching

2017-05-01

Rahul Vaze

Two related online problems: knapsack and truthful bipartite matching are considered. For these two problems, the common theme is how to `match' an arriving left vertex in an online fashion … Two related online problems: knapsack and truthful bipartite matching are considered. For these two problems, the common theme is how to `match' an arriving left vertex in an online fashion with any of the available right vertices, if at all, so as to maximize the sum of the value of the matched edges, subject to satisfying a sum-weight constraint on the matched left vertices. Assuming that the left vertices arrive in an uniformly random order (secretary model), two almost similar algorithms are proposed for the two problems, that are 2e competitive and 24 competitive, respectively. The proposed online bipartite matching algorithm is also shown to be truthful: there is no incentive for any left vertex to misreport its bid/weight. Direct applications of these problems include job allocation with load balancing, generalized adwords, crowdsourcing auctions, and matching wireless users to cooperative relays in device-to-device communication enabled cellular network.

View PDF Chat

Approval Voting and Incentives in Crowdsourcing

2020-06-22

Nihar B. Shah , Dengyong Zhou

The growing need for labeled training data has made crowdsourcing a vital tool for developing machine learning applications. Here, workers on a crowdsourcing platform are typically shown a list of … The growing need for labeled training data has made crowdsourcing a vital tool for developing machine learning applications. Here, workers on a crowdsourcing platform are typically shown a list of unlabeled items, and for each of these items, are asked to choose a label from one of the provided options. The workers in crowdsourcing platforms are not experts, thereby making it essential to judiciously elicit the information known to the workers. With respect to this goal, there are two key shortcomings of current systems: (i) the incentives of the workers are not aligned with those of the requesters; and (ii) the interface does not allow workers to convey their knowledge accurately by forcing them to make a single choice among a set of options. In this article, we address these issues by introducing approval voting to utilize the expertise of workers who have partial knowledge of the true answer and coupling it with two strictly proper scoring rules. We additionally establish attractive properties of optimality and uniqueness of our scoring rules. We also conduct preliminary empirical studies on Amazon Mechanical Turk, and the results of these experiments validate our approach.

View PDF Chat

Double or Nothing: Multiplicative Incentive Mechanisms for Crowdsourcing

2014-01-01

Nihar B. Shah , Dengyong Zhou

Crowdsourcing has gained immense popularity in machine learning applications for obtaining large amounts of labeled data. Crowdsourcing is cheap and fast, but suffers from the problem of low-quality data. To … Crowdsourcing has gained immense popularity in machine learning applications for obtaining large amounts of labeled data. Crowdsourcing is cheap and fast, but suffers from the problem of low-quality data. To address this fundamental challenge in crowdsourcing, we propose a simple payment mechanism to incentivize workers to answer only the questions that they are sure of and skip the rest. We show that surprisingly, under a mild and natural "no-free-lunch" requirement, this mechanism is the one and only incentive-compatible payment mechanism possible. We also show that among all possible incentive-compatible mechanisms (that may or may not satisfy no-free-lunch), our mechanism makes the smallest possible payment to spammers. We further extend our results to a more general setting in which workers are required to provide a quantized confidence for each question. Interestingly, this unique mechanism takes a "multiplicative" form. The simplicity of the mechanism is an added benefit. In preliminary experiments involving over 900 worker-task pairs, we observe a significant drop in the error rates under this unique mechanism for the same or lower monetary expenditure.

Efficient and Effective Budget-Feasible Mechanisms for Submodular Valuations

2025-05-01

Kai Han , Haotian Zhang , Shuang Cui

Truthful Multi-unit Procurements with Budgets

2014-01-01

Hau Chan , Jing Chen

View PDF Chat

Budget Feasible Mechanisms on Matroids

2017-01-01

Stefano Leonardi , Gianpiero Monaco , Piotr Sankowski +1 more

View PDF Chat

Simple and Efficient Budget Feasible Mechanisms for Monotone Submodular Valuations

2021-01-29

Pooya Jalaly , Éva Tardos

We study the problem of a budget limited buyer who wants to buy a set of items, each from a different seller, to maximize her value. The budget feasible mechanism … We study the problem of a budget limited buyer who wants to buy a set of items, each from a different seller, to maximize her value. The budget feasible mechanism design problem requires the design a mechanism that incentivizes the sellers to truthfully report their cost and maximizes the buyer’s value while guaranteeing that the total payment does not exceed her budget. Such budget feasible mechanisms can model a buyer in a crowdsourcing market interested in recruiting a set of workers (sellers) to accomplish a task for her. This budget feasible mechanism design problem was introduced by Singer in 2010. We consider the general case where the buyer’s valuation is a monotone submodular function. There are a number of truthful mechanisms known for this problem. We offer two general frameworks for simple mechanisms, and by combining these frameworks, we significantly improve on the best known results, while also simplifying the analysis. For example, we improve the approximation guarantee for the general monotone submodular case from 7.91 to 5 and for the case of large markets (where each individual item has negligible value) from 3 to 2.58. More generally, given an r approximation algorithm for the optimization problem (ignoring incentives), our mechanism is a r + 1 approximation mechanism for large markets, an improvement from 2 r 2 . We also provide a mechanism without the large market assumption, where we achieve a 4 r + 1 approximation guarantee. We also show how our results can be used for the problem of a principal hiring in a Crowdsourcing Market to select a set of tasks subject to a total budget.

View PDF Chat

Online Stochastic Packing Applied to Display Ad Allocation

2010-01-01

Jon Feldman , Monika Henzinger , Nitish Korula +2 more

View PDF Chat

Budget Feasible Mechanisms

2010-10-01

Yaron Singer

We study a novel class of mechanism design problems in which the outcomes are constrained by the payments. This basic class of mechanism design problems captures many common economic situations, … We study a novel class of mechanism design problems in which the outcomes are constrained by the payments. This basic class of mechanism design problems captures many common economic situations, and yet it has not been studied, to our knowledge, in the past. We focus on the case of procurement auctions in which sellers have private costs, and the auctioneer aims to maximize a utility function on subsets of items, under the constraint that the sum of the payments provided by the mechanism does not exceed a given budget. Standard mechanism design ideas such as the VCG mechanism and its variants are not applicable here. We show that, for general functions, the budget constraint can render mechanisms arbitrarily bad in terms of the utility of the buyer. However, our main result shows that for the important class of sub modular functions, a bounded approximation ratio is achievable. Better approximation results are obtained for subclasses of the sub modular functions. We explore the space of budget feasible mechanisms in other domains and give a characterization under more restricted conditions.

View PDF Chat

Budget feasible mechanism design: from prior-free to bayesian

2012-05-19

Xiaohui Bei , Ning Chen , Nick Gravin +1 more

Budget feasible mechanism design studies procurement combinatorial auctions in the sellers have private costs to produce items, and the buyer (auctioneer) aims to maximize a social valuation function on subsets … Budget feasible mechanism design studies procurement combinatorial auctions in the sellers have private costs to produce items, and the buyer (auctioneer) aims to maximize a social valuation function on subsets of items, under the budget constraint on the total payment. One of the most important questions in the field is which valuation domains admit truthful budget feasible mechanisms with 'small' approximations (compared to the social optimum)? Singer [35] showed that additive and submodular functions have a constant approximation mechanism. Recently, Dobzinski, Papadimitriou, and Singer [20] gave an O(log2n) approximation mechanism for subadditive functions; further, they remarked that: A fundamental question is whether, regardless of computational constraints, a constant-factor budget feasible mechanism exists for subadditive In this paper, we address this question from two viewpoints: prior-free worst case analysis and Bayesian analysis, are two standard approaches from computer science and economics, respectively. - For the prior-free framework, we use a linear program (LP) that describes the fractional cover of the valuation function; the LP is also connected to the concept of approximate core in cooperative game theory. We provide a mechanism for subadditive functions whose approximation is O(I), via the worst case integrality gap I of this LP. This implies an O(log n)-approximation for subadditive valuations, O(1)-approximation for XOS valuations, as well as for valuations having a constant integrality gap. XOS valuations are an important class of functions and lie between the submodular and the subadditive classes of valuations. We further give another polynomial time O(log n/(log log n)) sub-logarithmic approximation mechanism for subadditive functions. Both of our mechanisms improve the best known approximation ratio O(log2 n). - For the Bayesian framework, we provide a constant approximation mechanism for all subadditive functions, using the above prior-free mechanism for XOS valuations as a subroutine. Our mechanism allows correlations in the distribution of private information and is universally truthful.

View PDF Chat

On the Approximability of Budget Feasible Mechanisms

2011-01-23

Ning Chen , Nick Gravin , Pinyan Lu

Previous chapter Next chapter Full AccessProceedings Proceedings of the 2011 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)On the Approximability of Budget Feasible MechanismsNing Chen, Nick Gravin, and Pinyan LuNing Chen, … Previous chapter Next chapter Full AccessProceedings Proceedings of the 2011 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)On the Approximability of Budget Feasible MechanismsNing Chen, Nick Gravin, and Pinyan LuNing Chen, Nick Gravin, and Pinyan Lupp.685 - 699Chapter DOI:https://doi.org/10.1137/1.9781611973082.54PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract Budget feasible mechanisms, recently initiated by Singer (FOCS 2010), extend algorithmic mechanism design problems to a realistic setting with a budget constraint. We consider the problem of designing truthful budget feasible mechanisms for monotone submodular functions: We give a randomized mechanism with an approximation ratio of 7.91 (improving on the previous best-known result 233.83), and a deterministic mechanism with an approximation ratio of 8.34. We also study the knapsack problem, which is a special submodular function, give a 2 + √2 approximation deterministic mechanism (improving on the previous best-known result 5), and a 3 approximation randomized mechanism. We provide similar results for an extended knapsack problem with heterogeneous items, where items are divided into groups and one can pick at most one item from each group. Finally we show a lower bound of 1 + √2 for the approximation ratio of deterministic mechanisms and 2 for randomized mechanisms for knapsack, as well as the general monotone submodular functions. Our lower bounds are unconditional, and do not rely on any computational or complexity assumptions. Previous chapter Next chapter RelatedDetails Published:2011ISBN:978-0-89871-993-2eISBN:978-1-61197-308-2 https://doi.org/10.1137/1.9781611973082Book Series Name:ProceedingsBook Code:PR138Book Pages:xviii-1788

View PDF Chat

Incentives for Privacy Tradeoff in Community Sensing

2013-11-03

Adish Singla , Andreas Krause

Community sensing, fusing information from populations of privately-held sensors, presents a great opportunity to create efficient and cost-effective sensing applications. Yet, reasonable privacy concerns often limit the access to such … Community sensing, fusing information from populations of privately-held sensors, presents a great opportunity to create efficient and cost-effective sensing applications. Yet, reasonable privacy concerns often limit the access to such data streams. How should systems valuate and negotiate access to private information, for example in return for monetary incentives? How should they optimally choose the participants from a large population of strategic users with privacy concerns, and compensate them for information shared? In this paper, we address these questions and present a novel mechanism, SeqTGreedy, for budgeted recruitment of participants in community sensing. We first show that privacy tradeoffs in community sensing can be cast as an adaptive submodular optimization problem. We then design a budget feasible, incentive compatible (truthful) mechanism for adaptive submodular maximization, which achieves near-optimal utility for a large class of sensing applications. This mechanism is general, and of independent interest. We demonstrate the effectiveness of our approach in a case study of air quality monitoring, using data collected from the Mechanical Turk platform. Compared to the state of the art, our approach achieves up to 30% reduction in cost in order to achieve a desired level of utility.

View PDF Chat

Budget Feasible Mechanisms for Experimental Design

2014-01-01

Thibaut Horel , Stratis Ioannidis , S. Muthukrishnan

View PDF Chat

Budget feasible mechanism design

2012-05-19

Xiaohui Bei , Ning Chen , Nick Gravin +1 more

Budget feasible mechanism design studies procurement combinatorial auctions where the sellers have private costs to produce items, and the buyer(auctioneer) aims to maximize a social valuation function on subsets of … Budget feasible mechanism design studies procurement combinatorial auctions where the sellers have private costs to produce items, and the buyer(auctioneer) aims to maximize a social valuation function on subsets of items, under the budget constraint on the total payment. One of the most important questions in the field is "which valuation domains admit truthful budget feasible mechanisms with `small' approximations (compared to the social optimum)?" Singer showed that additive and submodular functions have such constant approximations. Recently, Dobzinski, Papadimitriou, and Singer gave an O(log^2 n)-approximation mechanism for subadditive functions; they also remarked that: "A fundamental question is whether, regardless of computational constraints, a constant-factor budget feasible mechanism exists for subadditive functions." We address this question from two viewpoints: prior-free worst case analysis and Bayesian analysis. For the prior-free framework, we use an LP that describes the fractional cover of the valuation function; it is also connected to the concept of approximate core in cooperative game theory. We provide an O(I)-approximation mechanism for subadditive functions, via the worst case integrality gap I of LP. This implies an O(log n)-approximation for subadditive valuations, O(1)-approximation for XOS valuations, and for valuations with a constant I. XOS valuations are an important class of functions that lie between submodular and subadditive classes. We give another polynomial time O(log n/loglog n) sub-logarithmic approximation mechanism for subadditive valuations. For the Bayesian framework, we provide a constant approximation mechanism for all subadditive functions, using the above prior-free mechanism for XOS valuations as a subroutine. Our mechanism allows correlations in the distribution of private information and is universally truthful.

View PDF Chat