Computational aspects of combinatorial pricing problems
| dc.contributor.advisor | Krysta, Piotr | |
| dc.contributor.author | Briest, Patrick | |
| dc.contributor.referee | Wegener, Ingo | |
| dc.date.accepted | 2007-11-20 | |
| dc.date.accessioned | 2007-11-26T10:54:02Z | |
| dc.date.available | 2007-11-26T10:54:02Z | |
| dc.date.issued | 2007-11-26T10:54:02Z | |
| dc.description.abstract | 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 maxbuying 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 envyfree 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. | en |
| dc.identifier.uri | http://hdl.handle.net/2003/24877 | |
| dc.identifier.uri | http://dx.doi.org/10.17877/DE290R-483 | |
| dc.identifier.urn | urn:nbn:de:hbz:290-2003/24877-8 | |
| dc.language.iso | en | en |
| dc.subject | approximation algorithms | en |
| dc.subject | hardness of approximation | en |
| dc.subject | pricing | en |
| dc.subject | algorithmic game theory | en |
| dc.subject.ddc | 004 | |
| dc.title | Computational aspects of combinatorial pricing problems | en |
| dc.type | Text | en |
| dc.type.publicationtype | doctoralThesis | en |
| dcterms.accessRights | open access |