TY - GEN
T1 - Mechanism design with unstructured beliefs: Doctoral consortium
AU - Li, Bo
N1 - Publisher Copyright:
© 2019 International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.
PY - 2019
Y1 - 2019
N2 - Mechanism design is the task to design algorithms, toward desired objectives, that is robust to potential manipulation by strategic players. Traditionally, it is assumed that the mechanism designer and the players in the economy share some common knowledge. However, as pointed out by Wilson, such common knowledge is "rarely present in experiments and never in practice", and "only by repeated weakening of common knowledge assumptions will the theory approximate reality." In the work, we mainly focus on designing resilient mechanisms that work properly even in such a less foreseeable environment. Bayesian auction design is a very flourishing topic in the field of mechanism design, where an important simplifying assumption is both the seller and the players know the exact distributions of all players' valuations. In this work we first consider the query complexity of Bayesian mechanisms, where we only allow the seller to have limited oracle accesses to the players' value distributions via simple queries. Then we further weaken the assumption by considering an information structure where the knowledge about the distributions can be arbitrarily scattered among the players. In both of these two unstructured information settings, we design mechanisms that are constant approximations to the optimal Bayesian mechanisms with full information. Finally, we study an envy-free allocation problem that the unstructured beliefs need to be taken into consideration. In particular, we model an environment where each player is unaware of the bundles (or allocated items) of other players, but still knows he does not receive the worst bundle. We present both conceptual and algorithmic results for this new envy-free allocation domain.
AB - Mechanism design is the task to design algorithms, toward desired objectives, that is robust to potential manipulation by strategic players. Traditionally, it is assumed that the mechanism designer and the players in the economy share some common knowledge. However, as pointed out by Wilson, such common knowledge is "rarely present in experiments and never in practice", and "only by repeated weakening of common knowledge assumptions will the theory approximate reality." In the work, we mainly focus on designing resilient mechanisms that work properly even in such a less foreseeable environment. Bayesian auction design is a very flourishing topic in the field of mechanism design, where an important simplifying assumption is both the seller and the players know the exact distributions of all players' valuations. In this work we first consider the query complexity of Bayesian mechanisms, where we only allow the seller to have limited oracle accesses to the players' value distributions via simple queries. Then we further weaken the assumption by considering an information structure where the knowledge about the distributions can be arbitrarily scattered among the players. In both of these two unstructured information settings, we design mechanisms that are constant approximations to the optimal Bayesian mechanisms with full information. Finally, we study an envy-free allocation problem that the unstructured beliefs need to be taken into consideration. In particular, we model an environment where each player is unaware of the bundles (or allocated items) of other players, but still knows he does not receive the worst bundle. We present both conceptual and algorithmic results for this new envy-free allocation domain.
KW - Bayesian auction
KW - Fair allocation
KW - Information elicitation
KW - Maximin-aware allocation
KW - Query complexity
UR - http://www.scopus.com/inward/record.url?scp=85077056119&partnerID=8YFLogxK
M3 - Conference article published in proceeding or book
AN - SCOPUS:85077056119
T3 - Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
SP - 2429
EP - 2431
BT - 18th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2019
PB - International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
T2 - 18th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2019
Y2 - 13 May 2019 through 17 May 2019
ER -