LAB42 Talk | CSC: Artem Tsikiridis - Partial Allocations in Budget-Feasible Mechanism Design

LAB42, L3.33

Join us in this Computational Social Choice Seminar from Artem Tsikiridis.

Partial Allocations in Budget-Feasible Mechanism Design: Bridging Multiple Levels of Service and Divisible Agents

Budget-feasible procurement has been a major paradigm in algorithmic mechanism design since its introduction. An auctioneer (buyer) with a strict budget constraint is interested in buying goods or services from a group of strategic agents (sellers). In many scenarios it makes sense to allow the auctioneer to only partially buy what an agent offers,e.g., an agent might have multiple copies of an item to sell, they might offer multiple levels of a service, or they may be available to perform a task for a fraction of a specified time interval. Nevertheless, the focus of the related literature has been on settings where each agent's services are either fully acquired or not at all. A reason for this is that in settings with partial allocations, without any assumptions on the costs, there are strong inapproximability results.

Under the mild assumption of being able to afford each agent entirely, we are able to circumvent such results. We design a polynomial-time, deterministic, truthful, budget-feasible, (2+\sqrt{3})-approximation mechanism for the setting where each agent offers multiple levels of service and the auctioneer has a discrete separable concave valuation function. We then use this result to design a deterministic, truthful and budget-feasible mechanism for the setting where any fraction of a service can be acquired and the auctioneer's valuation function is separable concave (i.e., the sum of concave functions). The approximation ratio of this mechanism depends on how "nice" the concave functions are, and is O(1)-approximate for valuation functions that are sums of O(1)-regular (Lipschitz) functions (e.g., functions like \log(1+x)). For the special case of a linear valuation function, we improve the best known approximation ratio from 1+\phi to 2. This establishes a separation result between this setting and its indivisible counterpart.

Computational Social Choice Seminar

This is the programme of the Computational Social Choice Seminar at the Institute for Logic, Language and Computation (ILLC) at the University of Amsterdam. The talks mostly address issues at the interface of computer science (including logic and and artificial intelligence) and mathematical economics (including social choice theory, game theory, and decision theory). Talks take one hour, including questions. All welcome!

For more information, please contact Ulle Endriss.