NDLI: Truthful Online Scheduling with Commitments

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

Truthful Online Scheduling with Commitments

Content Provider	ACM Digital Library
Author	Lucier, Brendan Azar, Yossi Naor, Joseph Seffi Kalp-Shaltiel, Inna Menache, Ishai Yaniv, Jonathan
Abstract	We study online mechanisms for preemptive scheduling with deadlines, with the goal of maximizing the total value of completed jobs. This problem is fundamental to deadline-aware cloud scheduling, but there are strong lower bounds even for the algorithmic problem without incentive constraints. However, these lower bounds can be circumvented under the natural assumption of deadline slackness, i.e., that there is a guaranteed lower bound s > 1 on the ratio between a job's size and the time window in which it can be executed. In this paper, we construct a truthful scheduling mechanism with a constant competitive ratio, given slackness s > 1. Furthermore, we show that if s is large enough then we can construct a mechanism that also satisfies a commitment property: it can be determined whether or not a job will finish, and the requisite payment if so, well in advance of each job's deadline. This is notable because, in practice, users with strict deadlines may find it unacceptable to discover only very close to their deadline that their job has been rejected.
Starting Page	715
Ending Page	732
Page Count	18
File Format	PDF
ISBN	9781450334105
DOI	10.1145/2764468.2764535
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2015-06-15
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Scheduling algorithms Truthful mechanisms Mechanism design Online scheduling Deadline scheduling Committed scheduling
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