We study revenue maximization in multi-dimensional auctions with n bidders and m items. When the bidders are constant-demand and either the number of bidders or the number of items is a constant, we give a quasi-polynomial time algorithm that computes an ε-Bayesian Incentive Compatible (ε-BIC) mechanism that obtains at least a (1 - ε) faction of the expected revenue of the optimal Bayesian Incentive Compatible (BIC) mechanism. We obtain this guarantee even when the value distribution of each bidder is unbounded, extending the main result of [Kothari et al., 2019] from a single bidder to multiple bidders.

The competition complexity of an auction setting is the number of additional bidders needed such that the simple mechanism of selling items separately (with additional bidders) achieves greater revenue than the optimal but complex (randomized, prior-dependent, Bayesian-truthful) optimal mechanism without the additional bidders. Our main result settles the competition complexity of n bidders with additive values over m < n independent items at [EQUATION]. The [EQUATION] upper bound is due to [Beyhaghi and Weinberg, 2019], and our main result improves the prior lower bound of Ω (ln n) to [EQUATION].

We study the model of metric voting initially proposed by Feldman et al. [2020]. In this model, experts and candidates are located in a metric space, and each candidate possesses a quality that is independent of her location. An expert evaluates each candidate as the candidate's quality less the distance between the candidate and the expert in the metric space. The expert votes for her favorite candidate. Naturally, the expert prefers candidates that are "similar" to herself, i.e., close to her location in the metric space, thus creating bias in the vote. The goal is to select a voting rule and a committee of experts to mitigate the bias. More specifically, given m candidates, what is the minimum number of experts needed to ensure that the voting rule selects a candidate whose quality is at most ε worse than the best one?

Tao Yu, Rui Zhang, Heyang Er, Suyi Li, Eric Xue, Bo Pang, Xi Victoria Lin, Yi Chern Tan, Tianze Shi, Zihan Li, Youxuan Jiang, Michihiro Yasunaga, Sungrok Shim, Tao Chen, Alexander Fabbri, Zifan Li, Luyao Chen, Yuwen Zhang, Shreya Dixit, Vincent Zhang, Caiming Xiong, Richard Socher, Walter Lasecki, Dragomir Radev. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). 2019.

Rui Zhang, Tao Yu, Heyang Er, Sungrok Shim, Eric Xue, Xi Victoria Lin, Tianze Shi, Caiming Xiong, Richard Socher, Dragomir Radev. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). 2019.