NDLI: Dynamic Mechanisms with Martingale Utilities

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

Fair Algorithms for Machine Learning

Dominant-Strategy versus Bayesian Multi-item Auctions: Maximum Revenue Determination and Comparison

The Double Clinching Auction for Wagering

The Stochastic Matching Problem: Beating Half with a Non-Adaptive Algorithm

A "Quantal Regret" Method for Structural Econometrics in Repeated Games

The Scope of Sequential Screening with Ex Post Participation Constraints

Accounting for Strategic Response in an Agent-Based Model of Financial Regulation

Stable Secretaries

Making Right Decisions Based on Wrong Opinions

A Simple and Approximately Optimal Mechanism for a Buyer with Complements: Abstract

Optimal Signaling Mechanisms in Unobservable Queues with Strategic Customers

Combinatorial Cost Sharing

Makespan Minimization via Posted Prices

Convex Program Duality, Fisher Markets, and Nash Social Welfare

Online Auctions and Multi-scale Online Learning

The Tragedy of your Upstairs Neighbors: Is the Negative Externality of Airbnb Internalized?

Truthful Allocation Mechanisms Without Payments: Characterization and Implications on Fairness

Planning with Multiple Biases

Approximating Gains from Trade in Two-sided Markets via Simple Mechanisms

Nash Social Welfare Approximation for Strategic Agents

Graphons: A Nonparametric Method to Model, Estimate, and Design Algorithms for Massive Networks

Stability, Strategy-Proofness, and Cumulative Offer Mechanisms

Simple Approximate Equilibria in Games with Many Players

Deferred-Acceptance Auctions for Multiple Levels of Service

Forecast Aggregation

Facilitating the Search for Partners on Matching Platforms: Restricting Agent Actions

The Theory is Predictive, but is it Complete?: An Application to Human Perception of Randomness

Dynamic Mechanisms with Martingale Utilities

Empirical Mechanism Design for Optimizing Clearing Interval in Frequent Call Markets

Computing Equilibrium in Matching Markets

Voting in the Limelight

Price Doubling and Item Halving: Robust Revenue Guarantees for Item Pricing

Information Sharing and Privacy in Networks

Truth and Regret in Online Scheduling

Controlled Dynamic Fair Division

Joint Pricing and Inventory Management with Strategic Customers

Interacting User Generated Content Technologies: How Q&As Affect Ratings & Reviews

From Monetary to Non-Monetary Mechanism Design via Artificial Currencies

Multidimensional Binary Search for Contextual Decision-Making

Approximately Efficient Two-Sided Combinatorial Auctions

Fair Public Decision Making

Stable Matching with Proportionality Constraints

Theoretical and Practical Advances on Smoothing for Extensive-Form Games

The Optimal Mechanism for Selling to a Budget Constrained Buyer: The General Case

Machine-Learning Aided Peer Prediction

Matching while Learning

Comparison-based Choices

Repeated Sales with Multiple Strategic Buyers

Potential Function Minimizers of Combinatorial Congestion Games: Efficiency and Computation

Communication Requirements and Informative Signaling in Matching Markets

Metric Distortion of Social Choice Rules: Lower Bounds and Fairness Properties

The Competition Complexity of Auctions: A Bulow-Klemperer Result for Multi-Dimensional Bidders

Algorithmic Persuasion with No Externalities

Cost-Sharing Methods for Scheduling Games under Uncertainty

A Lower Bound for Equitable Cake Cutting

Pricing and Optimization in Shared Vehicle Systems: An Approximation Framework

Learning in the Repeated Secretary Problem

Gibbard-Satterthwaite Success Stories and Obvious Strategyproofness

Bifurcation Mechanism Design - from Optimal Flat Taxes to Improved Cancer Treatments

Learning in Repeated Auctions with Budgets: Regret Minimization and Equilibrium

Approximation Algorithms for Maximin Fair Division

Making it Safe to Use Centralized Markets: Epsilon - Dominant Individual Rationality and Applications to Market Design

A Network Game of Dynamic Traffic

Optimal Multi-Unit Mechanisms with Private Demands

Peer Prediction with Heterogeneous Users

Redesigning the Israeli Psychology Master's Match

Combinatorial Auctions Do Need Modest Interaction

Posted Price Mechanisms for a Random Stream of Customers

Surge Pricing Solves the Wild Goose Chase

Complementary Inputs and the Existence of Stable Outcomes in Large Trading Networks

Of the People: Voting Is More Effective with Representative Candidates

Assortment Optimisation under a General Discrete Choice Model: A Tight Analysis of Revenue-Ordered Assortments

Fairness Incentives for Myopic Agents

Multidimensional Dynamic Pricing for Welfare Maximization

Diffusion in Networks and the Unexpected Virtue of Burstiness

How (Not) to Allocate Affordable Housing

A Polynomial Time Algorithm for Spatio-Temporal Security Games

Dynamic Mechanisms with Martingale Utilities

Content Provider	ACM Digital Library
Author	Paes Leme, Renato Balseiro, Santiago Mirrokni, Vahab
Abstract	We study the dynamic mechanism design problem of a seller who repeatedly sells independent items to a buyer with private values. In this setting, the seller could potentially extract the entire buyer surplus by running efficient auctions and charging an upfront participation fee at the beginning of the horizon. In some markets, such as internet advertising, participation fees are not practical since buyers expect to inspect items before purchasing them. This motivates us to study the design of dynamic mechanisms under successively more stringent requirements that capture the implicit business constraints of these markets. We first consider a periodic individual rationality constraint, which limits the mechanism to charge at most the buyer's value in each period. While this prevents large upfront participation fees, the seller can still design mechanisms that spread a participation fee across the first few auctions. These mechanisms have the unappealing feature that they provide close-to-zero buyer utility in earlier auctions in exchange for higher utility in later auctions. To address this problem, we introduce a {martingale utility constraint, which imposes the requirement that from the perspective of the buyer, the next item's expected utility is equal to the present one's. Our main result is providing a dynamic auction satisfying martingale utility and periodic individual rationality whose loss in profit with respect to first-best (full extraction of buyer surplus) is optimal up to polylogarithmic factors. The proposed mechanism is a dynamic two-tier auction with a hard floor and a soft floor that allocates the item whenever the buyer's bid is above the hard floor and charges the minimum of the bid and the soft floor.
Starting Page	165
Ending Page	165
Page Count	1
File Format	PDF
ISBN	9781450345279
DOI	10.1145/3033274.3084089
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2017-06-20
Publisher Place	New York
Access Restriction	Subscribed
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