Search Results

Documents authored by Goel, Gagan


Document
Reservation Exchange Markets for Internet Advertising

Authors: Gagan Goel, Stefano Leonardi, Vahab Mirrokni, Afshin Nikzad, and Renato Paes-Leme

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)


Abstract
Internet display advertising industry follows two main business models. One model is based on direct deals between publishers and advertisers where they sign legal contracts containing terms of fulfillment for a future inventory. The second model is a spot market based on auctioning page views in real-time on advertising exchange (AdX) platforms such as DoubleClick's Ad Exchange, RightMedia, or AppNexus. These exchanges play the role of intermediaries who sell items (e.g. page-views) on behalf of a seller (e.g. a publisher) to buyers (e.g., advertisers) on the opposite side of the market. The computational and economics issues arising in this second model have been extensively investigated in recent times. In this work, we consider a third emerging model called reservation exchange market. A reservation exchange is a two-sided market between buyer orders for blocks of advertisers' impressions and seller orders for blocks of publishers' page views. The goal is to match seller orders to buyer orders while providing the right incentives to both sides. In this work we first describe the important features of mechanisms for efficient reservation exchange markets. We then address the algorithmic problems of designing revenue sharing schemes to provide a fair division between sellers of the revenue collected from buyers. A major conceptual contribution of this work is in showing that even though both clinching ascending auctions and VCG mechanisms achieve the same outcome from a buyer perspective, however, from the perspective of revenue sharing among sellers, clinching ascending auctions are much more informative than VCG auctions.

Cite as

Gagan Goel, Stefano Leonardi, Vahab Mirrokni, Afshin Nikzad, and Renato Paes-Leme. Reservation Exchange Markets for Internet Advertising. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 142:1-142:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{goel_et_al:LIPIcs.ICALP.2016.142,
  author =	{Goel, Gagan and Leonardi, Stefano and Mirrokni, Vahab and Nikzad, Afshin and Paes-Leme, Renato},
  title =	{{Reservation Exchange Markets for Internet Advertising}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{142:1--142:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.142},
  URN =		{urn:nbn:de:0030-drops-62863},
  doi =		{10.4230/LIPIcs.ICALP.2016.142},
  annote =	{Keywords: Reservation Markets, Internet Advertising, Two-sided Markets, Clinching Auction, Envy-free allocations}
}
Document
Combinatorial Problems with Discounted Price Functions in Multi-agent Systems

Authors: Gagan Goel, Pushkar Tripathi, and Lei Wang

Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)


Abstract
Motivated by economic thought, a recent research agenda has suggested the algorithmic study of combinatorial optimization problems under functions which satisfy the property of decreasing marginal cost. A natural first step to model such functions is to consider submodular functions. However, many fundamental problems have turned out to be extremely hard to approximate under general submodular functions, thus indicating the need for a systematic study of subclasses of submodular functions that are practically motivated and yield good approximation ratios. In this paper, we introduce and study an important subclass of submodular functions, which we call discounted price functions. These functions are succinctly representable and generalize linear(additive) price functions. We study the following fundamental combinatorial optimization problems: edge cover, spanning tree, perfect matching and $s-t$ path. We give both upper and lower bound for the approximability of these problems.

Cite as

Gagan Goel, Pushkar Tripathi, and Lei Wang. Combinatorial Problems with Discounted Price Functions in Multi-agent Systems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 436-446, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{goel_et_al:LIPIcs.FSTTCS.2010.436,
  author =	{Goel, Gagan and Tripathi, Pushkar and Wang, Lei},
  title =	{{Combinatorial Problems with Discounted Price Functions in Multi-agent Systems}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
  pages =	{436--446},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-23-1},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{8},
  editor =	{Lodaya, Kamal and Mahajan, Meena},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.436},
  URN =		{urn:nbn:de:0030-drops-28847},
  doi =		{10.4230/LIPIcs.FSTTCS.2010.436},
  annote =	{Keywords: Approximation algorithm, decreasing marginal cost, submodular function, discounted price function}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail