---
_id: '11773'
abstract:
- lang: eng
  text: "Ad exchanges are an emerging platform for trading advertisement slots on
    the web with billions of dollars revenue per year. Every time a user visits a
    web page, the publisher of that web page can ask an ad exchange to auction off
    the ad slots on this page to determine which advertisements are shown at which
    price. Due to the high volume of traffic, ad networks typically act as mediators
    for individual advertisers at ad exchanges. If multiple advertisers in an ad network
    are interested in the ad slots of the same auction, the ad network might use a
    “local” auction to resell the obtained ad slots among its advertisers.\r\n\r\nIn
    this work we want to deepen the theoretical understanding of these new markets
    by analyzing them from the viewpoint of combinatorial auctions. Prior work studied
    mostly single-item auctions, while we allow the advertisers to express richer
    preferences over multiple items. We develop a game-theoretic model for the entanglement
    of the central auction at the ad exchange with the local auctions at the ad networks.
    We consider the incentives of all three involved parties and suggest a three-party
    competitive equilibrium, an extension of the Walrasian equilibrium that ensures
    envy-freeness for all participants. We show the existence of a three-party competitive
    equilibrium and a polynomial-time algorithm to find one for gross-substitute bidder
    valuations."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Oren
  full_name: Ben-Zwi, Oren
  last_name: Ben-Zwi
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Veronika
  full_name: Loitzenbauer, Veronika
  last_name: Loitzenbauer
citation:
  ama: 'Ben-Zwi O, Henzinger MH, Loitzenbauer V. Ad exchange: Envy-free auctions with
    mediators. In: <i>11th International Conference on Web and Internet Economics</i>.
    Vol 9470. Springer Nature; 2015:104–117. doi:<a href="https://doi.org/10.1007/978-3-662-48995-6_8">10.1007/978-3-662-48995-6_8</a>'
  apa: 'Ben-Zwi, O., Henzinger, M. H., &#38; Loitzenbauer, V. (2015). Ad exchange:
    Envy-free auctions with mediators. In <i>11th International Conference on Web
    and Internet Economics</i> (Vol. 9470, pp. 104–117). Amsterdam, Netherlands: Springer
    Nature. <a href="https://doi.org/10.1007/978-3-662-48995-6_8">https://doi.org/10.1007/978-3-662-48995-6_8</a>'
  chicago: 'Ben-Zwi, Oren, Monika H Henzinger, and Veronika Loitzenbauer. “Ad Exchange:
    Envy-Free Auctions with Mediators.” In <i>11th International Conference on Web
    and Internet Economics</i>, 9470:104–117. Springer Nature, 2015. <a href="https://doi.org/10.1007/978-3-662-48995-6_8">https://doi.org/10.1007/978-3-662-48995-6_8</a>.'
  ieee: 'O. Ben-Zwi, M. H. Henzinger, and V. Loitzenbauer, “Ad exchange: Envy-free
    auctions with mediators,” in <i>11th International Conference on Web and Internet
    Economics</i>, Amsterdam, Netherlands, 2015, vol. 9470, pp. 104–117.'
  ista: 'Ben-Zwi O, Henzinger MH, Loitzenbauer V. 2015. Ad exchange: Envy-free auctions
    with mediators. 11th International Conference on Web and Internet Economics. WINE:
    International Conference on Web and Internet Economics, LNCS, vol. 9470, 104–117.'
  mla: 'Ben-Zwi, Oren, et al. “Ad Exchange: Envy-Free Auctions with Mediators.” <i>11th
    International Conference on Web and Internet Economics</i>, vol. 9470, Springer
    Nature, 2015, pp. 104–117, doi:<a href="https://doi.org/10.1007/978-3-662-48995-6_8">10.1007/978-3-662-48995-6_8</a>.'
  short: O. Ben-Zwi, M.H. Henzinger, V. Loitzenbauer, in:, 11th International Conference
    on Web and Internet Economics, Springer Nature, 2015, pp. 104–117.
conference:
  end_date: 2015-09-12
  location: Amsterdam, Netherlands
  name: 'WINE: International Conference on Web and Internet Economics'
  start_date: 2015-09-09
date_created: 2022-08-08T13:33:56Z
date_published: 2015-12-09T00:00:00Z
date_updated: 2023-02-10T09:06:23Z
day: '09'
doi: 10.1007/978-3-662-48995-6_8
extern: '1'
external_id:
  arxiv:
  - '1604.05562'
intvolume: '      9470'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.1604.05562
month: '12'
oa: 1
oa_version: Preprint
page: 104–117
publication: 11th International Conference on Web and Internet Economics
publication_identifier:
  eisbn:
  - '9783662489956'
  isbn:
  - '9783662489949'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Ad exchange: Envy-free auctions with mediators'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9470
