Logo image
Back
Deterministic Budget-Feasible Clock Auctions
Preprint   Open access

Deterministic Budget-Feasible Clock Auctions

Eric Balkanski, Pranav Garimidi, Vasilis Gkatzelis, Daniel Schoepflin and Xizhi Tan
19 Jul 2021
DOI: https://doi.org/10.48550/arxiv.2107.09239
Featured in Collection :   UN Sustainable Development Goals @ Drexel
url
https://arxiv.org/abs/2107.09239View
SubmittedarXiv.org - Non-exclusive license to distribute,  Open

Abstract

Computer Science - Computer Science and Game Theory
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.

Metrics

24 Record Views
1 citations in Web of Science

Details

UN Sustainable Development Goals (SDGs)

This publication has contributed to the advancement of the following goals:

#10 Reduced Inequalities

InCites Highlights

Data related to this publication, from InCites Benchmarking & Analytics tool:

Collaboration types
Domestic collaboration
Web of Science research areas
Management
Operations Research & Management Science
Logo image