Nash Incentive-compatible Online Mechanism Learning via Weakly Differentially Private Online Learning
Authors: Joon Suk Huh, Kirthevasan Kandasamy
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 nontruthful behavior. Our method is IC and achieves O(T 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. |
| Researcher Affiliation | Academia | Joon Suk Huh 1 Kirthevasan Kandasamy 1 1Department of Computer Science, University of Wisconsin Madison, Madison, WI, USA. Correspondence to: Joon Suk Huh <joon@cs.wisc.edu>. |
| Pseudocode | Yes | Protocol 1. Online Mechanism Learning For each round t = 1, . . . , T: 1. M chooses a single-round mechanism πt based on past reported types b<t and observed objective functions G<t. 2. Each participating agent observes πt and reports their types bi,t Θi. 3. M executes πt with input bt and realizes an outcome st πt(bt). 4. Each participating agent experiences utility ui(θi,t, st). 5. M observes Gt and experiences Gt θt, st . |
| Open Source Code | No | The paper does not provide any statement or link indicating that open-source code for the described methodology is available. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments on datasets, thus it does not refer to public or open datasets for training. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments with data, thus it does not provide details on dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments that would require hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not describe any specific software dependencies with version numbers for experimental reproducibility. |
| Experiment Setup | No | The paper is theoretical and does not conduct empirical experiments, thus it does not provide specific experimental setup details such as hyperparameters or training settings. |