Asynchronous Auction for Distributed Nonlinear Resource Allocation Problem

Resource Allocation Problems (RAPs) are concerned with the optimal allocation of resources to tasks. Problems in fields such as search theory, statistics, finance, economics, logistics, sensor & wireless networks fit this formulation. In literature, several centralized/synchronous algorithms have been proposed including recently proposed auction algorithm, RAP Auction. Here we present asynchronous implementation of RAP Auction for distributed RAPs.

Pricing Algorithms For a Two-sided Internet Advertisement Market

The Google AdSense Program is a successful internet advertisement program where Google places contextual adverts on third-party websites and shares the resulting revenue with each publisher. Advertisers have budgets and bid on ad slots while publishers set reserve prices for the ad slots on their websites. Following previous modelling efforts, we model the program as a two-sided market with advertisers on one side and publishers on the other. We show a reduction from the Generalised Assignment Problem (GAP) to the problem of computing the revenue maximising allocation and pricing of publisher slots under a first-price auction. GAP is APX-hard but a (1-1/e) approximation is known. We compute truthful and revenue-maximizing prices and allocation of ad slots to advertisers under a second-price auction. The auctioneer's revenue is within (1-1/e) second-price optimal.