Computational Aspects of Bayesian Persuasion under Approximate Best Response
Authors: Kunhe Yang, Hanrui Zhang
NeurIPS 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We focus on the computational aspects of the problem, aiming to design algorithms that efficiently compute (almost) optimal strategies for the sender. Despite the absence of the revelation principle which has been one of the most powerful tools in Bayesian persuasion we design polynomial-time exact algorithms for the problem when either the state space or the action space is small, as well as a quasi-polynomial-time approximation scheme (QPTAS) for the general problem. On the negative side, we show there is no polynomial-time exact algorithm for the general problem unless P = NP. Our results build on several new algorithmic ideas, which might be useful in other principal-agent problems where robustness is desired. |
| Researcher Affiliation | Academia | Kunhe Yang University of California, Berkeley kunheyang@berkeley.edu Hanrui Zhang Chinese University of Hong Kong hanrui@cse.cuhk.edu.hk |
| Pseudocode | Yes | Algorithm 1: EXPLORE ... Algorithm 2: ALGORITHM FOR SMALL STATE SPACES |
| Open Source Code | No | The paper is theoretical and does not mention providing open-source code for the described methodology. |
| Open Datasets | No | This is a theoretical paper and does not involve experimental data or datasets. |
| Dataset Splits | No | This is a theoretical paper and does not involve experimental data or dataset splits for validation. |
| Hardware Specification | No | This is a theoretical paper and does not describe any experimental hardware used. |
| Software Dependencies | No | This is a theoretical paper and does not describe any specific software dependencies with version numbers for experiments. |
| Experiment Setup | No | This is a theoretical paper and does not describe an experimental setup with hyperparameters or training settings. |