On Revenue Maximization in Second-Price Ad Auctions (2009)
Azar, Yossi, Birnbaum, Benjamin, Karlin, Anna R., Nguyen, C. Thach
Most recent papers addressing the algorithmic problem of allocating advertisement space for keywords in sponsored search auctions assume that pricing is done via a first-price auction, which does not...
Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks (2009)
Azar, Yossi, Birnbaum, Benjamin, Celis, L. Elisa, Devanur, Nikhil R., Peres, Yuval
Bargaining games on exchange networks have been studied by both economists and sociologists. A Balanced Outcome for such a game is an equilibrium concept that combines notions of stability and...
On-line Bipartite Matching Made Simple (2008)
Benjamin Birnbaum, Claire Mathieu
We examine the classic on-line bipartite matching problem studied by Karp, Vazirani, and Vazirani [8] and provide a simple proof of their result that the Ranking algorithm for this problem achieves a...
Thinking Twice about Second-Price Ad Auctions (2008)
Azar, Yossi, Birnbaum, Benjamin, Karlin, Anna R., Nguyen, C. Thach
Recent work has addressed the algorithmic problem of allocating advertisement space for keywords in sponsored search auctions so as to maximize revenue, most of which assume that pricing is done via...
Improved Approximation Algorithms for Budgeted Allocations (2008)
Yossi Azar, Benjamin Birnbaum, Anna R. Karlin, Claire Mathieu, C. Thach Nguyen
Abstract. We provide a 3/2-approximation algorithm for an offline budgeted allocations problem, an improvement over the e/(e − 1) approximation of Andelman and Mansour [1] and the e/(e − 1) −...
An improved analysis for a greedy remote-clique algorithm using factorrevealing LPs (2006)
Benjamin Birnbaum, Kenneth J. Goldman
Given a positive integer k and a complete graph with non-negative edge weights satisfying the triangle inequality, the remote-clique problem is to find a subset of k vertices having a maximum-weight...