• Calendar

April 12, Tuesday
12:00 – 14:00

We study a representative task allocation problem called shortest paths: Let $G$ be a graph in which the edges are owned by self interested agents. The cost of each edge is privately known to its owner. Let $s$ and $t$ be two distinguished nodes in $G$. Given a distribution on the edge costs, the goal is to design a mechanism (protocol) which acquires a cheap $s-t$ path.

We first observe that the class of generalized VCG mechanisms has desired monotonicity properties. We exploit this observation to obtain, under an independence assumption, expected payments which are significantly lower than the worst case bounds of [AT02,ess03]. We then investigate whether these payments can be improved when there is competition among paths.

Surprisingly, we give evidence to the fact that typically such competition hardly helps incentive compatible mechanisms. In particular, we show this for the celebrated VCG mechanism. We then construct a novel general protocol combining the advantages of incentive compatible and non-incentive compatible mechanisms.

Under reasonable assumptions on the agents we show that the overpayment of our mechanism is very small. Finally, we show that many other task allocation problems can be reduced to shortest paths.

Joint work with Artur Czumaj

Bio:

Amir Ronen is a senior lecturer (assistant professor) in the Industrial Engineering and Management Faculty at the Technion. He received his Ph.D. from the Hebrew University of Jerusalem in the year 2000. His main areas of interest are the interplay between game theory and computer science, theoretical computer science, game theory, electronic commerce and the Internet.