VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback

• URL: http://arxiv.org/abs/2004.08924v4
• Date: Sun, 23 Jan 2022 20:46:54 GMT
• Title: VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback
• Authors: Kirthevasan Kandasamy and Joseph E. Gonzalez and Michael I. Jordan and Ion Stoica
• Abstract summary: We study a multi-round welfare-maximising mechanism design problem in instances where agents do not know their values. We first define three notions of regret for the welfare, the individual utilities of each agent and that of the mechanism. Our framework also provides flexibility to control the pricing scheme so as to trade-off between the agent and seller regrets.
• Score: 104.06766271716774
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study a multi-round welfare-maximising mechanism design problem in instances where agents do not know their values. On each round, a mechanism first assigns an allocation each to a set of agents and charges them a price; at the end of the round, the agents provide (stochastic) feedback to the mechanism for the allocation they received. This setting is motivated by applications in cloud markets and online advertising where an agent may know her value for an allocation only after experiencing it. Therefore, the mechanism needs to explore different allocations for each agent so that it can learn their values, while simultaneously attempting to find the socially optimal set of allocations. Our focus is on truthful and individually rational mechanisms which imitate the classical VCG mechanism in the long run. To that end, we first define three notions of regret for the welfare, the individual utilities of each agent and that of the mechanism. We show that these three terms are interdependent via an $\Omega(T^{\frac{2}{3}})$ lower bound for the maximum of these three terms after $T$ rounds of allocations, and describe an algorithm which essentially achieves this rate. Our framework also provides flexibility to control the pricing scheme so as to trade-off between the agent and seller regrets. Next, we define asymptotic variants for the truthfulness and individual rationality requirements and provide asymptotic rates to quantify the degree to which both properties are satisfied by the proposed algorithm.

Related papers

• Fair Allocation in Dynamic Mechanism Design [57.66441610380448]
  We consider a problem where an auctioneer sells an indivisible good to groups of buyers in every round, for a total of $T$ rounds. The auctioneer aims to maximize their discounted overall revenue while adhering to a fairness constraint that guarantees a minimum average allocation for each group.
  arXiv  Detail & Related papers  (2024-05-31T19:26:05Z)
• Refined Mechanism Design for Approximately Structured Priors via Active Regression [50.71772232237571]
  We consider the problem of a revenue-maximizing seller with a large number of items for sale to $n$ strategic bidders. It is well-known that optimal and even approximately-optimal mechanisms for this setting are notoriously difficult to characterize or compute.
  arXiv  Detail & Related papers  (2023-10-11T20:34:17Z)
• Benefits of Permutation-Equivariance in Auction Mechanisms [90.42990121652956]
  An auction mechanism that maximizes the auctioneer's revenue while minimizes bidders' ex-post regret is an important yet intricate problem in economics. Remarkable progress has been achieved through learning the optimal auction mechanism by neural networks.
  arXiv  Detail & Related papers  (2022-10-11T16:13:25Z)
• Online Allocation and Learning in the Presence of Strategic Agents [16.124755488878044]
  We study the problem of allocating $T$ sequentially arriving items among $n$ homogeneous agents under the constraint that each agent must receive a pre-specified fraction of all items. Our main contribution is an online learning based allocation mechanism that is approximately Bayesian incentive compatible.
  arXiv  Detail & Related papers  (2022-09-25T00:46:53Z)
• Pessimism meets VCG: Learning Dynamic Mechanism Design via Offline Reinforcement Learning [114.36124979578896]
  We design a dynamic mechanism using offline reinforcement learning algorithms. Our algorithm is based on the pessimism principle and only requires a mild assumption on the coverage of the offline data set.
  arXiv  Detail & Related papers  (2022-05-05T05:44:26Z)
• Online Learning of Competitive Equilibria in Exchange Economies [94.24357018178867]
  In economics, the sharing of scarce resources among multiple rational agents is a classical problem. We propose an online learning mechanism to learn agent preferences. We demonstrate the effectiveness of this mechanism through numerical simulations.
  arXiv  Detail & Related papers  (2021-06-11T21:32:17Z)
• Consequences of Misaligned AI [12.879600368339393]
  This paper argues that we should view the design of reward functions as an interactive and dynamic process. We show how modifying the setup to allow reward functions that reference the full state or allowing the principal to update the proxy objective over time can lead to higher utility solutions.
  arXiv  Detail & Related papers  (2021-02-07T19:34:04Z)
• Learning and Strongly Truthful Multi-Task Peer Prediction: A Variational Approach [8.932080210400535]
  We design a family of mechanisms with a scoring function that maps a pair of reports to a score. We show how to derive good bounds on the number of tasks required for different types of priors. This is the first peer-prediction mechanism on continuous signals designed for the multi-task setting.
  arXiv  Detail & Related papers  (2020-09-30T15:09:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.