Linear Program-Based Approximation for Personalized Reserve Prices | PERPUSTAKAAN UNIVERSITAS KATOLIK PARAHYANGAN

Text

Linear Program-Based Approximation for Personalized Reserve Prices

Derakhshan, Mahsa - Nama Orang; Golrezaei, Negin - Nama Orang; Leme, Renato Paes - Nama Orang;

We study the problem of computing data-driven personalized reserve prices in eager second price auctions without having any assumption on valuation distributions. Here, the input is a data set that contains the submitted bids of n buyers in a set of auctions, and the problem is to return personalized reserve prices r that maximize the revenue earned on these auctions by running eager second price auctions with reserve r. For this problem, which is known to be NP complete, we present a novel linear program (LP) formulation and a rounding procedure, which achieves a 0.684 approximation. This improves over the 12-approximation algorithm from Roughgarden and Wang. We show that our analysis is tight for this rounding procedure. We also bound the integrality gap of the LP, which shows that it is impossible to design an algorithm that yields an approximation factor larger than 0.828 with respect to this LP.

Ketersediaan

Barcode		Tipe Koleksi	Nomor Panggil	Lokasi	Status
art140903	null	Artikel		Gdg9-Lt3	Tersedia namun tidak untuk dipinjamkan - No Loan

Informasi Detail

Judul Seri: MANAGEMENT SCIENCE; Vol.68 No.3 March 2022
No. Panggil: -
Penerbit: : .,
Deskripsi Fisik: p. 1849-1864
Bahasa: English
ISBN/ISSN: -
Klasifikasi: NONE
Tipe Isi: -
Tipe Media: -
Tipe Pembawa: -
Edisi: -
Subjek: DATA-DRIVEN OPTIMIZATION
PERSONALIZED RESERVE PRICES
EAGER SECOND PRICE AUCTIONS
LP-BASED ALGORITHM
Info Detail Spesifik: https://doi.org/10.1287/mnsc.2020.3897
Pernyataan Tanggungjawab: Mahsa Derakhshan, Negin Golrezaei, Renato Paes Leme

Versi lain/terkait

Tidak tersedia versi lain

Lampiran Berkas

Tidak Ada Data

Komentar

Anda harus masuk sebelum memberikan komentar