Nash Incentive-compatible Online Mechanism Learning via Weakly Differentially Private Online Learning
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.
Code (0)
등록된 구현이 없습니다.
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Prior-Agnostic Incentive-Compatible Exploration
In bandit settings, optimizing long-term regret metrics requires exploration, which corresponds to sometimes taking myopically sub-optimal actions. When a long-lived principal merely recommends actions to be executed by …
No-Regret and Incentive-Compatible Online Learning
We study online learning settings in which experts act strategically to maximize their influence on the learning algorithm's predictions by potentially misreporting their beliefs about a sequence of binary events. Our go…
scoring ruleShill-Proof Auctions
In an auction, a seller may masquerade as one or more bidders in order to manipulate the clearing price. We characterize single-item auction formats that are shill-proof in the sense that a profit-maximizing seller has n…
FMore: An Incentive Scheme of Multi-dimensional Auction for Federated Learning in MEC
Promising federated learning coupled with Mobile Edge Computing (MEC) is considered as one of the most promising solutions to the AI-driven service provision. Plenty of studies focus on federated learning from the perfor…
Edge-computingFederated LearningIncentive Mechanism Design for Emergency Frequency Control in Multi-Infeed Hybrid AC-DC System
In multi-infeed hybrid AC-DC (MIDC) systems, the emergency frequency control (EFC) with LCC-HVDC systems participating is of vital importance for system frequency stability. Nevertheless, when regional power systems are …