Budget-feasible Mechanism Design with Predictions

Keywords: Mechanism Design, Algorithmic Game Theory, Algorithms with Predictions, Combinatorial Optimization

Share this page

Description

We consider the problem of designing budget-feasible mechanisms for procurement auctions. In this model, an auctioneer is interested in buying services (or goods) from a set of agents N. Each agent i ∈N specifies a cost c_i to be paid by the buyer for using their service; these costs are assumed to be private information. The auctioneer has a budget B and a valuation function v( ・), where v(S) specifies the value derived from the services of the agents in S ⊆ N.

Given the (reported) costs of the agents, the goal of the auctioneer is to choose a budget- feasible subset S ⊆ N of the agents, such that the valuation v(S) is maximized. Budget- feasibility here means that Σ_i∈S p_i ≤ B, where p_i is the payment issued from the mechanism to agent i.

The agents might try to extract larger payments from the mechanism by misreporting their actual costs, which is undesirable from the auctioneer’s perspective. The goal is to design budget-feasible mechanisms that (i) elicit truthful reporting of the costs by all agents (i.e., strategyproofness) and (ii) achieve a good approximation with respect to the optimal value for the auctioneer (i.e., approximate efficiency). The problem of designing budget-feasible mechanisms was introduced by Singer [2] and has received a lot of attention, both because of its theoretical appeal and of its relevance to several emerging application domains.

In this project, we focus on the most basic setting of the problem, where the valuation function v(・) is additive. The problem then relates to the classic knapsack problem and is generally well understood [1]. However, we add a twist to this setting by assuming that the auctioneer can use some predictions of the actual valuations of the agents. Such predictions could be extracted, for example, from the bidding behavior of the agents observed in the past. The question we would like to address in this new model is to which extent these predictions can help to derive improved mechanisms.

Prerequisites

Good knowledge of mechanism design (single-parameter setting, Myerson’s lemma) and approximation algorithms (knapsack problem); students having followed the Algorithmic Game Theory course should be well equipped.

Interested?

Please get in touch with Guido Schäfer

Note

The above is just one specific proposal of a potential research project related to algorithmic game theory. If you have interesting project proposals yourself or want to discuss other possibilities, please feel free to get in touch.

References

[1] Nick Gravin, Yaonan Jin, Pinyan Lu, and Chenhao Zhang. Optimal budget-feasible mechanisms for additive valuations. In ACM Conference on Economics and Computation (EC), pages 887–900. Association for Computing Machinery, 2020.