On the capacity of information processing systems
From MaRDI portal
Publication:4969342
DOI10.1287/OPRE.2017.1680zbMATH Open1442.90052OpenAlexW2963787128MaRDI 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
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
- On the power of (even a little) resource pooling
- 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 (7)
- On the Capacity of the Precision-Resolution System
- Reinforcement with fading memories
- Information and memory in dynamic resource allocation
- Crowdvoting judgment: an analysis of modern peer review
- Hierarchies of processors with endogenous capacity
- Matching while learning
- Information processing for a finite resource allocation mechanism
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)
