Videos

Efficiency in Adauctions and Stability in Switched Networks

Presenter
October 21, 2015
Keywords:
  • distributed control, adauctions, stability
MSC:
  • 90B18
Abstract
We consider distributed control in two distinct network applications: sponsored search and switched networks. First, we consider a large-scale sponsored search market. For this pay-per-click market, we discuss an efficient and highly decomposed mechanism that maximizes social welfare. Here on each search occurrence, the search-platform solves an assignment problem and, on a slower time scale, each advertiser submits a bid which matches its demand for click-through with supply. The setting, in which bids are distributed across for a large, continuous range of search types and varying competition, extends the scope of prior models which are typically limited to the auction of a single keyword amongst a static pool of advertisers. Second, we consider multi-hop switched networks, a model of interconnected Internet routers. Here the BackPressure and MaxWeight policies are most typically considered. We introduce a scheduling policy for FIFO networks, the Proportional Scheduler, which is based on the proportional fairness criterion. The distributed implementation and scaling of this policy is compared with the BackPressure policy, and its stability properties are further compared with those of MaxWeight. The first portion of the talk is based on joint work with F.P. Kelly and P. Key. The second portion of the talk is based on joint work with M. Bramson and B. D'Auria. Further, both works are influenced by theoretical advances made by a number of participants of the workshop. We take the time to emphasize the significance of these developments.