Title: Simultaneous Communication Complexity of Two-Player Combinatorial Auctions
Speaker: Matt Weinberg, Princeton University
Date: Wednesday, January 25, 2017 11:00am-12:00pm
Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We consider simultaneous protocols for the following communication problem: Alice and Bob each have some list of subsets of [m], A_1,...,A_a, and B_1,...,B_b, and wish to either:
(Allocation Problem): partition [m] into A \sqcup B in order to maximize \max_i {A \cap A_i} + \max_j {B \cap B_j}. (Decision Problem): decide whether there exists an i, j, such that A_i \cup B_ j \geq C.
For interactive protocols, a (tight) 3/4-approximation is known in poly(m) communication for both problems. We show the following: - A randomized, simultaneous protocol with O(m) communication that achieves a (tight) 3/4-approximation for the allocation problem. - No randomized, simultaneous protocol with subexponential (in m) communication guarantees better than a 3/4-1/108 approximation for the decision problem.
I'll further discuss the implications of these results for truthful combinatorial auctions due to a recent result of Dobzinski [FOCS 16].
Joint work with Mark Braverman and Jieming Mao.
See: http://www.math.rutgers.edu/~sk1233/theory-seminar/S17/