Efficiency of equilibria in restricted uniform machine scheduling with total weighted completion time as social cost
Why this work is in the frame
A frame that forgets how it found something cannot be audited. These are the routes that admitted this work.
Bibliographic record
Abstract
Abstract In the last decade, there has been much progress in understanding scheduling problems in which selfish jobs aim to minimize their individual completion time. Most of this work has focused on makespan minimization as social objective. In contrast, we consider as social cost the total weighted completion time, that is, the sum of the agent costs, a standard definition of welfare in economics. In our setting, jobs are processed on restricted uniform parallel machines , where each machine has a speed and is only capable of processing a subset of jobs; a job's cost is its weighted completion time; and each machine sequences its jobs in weighted shortest processing time (WSPT) order. Whereas for the makespan social cost the price of anarchy is not bounded by a constant in most environments, we show that for our minsum social objective the price of anarchy is bounded above by a small constant, independent of the instance. Specifically, we show that the price of anarchy is exactly 2 for the class of unit jobs, unit speed instances where the finite processing time values define the edge set of a forest with the machines as nodes. For the general case of mixed job strategies and restricted uniform machines, we prove that the price of anarchy equals 4. From a classical machine scheduling perspective, our results establish the same constant performance guarantees for WSPT list scheduling. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.001 | 0.001 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.000 | 0.000 |
| Bibliometrics | 0.000 | 0.001 |
| Science and technology studies | 0.000 | 0.000 |
| Scholarly communication | 0.000 | 0.000 |
| Open science | 0.000 | 0.000 |
| Research integrity | 0.000 | 0.001 |
| Insufficient payload (model declined to judge) | 0.000 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from it