hide
Free keywords:
Computer Science, Computer Science and Game Theory, cs.GT,Computer Science, Computational Geometry, cs.CG,Computer Science, Data Structures and Algorithms, cs.DS
Abstract:
Consider the following toy problem. There are $m$ rectangles and $n$ points
on the plane. Each rectangle $R$ is a consumer with budget $B_R$, who is
interested in purchasing the cheapest item (point) inside R, given that she has
enough budget. Our job is to price the items to maximize the revenue. This
problem can also be defined on higher dimensions. We call this problem the
geometric pricing problem.
In this paper, we study a new class of problems arising from a geometric
aspect of the pricing problem. It intuitively captures typical real-world
assumptions that have been widely studied in marketing research, healthcare
economics, etc. It also helps classify other well-known pricing problems, such
as the highway pricing problem and the graph vertex pricing problem on planar
and bipartite graphs. Moreover, this problem turns out to have close
connections to other natural geometric problems such as the geometric versions
of the unique coverage and maximum feasible subsystem problems.
We show that the low dimensionality arising in this pricing problem does lead
to improved approximation ratios, by presenting sublinear-approximation
algorithms for two central versions of the problem: unit-demand uniform-budget
min-buying and single-minded pricing problems. Our algorithm is obtained by
combining algorithmic pricing and geometric techniques. These results suggest
that considering geometric aspect might be a promising research direction in
obtaining improved approximation algorithms for such pricing problems. To the
best of our knowledge, this is one of very few problems in the intersection
between geometry and algorithmic pricing areas. Thus its study may lead to new
algorithmic techniques that could benefit both areas.
