Timezone: »

 
Poster
Online Mechanism Design for Information Acquisition
Federico Cacciamani · Matteo Castiglioni · Nicola Gatti

Wed Jul 26 05:00 PM -- 06:30 PM (PDT) @ Exhibit Hall 1 #440
in Poster Session 4 »
We study the problem of designing mechanisms for information acquisition scenarios. This setting models strategic interactions between a uniformed receiver and a set of informed senders. In our model the senders receive information about the underlying state of nature and communicate their observation (either truthfully or not) to the receiver, which, based on this information, selects an action. Our goal is to design mechanisms maximizing the receiver's utility while incentivizing the senders to report truthfully their information. First, we provide an algorithm that efficiently computes an optimal incentive compatible (IC) mechanism. Then, we focus on the online problem in which the receiver sequentially interacts in an unknown game, with the objective of minimizing the cumulative regret w.r.t. the optimal IC mechanism, and the cumulative violation of the incentive compatibility constraints. We investigate two different online scenarios, i.e., the full and bandit feedback settings. For the full feedback problem, we propose an algorithm that guarantees $\tilde{O}(\sqrt{T})$ regret and violation, while for the bandit feedback setting we present an algorithm that attains $\tilde{O}(T^{\alpha})$ regret and $\tilde{O}(T^{1-\alpha/2})$ violation for any $\alpha \in [1/2, 1]$. Finally, we complement our results providing a tight lower bound.
[ PDF] 

Author Information

Federico Cacciamani (Politecnico di Milano)
Matteo Castiglioni (Politecnico di Milano)
Nicola Gatti (Politecnico di Milano)

More from the Same Authors