Approximation algorithms for envy-free profit-maximization problems
Speaker: | Chaitanya Swamy |
---|---|
Affiliation: | University of Waterloo |
Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
We
consider
a
class
of
pricing
problems,
called
envy-free
profit-maximization
problems,
wherein
a
seller
wants
to
set
prices
on
items
and
allocate
items
(which
are
available
in
limited
supply)
to
customers
so
as
to
maximize
his
profit,
with
the
constraint
that
each
customer
receives
a
utility-maximizing
subset
of
items.
We
consider
the
important
setting
where
each
customer
desires
a
single
set
of
items,
which
is
called
the
single-minded
problem.
Even
special
cases
of
this
problem,
where
the
underlying
set
system
has
a
great
deal
of
combinatorial
structure
(e.g.,
paths
on
a
tree),
are
NP-hard
and
surprisingly
difficult,
with
no
non-trivial
approximation
guarantees
known.
We
present
the
first
approximation
algorithms
for
this
class
of
problems.
Our
approximation
bounds
are
obtained
by
comparing
the
profit
of
our
solution
against
the
optimal
value
of
the
corresponding
social-welfare-maximization
(SWM)
problem,
which
is
the
problem
of
finding
a
"winner-set"
of
customers
with
maximum
total
value.
We
show
that
any
LP-based
\rho-approximation
algorithm
for
the
corresponding
SWM
problem
can
be
used
to
obtain
profit
at
least
OPT/O(\rho\log
u_max),
where
OPT
is
the
optimal
value
of
the
SWM
problem,
and
u_max
is
the
maximum
supply
of
an
item.
This
immediately
yields
approximation
algorithms
for
a
host
of
single-minded
envy-free
profit-maximization
problems.
The
analysis
leverages
LP
duality
theory
in
a
novel
way.
The
talk
will
be
self-contained.
Joint work with Maurice Cheung.