Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGeneralized Assignment Problem: Truthful Mechanism Design without Money
87
0
0.0
(
0
)
Added by
Salman Fadaei
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
We study the problem of fairly dividing a heterogeneous resource, commonly known as cake cutting and chore division, in the presence of strategic agents. While a number of results in this setting have been established in previous works, they rely crucially on the free disposal assumption, meaning that the mechanism is allowed to throw away part of the resource at no cost. In the present work, we remove this assumption and focus on mechanisms that always allocate the entire resource. We exhibit a truthful and envy-free mechanism for cake cutting and chore division for two agents with piecewise uniform valuations, and we complement our result by showing that such a mechanism does not exist when certain additional constraints are imposed on the mechanisms. Moreover, we provide bounds on the efficiency of mechanisms satisfying various properties, and give truthful mechanisms for multiple agents with restricted classes of valuations.
We propose a mechanism to allocate slots fairly at congested airports. This mechanism: (a) ensures that the slots are allocated according to the true valuations of airlines, (b) provides fair opportunities to the flights connecting remote cities to large airports, and (c) controls the number of flights in each slot to minimize congestion. The mechanism draws inspiration from economic theory. It allocates the slots based on an affine maximizer allocation rule and charges payments to the airlines such that they are incentivized to reveal their true valuations. The allocation also optimizes the occupancy of every slot to keep them as uncongested as possible. The formulation solves an optimal integral solution in strongly polynomial time. We conduct experiments on the data collected from two major airports in India. We also compare our results with existing allocations and also with the allocations based on the International Air Transport Association (IATA) guidelines. The computational results show that the social utility generated using our mechanism is 20-30% higher than IATA and current allocations.
Demand response (DR) is not only a crucial solution to the demand side management but also a vital means of electricity market in maintaining power grid reliability, sustainability and stability. DR can enable consumers (e.g. data centers) to reduce their electricity consumption when the supply of electricity is a shortage. The consumers will be rewarded in the case of DR if they reduce or shift some of their energy usage during peak hours. Aiming at solving the efficiency of DR, in this paper, we present MEDR, a mechanism on emergency DR in colocation data center. First, we formalize the MEDR problem and propose a dynamic programming to solve the optimization version of the problem. We then design a deterministic mechanism as a solution to solve the MEDR problem. We show that our proposed mechanism is truthful. Next, we prove that our mechanism is an FPTAS, i.e., it can be approximated within $1 + epsilon$ for any given $epsilon > 0$, while the running time of our mechanism is polynomial in $n$ and $1/epsilon$, where $n$ is the number of tenants in the datacenter. Furthermore, we also give an auction system covering the efficient FPTAS algorithm as bidding decision program for DR in colocation datacenter. Finally, we choose a practical smart grid dataset to build a large number of datasets for simulation in performance evaluation. By evaluating metrics of the approximation ratio of our mechanism, the non-negative utility of tenants and social cost of colocation datacenter, the results demonstrate the effectiveness of our work.
In a crowdsourcing market, a requester is looking to form a team of workers to perform a complex task that requires a variety of skills. Candidate workers advertise their certified skills and bid prices for their participation. We design four incentive mechanisms for selecting workers to form a valid team (that can complete the task) and determining each individual workers payment. We examine profitability, individual rationality, computational efficiency, and truthfulness for each of the four mechanisms. Our analysis shows that TruTeam, one of the four mechanisms, is superior to the others, particularly due to its computational efficiency and truthfulness. Our extensive simulations confirm the analysis and demonstrate that TruTeam is an efficient and truthful pricing mechanism for team formation in crowdsourcing markets.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
