NDLI: Mechanism Design for Subadditive Agents via an Ex Ante Relaxation

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

Mechanism Design for Subadditive Agents via an Ex Ante Relaxation

Content Provider	ACM Digital Library
Author	Miller, J. Benjamin Chawla, Shuchi
Abstract	We consider the problem of maximizing revenue for a monopolist offering multiple items to multiple heterogeneous buyers. We develop a simple mechanism that obtains a constant factor approximation under the assumption that the buyers' values are additive subject to a matroid feasibility constraint and independent across items. Importantly, different buyers in our setting can have different constraints on the sets of items they desire. Our mechanism is a sequential variant of two-part tariffs. Prior to our work, simple approximation mechanisms for such multi-buyer problems were known only for the special cases of all unit-demand or all additive value buyers. Our work expands upon and unifies long lines of work on unit-demand settings and additive settings. We employ the ex ante relaxation approach developed by Alaei [2011] for reducing a multiple-buyer mechanism design problem with an ex post supply constraint into single-buyer problems with ex ante supply constraints. Solving the single-agent problems requires us to significantly extend a decomposition technique developed in the context of additive values Li and Yao [2013] and its extension to subadditive values by [2015].
Starting Page	579
Ending Page	596
Page Count	18
File Format	PDF
ISBN	9781450339360
DOI	10.1145/2940716.2940756
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-07-21
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Approximation Unit-demand values Additive values Multi-parameter mechanism design
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