Research Repository

A note on the efficiency of position mechanisms with budget constraints

Voudouris, Alexandros A (2019) 'A note on the efficiency of position mechanisms with budget constraints.' Information Processing Letters, 143. 28 - 33. ISSN 0020-0190

liquid.GSP.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (227kB) | Preview


We study the social efficiency of several well-known mechanisms for the allocation of a set of available (advertising) positions to a set of competing budget-constrained users (advertisers). Specifically, we focus on the Generalized Second Price auction (GSP), the Vickrey–Clarke–Groves mechanism (VCG) and the Expressive Generalized First Price auction (EGFP). Using liquid welfare as our efficiency benchmark, we prove a tight bound of 2 on the liquid price of anarchy and stability of these mechanisms for pure Nash equilibria.

Item Type: Article
Uncontrolled Keywords: Analysis of algorithms, Position mechanisms, Liquid welfare, Budget constraints, Liquid price of anarchy
Divisions: Faculty of Science and Health > Computer Science and Electronic Engineering, School of
Depositing User: Elements
Date Deposited: 20 May 2020 11:34
Last Modified: 20 May 2020 11:53

Actions (login required)

View Item View Item