### DIMACS Theory of Computing Seminar

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/