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
Mon Nov 10 22:49:02 PST 2014

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.



Title: Welfare Maximization with Production Costs: A Primal Dual Approach

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