TY - JOUR AU - Sui, Xin AU - Boutilier, Craig PY - 2011/08/04 Y2 - 2024/03/29 TI - Efficiency and Privacy Tradeoffs in Mechanism Design JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 25 IS - 1 SE - AAAI Technical Track: Multiagent Systems DO - 10.1609/aaai.v25i1.7865 UR - https://ojs.aaai.org/index.php/AAAI/article/view/7865 SP - 738-744 AB - <p> A key problem in mechanism design is the construction of protocols that reach socially efficient decisions with minimal information revelation. This can reduce agent communication, and further, potentially increase privacy in the sense that agents reveal no more private information than is needed to determine an optimal outcome. This is not always possible: previous work has explored the tradeoff between communication cost and efficiency, and more recently, communication and privacy. We explore a third dimension: the tradeoff between privacy and efficiency. By sacrificing efficiency, we can improve the privacy of a variety of existing mechanisms. We analyze these tradeoffs in both second-price auctions and facility location problems (introducing new incremental mechanisms for facility location along the way). Our results show that sacrifices in efficiency can provide gains in privacy (and communication), in both the average and worst case. </p> ER -