Group:Grad-student Theory Lunch
Title: Mechanism Design without Money
Speaker: Chengu Wang,Chenye Wu Tsinghua university
Time: 2010-06-10 12:00-2010-06-10 13:30
Venue: FIT 1-222

Abstract:

Chengu Wang

Abstract:

I am going to talk about the two following communication complexity problem. ONE-CYCLE problem: Alice and Bob hold permutations \sigma and \pi respectively. Their goal is to determine whether \pi^{-1} \circ \sigma is a Hamiltonian cycle.

IN-SAME-CYCLE problem: Alice and Bob hold permutations \sigma and \pi respectively. Their goal is to determine whether v_1 and v_2 are in the same cycle.

O(n\log n) is a trivial deterministic upper bound for both problems. In FOCS '93, Raz and Spieker proved that N(ONE-CYCLE)=\Omega(n\log\log n). In SODA '08, Harvey proved that D(IN-SAME-CYCLE)=\Omega(n),N^0(IN-SAME-CYCLE)=\Omega(n), N^1(IN-SAME-CYCLE)=\Omega(n), and an \Omega(n\log n) randomized lower bound on the one round communication complexity.

We are going to give a randomized \Omega(n) lower bound for this two problems, by using a reduction from the SET-DISJOINTNESS problem.

Chenye Wu

Abstract:

Despite impossibility results on general domains, there are some classes of situations in which there exist interesting dominant strategy mechanisms. While some of these situations (and the resulting mechanisms) involve the transfer of money, we examine some that do not. Specifically, we analyze problems where agents have single peaked preferences over a one dimensional public policy space; and problems where agents must match with each other.



Short Bio: