NDLI: Polyhedral Clinching Auctions and the AdWords Polytope

Content Provider	ACM Digital Library
Author	Goel, Gagan Mirrokni, Vahab Leme, Renato Paes
Copyright Year	2015
Abstract	A central issue in applying auction theory in practice is the problem of dealing with budget-constrained agents. A desirable goal in practice is to design incentive compatible, individually rational, and Pareto optimal auctions while respecting the budget constraints. Achieving this goal is particularly challenging in the presence of nontrivial combinatorial constraints over the set of feasible allocations. Toward this goal and motivated by AdWords auctions, we present an auction for $\textit{polymatroidal}$ environments satisfying these properties. Our auction employs a novel clinching technique with a clean geometric description and only needs an oracle access to the submodular function defining the polymatroid. As a result, this auction not only simplifies and generalizes all previous results, it applies to several new applications including AdWords Auctions, bandwidth markets, and video on demand. In particular, our characterization of the AdWords auction as polymatroidal constraints might be of independent interest. This allows us to design the first mechanism for Ad Auctions taking into account simultaneously budgets, multiple keywords and multiple slots. We show that it is impossible to extend this result to generic polyhedral constraints. This also implies an impossibility result for multiunit auctions with decreasing marginal utilities in the presence of budget constraints.
Starting Page	1
Ending Page	27
Page Count	27
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/2757277
Journal	Journal of the ACM (JACM)
Volume Number	62
Issue Number	3
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2015-06-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	AdWords Clinching auctions Budgets Polymatroids
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Polyhedral Clinching Auctions and the Adwords Polytope (2013)

Polyhedral clinching auctions and the adwords polytope

AdWords and generalized online matching

Bayesian Combinatorial Auctions

Polyhedral Clinching Auctions and the Adwords Polytope

A subdivision-based algorithm for the sparse resultant

Truth revelation in approximately efficient combinatorial auctions

Online algorithms for market clearing

Single-value combinatorial auctions and algorithmic implementation in undominated strategies

Polyhedral Clinching Auctions and the AdWords Polytope

Similar Documents

Polyhedral Clinching Auctions and the Adwords Polytope (2013)

Polyhedral clinching auctions and the adwords polytope

AdWords and generalized online matching

Bayesian Combinatorial Auctions

Polyhedral Clinching Auctions and the Adwords Polytope

A subdivision-based algorithm for the sparse resultant

Truth revelation in approximately efficient combinatorial auctions

Online algorithms for market clearing

Single-value combinatorial auctions and algorithmic implementation in undominated strategies

Polyhedral Clinching Auctions and the AdWords Polytope