Colección SciELO Chile

Departamento Gestión de Conocimiento, Monitoreo y Prospección
Consultas o comentarios: productividad@anid.cl
Búsqueda Publicación
Búsqueda por Tema Título, Abstract y Keywords



Optimal item pricing in online combinatorial auctions
Indexado
WoS WOS:001093302500001
Scopus SCOPUS_ID:85175057859
DOI 10.1007/S10107-023-02027-2
Año 2024
Tipo artículo de investigación

Citas Totales

Autores Afiliación Chile

Instituciones Chile

% Participación
Internacional

Autores
Afiliación Extranjera

Instituciones
Extranjeras


Abstract



We consider a fundamental pricing problem in combinatorial auctions. We are given a set of indivisible items and a set of buyers with randomly drawn monotone valuations over subsets of items. A decision-maker sets item prices and then the buyers make sequential purchasing decisions, taking their favorite set among the remaining items. We parametrize an instance by d, the size of the largest set a buyer may want. Our main result asserts that there exist prices such that the expected (over the random valuations) welfare of the allocation they induce is at least a factor 1/(d+1) times the expected optimal welfare in hindsight. Moreover, we prove that this bound is tight. Thus, our result not only improves upon the 1/(4d-2) bound of Dütting et al., but also settles the approximation that can be achieved by using item prices. The existence of these prices follows from the existence of a fixed point of a related mapping, and therefore, it is non-constructive. However, we show how to compute such a fixed point in polynomial time, even if we only have sample access to the valuation distributions. We provide additional results for the special case when buyers’ valuations are known (but a posted-price mechanism is still desired), and an improved impossibility result for the special case of prophet inequalities for bipartite matching.

Revista



Revista ISSN
Mathematical Programming 0025-5610

Métricas Externas



PlumX Altmetric Dimensions

Muestra métricas de impacto externas asociadas a la publicación. Para mayor detalle:

Disciplinas de Investigación



WOS
Computer Science, Software Engineering
Mathematics, Applied
Operations Research & Management Science
Scopus
Mathematics (All)
Software
SciELO
Sin Disciplinas

Muestra la distribución de disciplinas para esta publicación.

Publicaciones WoS (Ediciones: ISSHP, ISTP, AHCI, SSCI, SCI), Scopus, SciELO Chile.

Colaboración Institucional



Muestra la distribución de colaboración, tanto nacional como extranjera, generada en esta publicación.


Autores - Afiliación



Ord. Autor Género Institución - País
1 CORREA-FONTECILLA, JOSE RAFAEL Hombre Universidad de Chile - Chile
2 Cristi, Andrés Hombre Universidad de Chile - Chile
3 GSCHWENDER-KRAUSE, ANTONIO ENRIQUE Hombre Faculty of Engineering - Australia
UNIV SYDNEY - Australia
4 Pollner, Tristan - Stanford University - Estados Unidos
Universidad de Stanford - Estados Unidos
Stanford Engineering - Estados Unidos
Stanford Univ - Estados Unidos
5 Weinberg, S. Matthew - Princeton University - Estados Unidos
Princeton Univ - Estados Unidos
School of Engineering and Applied Science - Estados Unidos

Muestra la afiliación y género (detectado) para los co-autores de la publicación.

Financiamiento



Fuente
National Science Foundation
Fondo Nacional de Desarrollo Científico y Tecnológico
Agencia Nacional de Investigación y Desarrollo
We thank the two anonymous reviewers for carefully reading the paper and providing many constructive comments that greatly improved the presentation.

Muestra la fuente de financiamiento declarada en la publicación.

Agradecimientos



Agradecimiento
This work was partially supported by NSF CCF-1955205 and by ANID (Chile) through grants ACT210005, FB210005 and FONDECYT 1220054.
We thank the two anonymous reviewers for carefully reading the paper and providing many constructive comments that greatly improved the presentation.

Muestra la fuente de financiamiento declarada en la publicación.