Graph Pricing with Limited Supply
| Autor: | Zachary Friggstad, Maryam Mahboub |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Combinatorics
Vertex (graph theory) 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Graph (abstract data type) 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology 01 natural sciences Mathematics |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783030835071 WADS |
| DOI: | 10.1007/978-3-030-83508-8_29 |
| Popis: | We study approximation algorithms for graph pricing with vertex capacities yet without the traditional envy-free constraint. Specifically, we have a set of items V and a set of customers X where each customer \(i \in X\) has a budget \(b_i\) and is interested in a bundle of items \(S_i \subseteq V\) with \(|S_i| \le 2\). However, there is a limited supply of each item: we only have \(\mu _v\) copies of item v to sell for each \(v \in V\). We should assign a price p(v) to each \(v \in V\) and choose a subset \(Y \subseteq X\) of customers so that each \(i \in Y\) can afford their bundle (\(p(S_i) \le b_i\)) and at most \(\mu _v\) chosen customers have item v in their bundle for each item \(v \in V\). Each customer \(i \in Y\) pays \(p(S_i)\) for the bundle they purchased: our goal is to do this in a way that maximizes revenue. Such pricing problems have been studied from the perspective of envy-freeness where we also must ensure that \(p(S_i) \ge b_i\) for each \(i \notin Y\). However, the version where we simply allocate items to customers after setting prices and do not worry about the envy-free condition has received less attention. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|