Computational aspects of combinatorial pricing problems [Elektronische Ressource] / von Patrick Briest

Sujets

• Mathematics

Informations

• Publié par: technischen_universitat_dortmund
• Publié le: 01 janvier 2007
• Nombre de lectures: 13
• Langue: English

Extrait

Computational Aspects of Combinatorial
Pricing Problems
Dissertation
zur Erlangung des Grades eines
Doktors der Naturwissenschaften
der Universitat¨ Dortmund
am Fachbereich Informatik
von
Patrick Briest
.............................................. Dortmund
2007.
Tag der mundlichen¨ Prufung:¨ 20. November 2007
Dekan: Professor Dr. Peter Buchholz
Gutachter: Privatdozent Dr. Piotr Krysta
Professor Dr. Ingo WegenerAbstract
...... Combinatorial pricing encompasses a wide range of natural optimization problems that arise in the
computation of revenue maximizing pricing schemes for a given set of goods, as well as the design of
profit maximizing auctions in strategic settings. We consider the computational side of several different
multi product and network pricing problems and, as most of the problems in this area are NP hard, we
focus on the design of approximation algorithms and corresponding inapproximability results.
...... In the unit demand multi product pricing problem it is assumed that each consumer has different
budgets for the products she is interested in and purchases a single product out of her set of alternatives.
Depending on how consumers choose their products once prices are fixed we distinguish the min buying,
max buying and rank buying models, in which consumers select the affordable product with smallest
price, highest price or highest rank according to some predefined preference list, respectively. We prove
that the max buying model allows for constant approximation guarantees and this is true even in the case
of limited product supply. For the min buying model we prove inapproximability beyond the known
logarithmic guarantees under standard complexity theoretic assumptions. Surprisingly, this result even
extends to the case of pricing with a price ladder constraint, i.e., a predefined relative order on the product
prices. Furthermore, similar results can be shown for the uniform budget version of the problem, which
corresponds to a special case of the unit demand envy free pricing problem, under an assumption about the
average case hardness of refuting random 3SAT instances. Introducing the notion of stochastic selection
rules we show that among a large class of selection rules based on the order of product prices the max
buying model is in fact the only one allowing for sub logarithmic approximation guarantees.
...... In the single minded pricing problem each consumer is interested in a single set of products, which
she purchases if the sum of prices does not exceed her budget. It turns out that our results on envy
free unit demand pricing can be extended to this scenario and yield inapproximability results for ratios
expressed in terms of the number of distinct products, thereby complementing existing hardness results.
On the algorithmic side, we present an algorithm with approximation guarantee that depends only on
the maximum size of the sets and the number of requests per product. Our algorithm’s ratio matches
previously known results in the worst case but has significantly better provable performance guarantees
on sparse problem instances. Viewing single minded as a network pricing problem in which we assign
prices to edges and consumers want to purchase paths in the network, it is proven that the problem remains
APX hard even on extremely sparse instances. For the special case of pricing on a line with paths that are
nested, we design an FPTAS and prove NP hardness.
...... In a Stackelberg network pricing game a so called leader sets the prices on a subset of the edges of
a network, the remaining edges have associated fixed costs. Once prices are fixed, one or more followers
purchase min cost subnetworks according to their requirements and pay the leader for all pricable edges
contained in their networks. We extend the analysis of the known single price algorithm, which assigns
the same price to all pricable edges, from cases in which the feasible subnetworks of a follower form the
basis of a matroid to the general case, thus, obtaining logarithmic approximation guarantees for general
Stackelberg games. We then consider a special 2 player game in which the follower buys a min cost
vertex cover in a bipartite graph and the leader sets prices on a subset of the vertices. We prove that this
problem is polynomial time solvable in some cases and allows for constant approximation guarantees in
general. Finally, we point out that results on unit demand and single minded pricing yield several strong
inapproximability results for Stackelberg pricing games with multiple followers..Acknowledgements
...... Many people have contributed in various ways to this thesis. First and foremost, I am deeply indebted
to Piotr Krysta for his consistent guidance in my research, his steady support and encouragement as an
always thoughtful advisor and a friend. To Ingo Wegener I want to express my gratefulness not only for
agreeing to serve as a reviewer for my thesis, but for being a great lecturer and sparking my interest in the
theoretical side of computer science in the first place.
...... Science is not a one man show. I want to thank all my co authors whom I was lucky enough to be
able to collaborate with in the course of my studies, especially Piotr Krysta and Martin Hoefer. I am also
greatly indebted to my colleagues both in Dortmund and Liverpool for stimulating a fantastic research
environment and making the last three years a most enjoyable and memorable time.
...... This thesis would not exist without the financial support of the DFG through grant Kr 2332/1 within
the Emmy Noether program.
...... Last, but not least, I want to thank my parents for their never faltering support throughout the last 28
years, without which none of this would have been possible..Contents
1 Introduction 9
1.1 Pricing for Unit Demand Consumers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.1.1 New Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2 Pricing for Single Minded Consumers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.2.1 New Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3 Stackelberg Pricing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.3.1 New Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.4 List of Publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2 Buying Cheap is Expensive: The Min Buying Model 21
2.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2 The Single Price Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3 Hardness of Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.1 Independent Sets and Derandomized Graph Products . . . . . . . . . . . . . . . . 25
2.3.2 Reduction to UDP(C)-MIN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4 AnO(‘) Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.5 Literature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3 The Other End of the Chart: The Max Buying Model 35
3.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2 Hardness of Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.3 A Local Search Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.4 Max Buying with Price Ladder Constraint . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.4.1 A PTAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.4.2 Strong NP Hardness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.5 A Max Buying Pricing Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.6 Literature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4 The Space Between: Stochastic Selection and the Rank Buying Model 49
4.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.2 Hardness of Stochastic Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.3 Approximability of Rank Buying . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.4 Literature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5 Uniform Budgets: The Envy Free Pricing Problem 57
5.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.2 Hardness of Approximation - Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.3 Full Proof of Theorem 5.2.10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
?5.3.1 R3SAT (poly(n)) hardness of Constant DegreeBBIS . . . . . . . . . . . . . . . 63
7Contents
5.3.2 Gap Amplification for Bounded DegreeBBIS . . . . . . . . . . . . . . . . . . . . 66
5.3.3 Maximum Expanding Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.3.4 Reduction to UDP(C)-MIN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.4 Literature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
6 Network Pricing I: The Single Minded Pricing