Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Theory Lunch 10/13: Anthony Kim on Welfare Maximization with Production Costs

Greg Bodwin greg.bodwin at
Thu Nov 13 11:32:50 PST 2014

Reminder: in ~1 hour!

On Mon, Nov 10, 2014 at 10:49 PM, Greg Bodwin <greg.bodwin at> wrote:

> Hi all,
> As usual, there will be a Theory Lunch this Thursday in the Gates 4b
> wing.  Food at 12:15, speaker at 12:30.  Hope to see you there.
> Greg
> ---------------
> Title: Welfare Maximization with Production Costs: A Primal Dual Approach
> Info:
> We study online combinatorial auctions with production costs using the
> online primal dual framework. In this model, buyers arrive online, and the
> seller can produce multiple copies of each item subject to a non-decreasing
> marginal cost per copy. The goal is to allocate items to maximize social
> welfare less total production cost. For arbitrary (strictly convex and
> differentiable) production cost functions, we characterize the optimal
> competitive ratio achievable by online mechanisms/algorithms. We show that
> online posted pricing mechanisms, which are incentive compatible, can
> achieve competitive ratios arbitrarily close to the optimal, and construct
> lower bound instances on which no online algorithms, not necessarily
> incentive compatible, can do better. Our positive results improve or match
> the results in several previous work.
> Joint work with Zhiyi Huang.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list