NDLI: Ignorance is Almost Bliss: Near-Optimal Stochastic Matching With Few Queries

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

Econometrics for Learning Agents

Hidden Substitutes

Decentralized Dynamics and Fast Convergence in the Assignment Game: Extended Abstract

Online Reputation Management: Estimating the Impact of Management Responses on Consumer Reviews

Near-Optimum Online Ad Allocation for Targeted Advertising

Algorithms as Mechanisms: The Price of Anarchy of Relax-and-Round

A Non-asymptotic Approach to Analyzing Kidney Exchange Graphs

Designing Dynamic Contests

Information Asymmetries in Common-Value Auctions with Discrete Signals

Ignorance is Almost Bliss: Near-Optimal Stochastic Matching With Few Queries

Competitive Analysis via Benchmark Decomposition

Improved Efficiency Guarantees in Auctions with Budgets

Customer Referral Incentives and Social Media

At What Quality and What Price?: Eliciting Buyer Preferences as a Market Design Problem

Mechanisms for Fair Attribution

Integrating Market Makers, Limit Orders, and Continuous Trade in Prediction Markets

The Impact of the Sharing Economy on the Hotel Industry: Evidence from Airbnb's Entry Into the Texas Market

The Wisdom of Multiple Guesses

Dynamic Fair Division with Minimal Disruptions

Short Lists in Centralized Clearinghouses

Reverse Mechanism Design

Combining Traditional Marketing and Viral Marketing with Amphibious Influence Maximization

Finding Any Nontrivial Coarse Correlated Equilibrium Is Hard

Why Prices Need Algorithms

Full Substitutability in Trading Networks

Making the Most of Your Samples

Canary in the e-Commerce Coal Mine: Detecting and Predicting Poor Experiences Using Buyer-to-Seller Messages

Core-competitive Auctions

Smooth Online Mechanisms: A Game-Theoretic Problem in Renewable Energy Markets

Designing Matching Mechanisms under General Distributional Constraints

Managing Innovation in a Crowd

Simple Auctions with Simple Strategies

Matching with Stochastic Arrival

Simple Mechanisms for a Subadditive Buyer and Applications to Revenue Monotonicity

Truthful Mechanism Design via Correlated Tree Rounding

Estimating the Causal Impact of Recommendation Systems from Observational Data

Procurement Mechanisms for Differentiated Products

Sound Auction Specification and Implementation

Learning What's Going on: Reconstructing Preferences and Priorities from Opaque Transactions

Pricing in Ride-Sharing Platforms: A Queueing-Theoretic Approach

Generalized Decision Scoring Rules: Statistical, Computational, and Axiomatic Properties

Truthful Online Scheduling with Commitments

Redesigning the Israeli Medical Internship Match

Price Competition, Fluctuations and Welfare Guarantees

Approximability of Adaptive Seeding under Knapsack Constraints

Faster First-Order Methods for Extensive-Form Game Solving

Near Feasible Stable Matchings

Commitment Without Regrets: Online Learning in Stackelberg Security Games

Coalition Games on Interaction Graphs: A Horticultural Perspective

Adverse Selection and Auction Design for Internet Display Advertising

Greedy Algorithms Make Efficient Mechanisms

Private Pareto Optimal Exchange

Incentive-Compatible Experimental Design

Randomization Beats Second Price as a Prior-Independent Auction

Leximin Allocations in the Real World

Public Projects, Boolean Functions, and the Borders of Border's Theorem

Revenue Maximization and Ex-Post Budget Constraints

Inducing Approximately Optimal Flow Using Truthful Mediators

Team Performance with Test Scores

Bayesian Incentive-Compatible Bandit Exploration

Low-Cost Learning via Active Data Procurement

Bias and Reciprocity in Online Reviews: Evidence From Field Experiments on Airbnb

Behavioral Mechanism Design: Optimal Crowdsourcing Contracts and Prospect Theory

Markets with Production: A Polynomial Time Algorithm and a Reduction to Pure Exchange

Assigning More Students to their Top Choices: A Tiebreaking Rule Comparison

Robust Dynamic Pricing With Strategic Customers

Bidding Games and Efficient Allocations

Online Allocation with Traffic Spikes: Mixing Adversarial and Stochastic Models

Algorithms against Anarchy: Understanding Non-Truthful Mechanisms

An Approximate Law of One Price in Random Assignment Games

Strong Duality for a Multiple-Good Monopolist

The Burden of Risk Aversion in Mean-Risk Selfish Routing

Ignorance is Almost Bliss: Near-Optimal Stochastic Matching With Few Queries

Content Provider	ACM Digital Library
Author	Haghtalab, Nika Sharma, Ankit Blum, Avrim Dickerson, John P. Procaccia, Ariel D. Sandholm, Tuomas
Abstract	The stochastic matching problem deals with finding a maximum matching in a graph whose edges are unknown but can be accessed via queries. This is a special case of stochastic k-set packing, where the problem is to find a maximum packing of sets, each of which exists with some probability. In this paper, we provide edge and set query algorithms for these two problems, respectively, that provably achieve some fraction of the omniscient optimal solution. Our main theoretical result for the stochastic matching (i.e., 2-set packing) problem is the design of an adaptive algorithm that queries only a constant number of edges per vertex and achieves a (1-ε) fraction of the omniscient optimal solution, for an arbitrarily small ε > 0. Moreover, this adaptive algorithm performs the queries in only a constant number of rounds. We complement this result with a non-adaptive (i.e., one round of queries) algorithm that achieves a (0.5 - ε) fraction of the omniscient optimum. We also extend both our results to stochastic k-set packing by designing an adaptive algorithm that achieves a (2/k - ε) fraction of the omniscient optimal solution, again with only O(1) queries per element. This guarantee is close to the best known polynomial-time approximation ratio of 3/k+1 -ε for the deterministic k-set packing problem [Furer 2013]. We empirically explore the application of (adaptations of) these algorithms to the kidney exchange problem, where patients with end-stage renal failure swap willing but incompatible donors. We show on both generated data and on real data from the first 169 match runs of the UNOS nationwide kidney exchange that even a very small number of non-adaptive edge queries per vertex results in large gains in expected successful matches.
Starting Page	325
Ending Page	342
Page Count	18
File Format	PDF
ISBN	9781450334105
DOI	10.1145/2764468.2764479
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2015-06-15
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Economics Stochastic matching Algorithms Stochastic k-set packing Experimentation Kidney exchange
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