ARC Distinguished Lecture: Avrim Blum, Carnegie Mellon University

Event Details
  • Date/Time:
    • Monday April 8, 2013 - Tuesday April 9, 2013
      3:00 pm - 2:59 pm
  • Location: Klaus 1116
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:
No contact information submitted.

Summary Sentence: No summary sentence submitted.

Full Summary: No summary paragraph submitted.

Title: Algorithmic Pricing


Pricing and allocating goods to buyers with complex preferences in order to maximize some desired objective (e.g., social welfare or profit) is a central problem in Algorithmic Mechanism Design.

 In this talk I will discuss some particularly simple algorithms that are able to achieve surprisingly strong guarantees for a range of problems of this type.  As one example, for the problem of pricing <i>resources</i>, modeled as goods having an increasing marginal extraction cost to the seller, a simple approach of pricing the <i>i</i>th unit of each good at a value equal to the anticipated extraction cost of the <i>2i</i>th unit gives a constant-factor approximation to social welfare for a wide range of cost curves and for arbitrary buyer valuation functions.  I will also discuss simple algorithms with good approximation guarantees for revenue, as well as settings having an opposite character to resources, namely having economies of scale or decreasing marginal costs to the seller.


Additional Information

In Campus Calendar

College of Computing, School of Computer Science, ARC

Invited Audience
No audiences were selected.
No categories were selected.
No keywords were submitted.
  • Created By: Elizabeth Ndongi
  • Workflow Status: Published
  • Created On: Feb 12, 2013 - 10:00am
  • Last Updated: Oct 7, 2016 - 10:02pm