year: '2015'
...
---
_id: '11774'
abstract:
- lang: eng
  text: "Combinatorial auctions (CA) are a well-studied area in algorithmic mechanism
    design. However, contrary to the standard model, empirical studies suggest that
    a bidder’s valuation often does not depend solely on the goods assigned to him.
    For instance, in adwords auctions an advertiser might not want his ads to be displayed
    next to his competitors’ ads. In this paper, we propose and analyze several natural
    graph-theoretic models that incorporate such negative externalities, in which
    bidders form a directed conflict graph with maximum out-degree Δ. We design algorithms
    and truthful mechanisms for social welfare maximization that attain approximation
    ratios depending on Δ.\r\n\r\nFor CA, our results are twofold: (1) A lottery that
    eliminates conflicts by discarding bidders/items independent of the bids. It allows
    to apply any truthful \U0001D6FC-approximation mechanism for conflict-free valuations
    and yields an \U0001D4AA(\U0001D6FCΔ)-approximation mechanism. (2) For fractionally
    sub-additive valuations, we design a rounding algorithm via a novel combination
    of a semi-definite program and a linear program, resulting in a cone program;
    the approximation ratio is \U0001D4AA((ΔloglogΔ)/logΔ). The ratios are almost
    optimal given existing hardness results.\r\n\r\nFor adwords auctions, we present
    several algorithms for the most relevant scenario when the number of items is
    small. In particular, we design a truthful mechanism with approximation ratio
    \U0001D45C(Δ) when the number of items is only logarithmic in the number of bidders."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Yun Kuen
  full_name: Cheung, Yun Kuen
  last_name: Cheung
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Martin
  full_name: Hoefer, Martin
  last_name: Hoefer
- first_name: Martin
  full_name: Starnberger, Martin
  last_name: Starnberger
citation:
  ama: 'Cheung YK, Henzinger MH, Hoefer M, Starnberger M. Combinatorial auctions with
    conflict-based externalities. In: <i>11th International Conference on Web and
    Internet Economics</i>. Vol 9470. Springer Nature; 2015:230–243. doi:<a href="https://doi.org/10.1007/978-3-662-48995-6_17">10.1007/978-3-662-48995-6_17</a>'
  apa: 'Cheung, Y. K., Henzinger, M. H., Hoefer, M., &#38; Starnberger, M. (2015).
    Combinatorial auctions with conflict-based externalities. In <i>11th International
    Conference on Web and Internet Economics</i> (Vol. 9470, pp. 230–243). Amsterdam,
    Netherlands: Springer Nature. <a href="https://doi.org/10.1007/978-3-662-48995-6_17">https://doi.org/10.1007/978-3-662-48995-6_17</a>'
  chicago: Cheung, Yun Kuen, Monika H Henzinger, Martin Hoefer, and Martin Starnberger.
    “Combinatorial Auctions with Conflict-Based Externalities.” In <i>11th International
    Conference on Web and Internet Economics</i>, 9470:230–243. Springer Nature, 2015.
    <a href="https://doi.org/10.1007/978-3-662-48995-6_17">https://doi.org/10.1007/978-3-662-48995-6_17</a>.
  ieee: Y. K. Cheung, M. H. Henzinger, M. Hoefer, and M. Starnberger, “Combinatorial
    auctions with conflict-based externalities,” in <i>11th International Conference
    on Web and Internet Economics</i>, Amsterdam, Netherlands, 2015, vol. 9470, pp.
    230–243.
  ista: 'Cheung YK, Henzinger MH, Hoefer M, Starnberger M. 2015. Combinatorial auctions
    with conflict-based externalities. 11th International Conference on Web and Internet
    Economics. WINE: International Conference on Web and Internet Economics, LNCS,
    vol. 9470, 230–243.'
  mla: Cheung, Yun Kuen, et al. “Combinatorial Auctions with Conflict-Based Externalities.”
    <i>11th International Conference on Web and Internet Economics</i>, vol. 9470,
    Springer Nature, 2015, pp. 230–243, doi:<a href="https://doi.org/10.1007/978-3-662-48995-6_17">10.1007/978-3-662-48995-6_17</a>.
  short: Y.K. Cheung, M.H. Henzinger, M. Hoefer, M. Starnberger, in:, 11th International
    Conference on Web and Internet Economics, Springer Nature, 2015, pp. 230–243.
conference:
  end_date: 2015-12-12
  location: Amsterdam, Netherlands
  name: 'WINE: International Conference on Web and Internet Economics'
  start_date: 2015-12-09
date_created: 2022-08-08T13:54:32Z
date_published: 2015-12-09T00:00:00Z
date_updated: 2023-02-10T09:08:30Z
day: '09'
doi: 10.1007/978-3-662-48995-6_17
extern: '1'
external_id:
  arxiv:
  - '1509.09147'
intvolume: '      9470'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.1509.09147
month: '12'
oa: 1
oa_version: Preprint
page: 230–243
publication: 11th International Conference on Web and Internet Economics
publication_identifier:
  eisbn:
  - '9783662489956'
  isbn:
  - '9783662489949'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Combinatorial auctions with conflict-based externalities
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9470
year: '2015'
...