Social Algorithms and Internet Economics

Classical algorithm design assumes that all the parameters of the objective function is known. When that information is held privately by multiple agents, we arrive in the domain of mechanism design, where the parameters of a social objective function is dispersed among the strategic agents who reveal this information when an algorithm can be designed to incentivize them to do so. In the first part of the talk, I will motivate the design of algorithm under incomplete information. In the latter part, I will discuss our recent result in the domain of quasi-linear preferences with selfish valuations, a domain that is relevant for resource sharing applications like mobile bandwidth or cloud computing. We show that even though the valuations are less rich than that in the requirements of Roberts (1979), we are able to get the affine maximizer result with an additional assumption on the social choice function and the allocation space.

The later part of the talk is based on my recent work: https://dl.dropboxusercontent.com/u/26115762/site/publications.html#nath-sen14roberts