We consider the revenue maximization problem with sharp multi-demand, in which m indivisible items have to be sold to n potential buyers. Each buyer i is interested in getting exactly di items, and each item j gives a benefit vij to buyer i. In particular, each item j has a quality qj, each buyer i has a value vi and the benefit vij is defined as the product viqj. The problem asks to determine a price for each item and an allocation of bundles of items to buyers with the aim of maximizing the total revenue, i.e., the sum of the prices of all the sold items. The allocation must be envy-free, that is, each buyer must be happy with her assigned bundle and cannot improve her utility, defined as the benefit of all the items in the bundle minus their purchase prices, by receiving any different bundle. We first prove that the problem cannot be approximated within a factor of O(m1−ϵ), for any ϵ>0, unless P=NP and that this result is asymptotically tight. In fact, we show that a simple greedy algorithm provides an m-approximation of the optimal revenue (this approximation guarantee holds even for the generalization in which the benefits vij are completely arbitrary). Then, we focus on an interesting subclass of “proper” instances, i.e., not containing buyers (useless buyers) who are a priori known to be not able to receive any bundle. For these instances, we design an interesting 2-approximation algorithm and show that no better approximation is possible unless P=NP. We stress that it is possible to efficiently check if an instance is proper and, if discarding useless buyers is allowed, an instance can be made proper in polynomial time without worsening the value of its optimal solution.

Approximating the revenue maximization problem with sharp demands

FLAMMINI, MICHELE
;
2017

Abstract

We consider the revenue maximization problem with sharp multi-demand, in which m indivisible items have to be sold to n potential buyers. Each buyer i is interested in getting exactly di items, and each item j gives a benefit vij to buyer i. In particular, each item j has a quality qj, each buyer i has a value vi and the benefit vij is defined as the product viqj. The problem asks to determine a price for each item and an allocation of bundles of items to buyers with the aim of maximizing the total revenue, i.e., the sum of the prices of all the sold items. The allocation must be envy-free, that is, each buyer must be happy with her assigned bundle and cannot improve her utility, defined as the benefit of all the items in the bundle minus their purchase prices, by receiving any different bundle. We first prove that the problem cannot be approximated within a factor of O(m1−ϵ), for any ϵ>0, unless P=NP and that this result is asymptotically tight. In fact, we show that a simple greedy algorithm provides an m-approximation of the optimal revenue (this approximation guarantee holds even for the generalization in which the benefits vij are completely arbitrary). Then, we focus on an interesting subclass of “proper” instances, i.e., not containing buyers (useless buyers) who are a priori known to be not able to receive any bundle. For these instances, we design an interesting 2-approximation algorithm and show that no better approximation is possible unless P=NP. We stress that it is possible to efficiently check if an instance is proper and, if discarding useless buyers is allowed, an instance can be made proper in polynomial time without worsening the value of its optimal solution.
Envy-freeness, Revenue maximization, Auctions with sharp demands
File in questo prodotto:
File Dimensione Formato  
2017_TheorComputSci_662_Bilo.pdf

non disponibili

Descrizione: Articolo principale
Tipologia: Versione Editoriale (PDF)
Licenza: Non pubblico
Dimensione 556.71 kB
Formato Adobe PDF
556.71 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12571/228
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 8
social impact