Campus Event Calendar
Event Entry
What and Who
How to price items: mechanisms, complexity, and algorithms
Khaled Elbassioni
Max-Planck-Institut für Informatik - D1
Senior Researcher Series
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, RG2
MPI Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 5 March 2008
16:00
45 Minutes
E1 4
024
Saarbrücken
Abstract
Item pricing is one of the fundamental problems in Economics, whose
computational aspects have received attention only quite recently in the
Computer Science community.
In a typical scenario, a company or a store has a set of items to sell to
a number of potential buyers, and knows (say through market research or
interaction) each customer's valuation for each subset (called bundle) of
items, which is the largest amount the customer is willing to pay for that
subset. If a customer buys a subset, his utility, which is the difference
between the valuation and the purchased price, must be non-negative. The
seller's task is to assign individual prices to the items, and allocate
bundles to (a subset of) customers, such that his total revenue, i.e. the
sum of prices of all sold items, is maximized. Clearly, a low price will
attract more customers while a high price will generate more revenue. As
an example (called the tollbooth problem), suppose that customers want to
buy bandwidth along subpaths of a network and are welling to pay up to
some amount for the bandwidth, how should one price the bandwidth along
the individual links in order to maximize the revenue?
The situation can be made more complicated by the fact that there maybe
a limited supply of each item, and by the requirement to have a pricing
mechanism offering some kind of fairness towards the different customers.
It turns out that even the simplest variants of this type of optimization
problems are NP-hard, and moreover it is hard to approximate the optimum
solution reasonably well. On the other hand, a logarithmic and
super-logarithmic approximations, respectively in the unlimited and
limited supply cases have been recently proposed. We will go briefly over
these and related results.
Then we will concentrate on the single-minded case, in which each customer
is interested only in buying a particular bundle. In this case, the
problem can be cast as some type of maximum feasible subsystem problem,
that is, of finding among a given set of linear inequalities, the maximum
number of inequalities which have together a feasible solution. This also
allows us to model other variants of the problem with different
objectives, for instance, to find a pricing which maximizes the number of
customers that are able to purchase their bundles, paying at least some
minimum amount, e.g. a fraction of their budgets.
We will argue that this latter variant of the problem is generally much
harder, and also present some approximation algorithms for interesting
special cases, including the tollbooth problem on the line.
computational aspects have received attention only quite recently in the
Computer Science community.
In a typical scenario, a company or a store has a set of items to sell to
a number of potential buyers, and knows (say through market research or
interaction) each customer's valuation for each subset (called bundle) of
items, which is the largest amount the customer is willing to pay for that
subset. If a customer buys a subset, his utility, which is the difference
between the valuation and the purchased price, must be non-negative. The
seller's task is to assign individual prices to the items, and allocate
bundles to (a subset of) customers, such that his total revenue, i.e. the
sum of prices of all sold items, is maximized. Clearly, a low price will
attract more customers while a high price will generate more revenue. As
an example (called the tollbooth problem), suppose that customers want to
buy bandwidth along subpaths of a network and are welling to pay up to
some amount for the bandwidth, how should one price the bandwidth along
the individual links in order to maximize the revenue?
The situation can be made more complicated by the fact that there maybe
a limited supply of each item, and by the requirement to have a pricing
mechanism offering some kind of fairness towards the different customers.
It turns out that even the simplest variants of this type of optimization
problems are NP-hard, and moreover it is hard to approximate the optimum
solution reasonably well. On the other hand, a logarithmic and
super-logarithmic approximations, respectively in the unlimited and
limited supply cases have been recently proposed. We will go briefly over
these and related results.
Then we will concentrate on the single-minded case, in which each customer
is interested only in buying a particular bundle. In this case, the
problem can be cast as some type of maximum feasible subsystem problem,
that is, of finding among a given set of linear inequalities, the maximum
number of inequalities which have together a feasible solution. This also
allows us to model other variants of the problem with different
objectives, for instance, to find a pricing which maximizes the number of
customers that are able to purchase their bundles, paying at least some
minimum amount, e.g. a fraction of their budgets.
We will argue that this latter variant of the problem is generally much
harder, and also present some approximation algorithms for interesting
special cases, including the tollbooth problem on the line.
Contact
Roxane Wetzel
900
--email hidden
passcode not visible
logged in users only
Roxane Wetzel, 02/07/2008 11:34
Roxane Wetzel, 02/06/2008 08:56
Roxane Wetzel, 12/20/2007 09:46
Roxane Wetzel, 12/20/2007 09:44 -- Created document.
Roxane Wetzel, 02/06/2008 08:56
Roxane Wetzel, 12/20/2007 09:46
Roxane Wetzel, 12/20/2007 09:44 -- Created document.