Seminars & Colloquia Calendar

Download as iCal file

DIMACS Theory of Computing Seminar

Simultaneous Communication Complexity of Two-Player Combinatorial Auctions

Matt Weinberg: Princeton University

Location:  CoRE 301
Date & time: Wednesday, 25 January 2017 at 11:00AM - 11:11AM

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.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.