Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Truthful Mechanism for the Generalized Assignment Problem
215
0
0.0
(
0
)
Added by
Salman Fadaei
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We propose a truthful-in-expectation, $(1-1/e)$-approximation mechanism for a strategic variant of the generalized assignment problem (GAP). In GAP, a set of items has to be optimally assigned to a set of bins without exceeding the capacity of any singular bin. In the strategic variant of the problem we study, values for assigning items to bins are the private information of bidders and the mechanism should provide bidders with incentives to truthfully report their values. The approximation ratio of the mechanism is a significant improvement over the approximation ratio of the existing truthful mechanism for GAP. The proposed mechanism comprises a novel convex optimization program as the allocation rule as well as an appropriate payment rule. To implement the convex program in polynomial time, we propose a fractional local search algorithm which approximates the optimal solution within an arbitrarily small error leading to an approximately truthful-in-expectation mechanism. The presented algorithm improves upon the existing optimization algorithms for GAP in terms of simplicity and runtime while the approximation ratio closely matches the best approximation ratio given for GAP when all inputs are publicly known.
rate research
Read More
In this paper, we study a problem of truthful mechanism design for a strategic variant of the generalized assignment problem (GAP) in a both payment-free and prior-free environment. In GAP, a set of items has to be optimally assigned to a set of bins without exceeding the capacity of any singular bin. In the strategic variant of the problem we study, bins are held by strategic agents, and each agent may hide its compatibility with some items in order to obtain items of higher values. The compatibility between an agent and an item encodes the willingness of the agent to receive the item. Our goal is to maximize total value (sum of agents values, or social welfare) while certifying no agent can benefit from hiding its compatibility with items. The model has applications in auctions with budgeted bidders. For two variants of the problem, namely emph{multiple knapsack problem} in which each item has the same size and value over bins, and emph{density-invariant GAP} in which each item has the same value density over the bins, we propose truthful $4$-approximation algorithms. For the general problem, we propose an $O(ln{(U/L)})$-approximation mechanism where $U$ and $L$ are the upper and lower bounds for value densities of the compatible item-bin pairs.
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 study a central problem in Algorithmic Mechanism Design: constructing truthful mechanisms for welfare maximization in combinatorial auctions with submodular bidders. Dobzinski, Nisan, and Schapira provided the first mechanism that guarantees a non-trivial approximation ratio of $O(log^2 m)$ [STOC06], where $m$ is the number of items. This was subsequently improved to $O(log mlog log m)$ [Dobzinski, APPROX07] and then to $O(log m)$ [Krysta and Vocking, ICALP12]. In this paper we develop the first mechanism that breaks the logarithmic barrier. Specifically, the mechanism provides an approximation ratio of $O(sqrt {log m})$. Similarly to previous constructions, our mechanism uses polynomially many value and demand queries, and in fact provides the same approximation ratio for the larger class of XOS (a.k.a. fractionally subadditive) valuations. We also develop a computationally efficient implementation of the mechanism for combinatorial auctions with budget additive bidders. Although in general computing a demand query is NP-hard for budget additive valuations, we observe that the specific form of demand queries that our mechanism uses can be efficiently computed when bidders are budget additive.
We design novel mechanisms for welfare-maximization in two-sided markets. That is, there are buyers willing to purchase items and sellers holding items initially, both acting rationally and strategically in order to maximize utility. Our mechanisms are designed based on a powerful correspondence between two-sided markets and prophet inequalities. They satisfy individual rationality, dominant-strategy incentive compatibility, budget-balance constraints and give constant-factor approximations to the optimal social welfare. We improve previous results in several settings: Our main focus is on matroid double auctions, where the set of buyers who obtain an item needs to be independent in a matroid. We construct two mechanisms, the first being a $1/3$-approximation of the optimal social welfare satisfying strong budget-balance and requiring the agents to trade in a customized order, the second being a $1/2$-approximation, weakly budget-balanced and able to deal with online arrival determined by an adversary. In addition, we construct constant-factor approximations in two-sided markets when buyers need to fulfill a knapsack constraint. Also, in combinatorial double auctions, where buyers have valuation functions over item bundles instead of being interested in only one item, using similar techniques, we design a mechanism which is a $1/2$-approximation of the optimal social welfare, strongly budget-balanced and can deal with online arrival of agents in an adversarial order.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
