Second-Price Ad Auctions with Binary Bids and markets with good competition

Autor(es)

Fernandes, Cristina G. ; Schouery, Rafael C. S.

• Tipo de documento: Artigo Científico
• Fonte: THEORETICAL COMPUTER SCIENCE; v. 540, p. 12-pg., 2014-06-26.

Resumo

Given a bipartite graph G = (U, V, E) with U = {1, ..., n}, and a positive budget By for each v in V. a B-matching M in G is a second-price B-matching if, for every edge uv in M, there is an edge uw in E so that less than B-w edges u'w with u' < u belong to M. The Second-Price Ad Auction with Binary Bids (B2PAA) consists of, given G and B as above, finding a second-price B-matching in G as large as possible. The particular case of this problem where B-v = 1 for all v, called Second-Price Matching (2PM), is known to be APX-hard and there is a 2-approximation for it. We present a way to use this approximation and similar ones to approximate B2PAA. Also, we formalize the idea of a competitive market, present an improved approximation for 2PM on competitive markets, extend the inapproximability result for competitive markets and analyze the performance of an algorithm of Azar, Birnbaum, Karlin, and Nguyen for the online 2PM on competitive markets. Our improved approximation can also be used for B2PAA. (C) 2013 Elsevier B.V. All rights reserved. (AU)

• Processo FAPESP: 09/00387-7 - Otimização combinatória e teoria dos jogos
• Beneficiário: Rafael Crivellari Saliba Schouery
• Modalidade de apoio: Bolsas no Brasil - Doutorado Direto