On the capacity of information processing systems

DOI10.1287/OPRE.2017.1680zbMATH Open1442.90052arXiv1603.00544OpenAlexW2963787128MaRDI QIDQ4969342FDOQ4969342

Authors: Laurent Massoulié, Kuang Xu 

Publication date: 5 October 2020

Published in: Operations Research (Search for Journal in Brave)

Abstract: We propose and analyze a family of information processing systems, where a finite set of experts or servers are employed to extract information about a stream of incoming jobs. Each job is associated with a hidden label drawn from some prior distribution. An inspection by an expert produces a noisy outcome that depends both on the job's hidden label and the type of the expert, and occupies the expert for a finite time duration. A decision maker's task is to dynamically assign inspections so that the resulting outcomes can be used to accurately recover the labels of all jobs, while keeping the system stable. Among our chief motivations are applications in crowd-sourcing, diagnostics, and experiment designs, where one wishes to efficiently learn the nature of a large number of items, using a finite pool of computational resources or human agents. We focus on the capacity of such an information processing system. Given a level of accuracy guarantee, we ask how many experts are needed in order to stabilize the system, and through what inspection architecture. Our main result provides an adaptive inspection policy that is asymptotically optimal in the following sense: the ratio between the required number of experts under our policy and the theoretical optimal converges to one, as the probability of error in label recovery tends to zero.

Full work available at URL: https://arxiv.org/abs/1603.00544

Recommendations

• Budget-Optimal Task Allocation for Reliable Crowdsourcing Systems
• Information and memory in dynamic resource allocation
• Efficient crowdsourcing of unknown experts using bounded multi-armed bandits
• Efficient crowdsourcing of unknown experts using multi-armed bandits
• Adaptive matching for expert systems with uncertain task types

zbMATH Keywords

hypothesis testingfluid modelstochastic resource allocationinformation processing system

Mathematics Subject Classification ID

Management decision making, including multiple objectives (90B50) Queues and service in operations research (90B22) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Cites Work

• Sequential Tests of Statistical Hypotheses
• On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid limit models
• Title not available (Why is that?)
• Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks
• Structural properties of proportional fairness: stability and insensitivity
• Ergodicity of stochastic processes describing the operation of open queueing networks
• Heavy traffic resource pooling in parallel-server systems
• Flexible Queueing Architectures
• Title not available (Why is that?)
• State space collapse with application to heavy traffic limits for multiclass queueing networks
• Sequential Design of Experiments
• Investment Timing with Incomplete Information and Multiple Means of Learning
• Fluid Models for Overloaded Multiclass Many-Server Queueing Systems with First-Come, First-Served Routing
• Budget-Optimal Task Allocation for Reliable Crowdsourcing Systems

Cited In (6)

• Crowdvoting Judgment: An Analysis of Modern Peer Review
• Matching While Learning
• On the Capacity of the Precision-Resolution System
• Hierarchies of processors with endogenous capacity
• Information processing for a finite resource allocation mechanism
• Reinforcement with Fading Memories

This page was built for publication: On the capacity of information processing systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4969342)