Nash Incentive-compatible Online Mechanism Learning via Weakly Differentially Private Online Learning

• URL: http://arxiv.org/abs/2407.04898v1
• Date: Sat, 6 Jul 2024 00:02:25 GMT
• Title: Nash Incentive-compatible Online Mechanism Learning via Weakly Differentially Private Online Learning
• Authors: Joon Suk Huh, Kirthevasan Kandasamy,
• Abstract summary: We study a multi-round mechanism design problem, where we interact with a set of agents over a sequence of rounds. We wish to design an incentive-compatible (IC) online learning scheme to maximize an application-specific objective.
• Score: 6.869373893556194
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study a multi-round mechanism design problem, where we interact with a set of agents over a sequence of rounds. We wish to design an incentive-compatible (IC) online learning scheme to maximize an application-specific objective within a given class of mechanisms, without prior knowledge of the agents' type distributions. Even if each mechanism in this class is IC in a single round, if an algorithm naively chooses from this class on each round, the entire learning process may not be IC against non-myopic buyers who appear over multiple rounds. On each round, our method randomly chooses between the recommendation of a weakly differentially private online learning algorithm (e.g., Hedge), and a commitment mechanism which penalizes non-truthful behavior. Our method is IC and achieves $O(T^{\frac{1+h}{2}})$ regret for the application-specific objective in an adversarial setting, where $h$ quantifies the long-sightedness of the agents. When compared to prior work, our approach is conceptually simpler,it applies to general mechanism design problems (beyond auctions), and its regret scales gracefully with the size of the mechanism class.

Related papers

• LoRA-Ensemble: Efficient Uncertainty Modelling for Self-attention Networks [52.46420522934253]
  We introduce LoRA-Ensemble, a parameter-efficient deep ensemble method for self-attention networks. By employing a single pre-trained self-attention network with weights shared across all members, we train member-specific low-rank matrices for the attention projections. Our method exhibits superior calibration compared to explicit ensembles and achieves similar or better accuracy across various prediction tasks and datasets.
  arXiv  Detail & Related papers  (2024-05-23T11:10:32Z)
• 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)
• Efficient Methods for Non-stationary Online Learning [67.3300478545554]
  We present efficient methods for optimizing dynamic regret and adaptive regret, which reduce the number of projections per round from $mathcalO(log T)$ to $1$. Our technique hinges on the reduction mechanism developed in parameter-free online learning and requires non-trivial twists on non-stationary online methods.
  arXiv  Detail & Related papers  (2023-09-16T07:30:12Z)
• 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)
• Learning Dynamic Mechanisms in Unknown Environments: A Reinforcement Learning Approach [130.9259586568977]
  We propose novel learning algorithms to recover the dynamic Vickrey-Clarke-Grove (VCG) mechanism over multiple rounds of interaction. A key contribution of our approach is incorporating reward-free online Reinforcement Learning (RL) to aid exploration over a rich policy space.
  arXiv  Detail & Related papers  (2022-02-25T16:17:23Z)
• Socially-Optimal Mechanism Design for Incentivized Online Learning [32.55657244414989]
  Multi-arm bandit (MAB) is a classic online learning framework that studies the sequential decision-making in an uncertain environment. It is a practically important scenario in many applications such as spectrum sharing, crowdsensing, and edge computing. This paper establishes the incentivized online learning (IOL) framework for this scenario.
  arXiv  Detail & Related papers  (2021-12-29T00:21:40Z)
• Faithful Edge Federated Learning: Scalability and Privacy [4.8534377897519105]
  Federated learning enables machine learning algorithms to be trained over a network of decentralized edge devices without requiring the exchange of local datasets. We analyze how the key feature of federated learning, unbalanced and non-i.i.d. data, affects agents' incentives to voluntarily participate. We design two faithful federated learning mechanisms which satisfy economic properties, scalability, and privacy.
  arXiv  Detail & Related papers  (2021-06-30T08:46:40Z)
• 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)

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.