NDLI: Simple Mechanisms for Agents with Complements

Please wait, while we are loading the content...

Ironing in the Dark

Position-Indexed Formulations for Kidney Exchange

Deferred Acceptance with Compensation Chains

The Revelation Principle for Mechanism Design with Reporting Costs

When Should an Expert Make a Prediction?

Optimal Commitments in Asymmetric Auctions with Incomplete Information

On Voting and Facility Location

Planning Problems for Sophisticated Agents with Present Bias

The Invisible Hand of Dynamic Market Pricing

Dynamic Pricing in a Labor Market: Surge Pricing and Flexible Work on the Uber Platform

Imperfect-Recall Abstractions with Bounds in Games

The Seasonality Of Paid Search Effectiveness From A Long Running Field Test

Mechanism Design for Subadditive Agents via an Ex Ante Relaxation

General Threshold Model for Social Cascades: Analysis and Simulations

Pricing with Limited Knowledge of Demand

Computational Extensive-Form Games

Strategic Payment Routing in Financial Credit Networks

Petty Envy When Assigning Objects

The Pareto Frontier for Random Mechanisms

Large Market Games with Near Optimal Efficiency

Truthful Outcomes from Non-Truthful Position Auctions

Fair Resource Allocation in A Volatile Marketplace

A/B Testing of Auctions

The Stochastic Matching Problem with (Very) Few Queries

Which Is the Fairest (Rent Division) of Them All?

Optimal Auctions for Negatively Correlated Items

The Possibilities and Limitations of Private Prediction Markets

Sequential Mechanisms with Ex-post Participation Guarantees

Towards Large-Scale Deliberative Decision-Making: Small Groups and the Importance of Triads

Procrastination with Variable Present Bias

Lottery Pricing Equilibria

Intrinsic Robustness of the Price of Anarchy: Abstract of the Kalai Prize Talk

A Hydraulic Approach to Equilibria of Resource Selection Games

Returns to Consumer Search: Evidence from eBay

Where to Sell: Simulating Auctions From Learning Algorithms

Impact of Community Structure on Cascades

The Strange Case of Privacy in Equilibrium Models

Ascending-Price Algorithms for Unknown Markets

Sybil Detection Using Latent Network Structure

"Strategic" Behavior in a Strategy-proof Environment

Mechanism Design with Selective Verification

Rate of Price Discovery in Iterative Combinatorial Auctions

Dynamic Mechanism Design with Budget Constrained Buyers under Limited Commitment

Revealed Preference at Scale: Learning Personalized Preferences from Assortment Choices

The FedEx Problem

Cadet-Branch Matching in a Quasi-Linear Labor Market

Strategic Ironing in Pay-as-Bid Auctions: Equilibrium Existence with Private Information

Arbitrage-Free Combinatorial Market Making via Integer Programming

Optimal Auctions with Restricted Allocations

The Unreasonable Fairness of Maximum Nash Welfare

A Dynamic Model of Crowdfunding

Online Budgeted Allocation with General Budgets

Hardness Results for Signaling in Bayesian Zero-Sum and Network Routing Games

The Good, the Bad, and the Unflinchingly Selfish: Cooperative Decision-Making can be Predicted with high Accuracy when using only Three Behavioral Types

A Near-Optimal Exploration-Exploitation Approach for Assortment Selection

Dynamics of Evolving Social Groups

Bayesian Exploration: Incentivizing Exploration in Bayesian Games

Competitive Equilibrium and Trading Networks: A Network Flow Approach

Economic Recommendation Systems: One Page Abstract

On Matching and Thickness in Heterogeneous Dynamic Markets

Mechanisms with Referrals: VCG Mechanisms and Multilevel Mechanisms

On the Efficacy of Static Prices for Revenue Management in the Face of Strategic Customers

Feature-based Dynamic Pricing

Dynamic Taxes for Polynomial Congestion Games

Descending Price Optimally Coordinates Search

Virtual Demand and Stable Mechanisms

Pay-as-Bid: Selling Divisible Goods

Informed Truthfulness in Multi-Task Peer Prediction

Does Information Revelation Improve Revenue?

How Effective Can Simple Ordinal Peer Grading Be?

Blockchain Mining Games

Matroid Online Bipartite Matching and Vertex Cover

The Mysteries of Security Games: Equilibrium Computation Becomes Combinatorial Algorithm Design

Understanding Emerging Threats to Online Advertising

Minimizing Regret with Multiple Reserves

Dynamic Conflict on a Network

Persuasion with Limited Communication

Average Case Performance of Replicator Dynamics in Potential Games via Computing Regions of Attraction

Clearing Payments in Financial Networks with Credit Default Swaps [Extended Abstract]

What Matters in School Choice Tie-breakings?: How Competition Guides Design

Simple Mechanisms for Agents with Complements

Assortment Optimization under a Random Swap based Distribution over Permutations Model

Simple Mechanisms for Agents with Complements

Content Provider	ACM Digital Library
Author	Feldman, Michal Reiner, Guy Friedler, Ophir Morgenstern, Jamie
Abstract	We study the efficiency of simple auctions in the presence of complements. Devanur et al. [2015] introduced the single-bid auction, and showed that it has a price of anarchy (PoA) of O(log m) for complement-free (i.e., subadditive) valuations. Prior to our work, no non-trivial upper bound on the PoA of single bid auctions was known for valuations exhibiting complements. We introduce a hierarchy over valuations, where levels of the hierarchy correspond to the degree of complementarity, and the PoA of the single bid auction degrades gracefully with the level of the hierarchy. This hierarchy is a refinement of the Maximum over Positive Hypergraphs (MPH) hierarchy [Feige et al. 2015], where the degree of complementarity d is captured by the maximum number of neighbours of a node in the positive hypergraph representation.We show that the price of anarchy of the single bid auction for valuations of level d of the hierarchy is $O(d^{2}$ log(m/d)), where m is the number of items. We also establish an improved upper bound of O(d log m) for a subclass where every hyperedge in the positive hypergraph representation is of size at most 2 (but the degree is still d). Finally, we show that randomizing between the single bid auction and the grand bundle auction has a price of anarchy of at most O(√m) for general valuations. All of our results are derived via the smoothness framework, thus extend to coarse-correlated equilibria and to Bayes Nash equilibria.
Starting Page	251
Ending Page	267
Page Count	17
File Format	PDF
ISBN	9781450339360
DOI	10.1145/2940716.2940735
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-07-21
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Algorithms Restricted complements Mechanism design Auctions Performance Price of anarchy
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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