Obviously Strategyproof Mechanisms without Money for Scheduling

Maria Kyropoulou; Carmine Ventre

doi:10.1137/23M1563578

Obviously Strategyproof Mechanisms without Money for Scheduling

Maria Kyropoulou, Carmine Ventre

University of Essex

Research output: Contribution to journal › Article › peer-review

76 Downloads (Pure)

Abstract

We consider the scheduling problem when no payments are allowed and the machines are bound by their declarations. We are interested in a notion of incentive compatibility, stronger than the (standard) strategy-proofness, termed obviously strategy-proof (OSP), and explore its possibilities and limitations. OSP formalizes the concept of strategy-proofness for agents/machines with a certain kind of bounded rationality by making an agent's incentives to act truthfully obvious in some sense: roughly speaking, the worst possible outcome after providing information about her true type is at least as good as the best possible outcome after misreporting information about her type. Under the weaker constraint of strategyroofness, Koutsoupias [Theoret. Comput. Syst., 54 (2014), pp. 375-387 proves a tight approximation ratio of (Formula presented) for the makespan for one task, under the monitoring paradigm. We wish to examine how this guarantee is affected by the strengthening of the incentive compatibility constraint. The main message of our work is that there is essentially no worsening of the approximation guarantee corresponding to the significant strengthening of the guarantee of incentive compatibility from strategy-proofness to OSP, as long as the mechanism designer can implement a particular notion of monitoring. To achieve this, we introduce the notion of max-monitoring and prove that weaker monitoring frameworks do not suffice, thus providing a complete picture of OSP with monitoring in the context of scheduling a task without money.

Original language	English
Pages (from-to)	1102-1122
Number of pages	21
Journal	SIAM JOURNAL ON DISCRETE MATHEMATICS
Volume	39
Issue number	2
DOIs	https://doi.org/10.1137/23M1563578
Publication status	Published - 9 May 2025

Access to Document

10.1137/23M1563578

OSPscheduling-R2-SIDMAAccepted author manuscript, 366 KB

Cite this

@article{4759c3bea24c40399edc11134ac37e02,

title = "Obviously Strategyproof Mechanisms without Money for Scheduling",

abstract = "We consider the scheduling problem when no payments are allowed and the machines are bound by their declarations. We are interested in a notion of incentive compatibility, stronger than the (standard) strategy-proofness, termed obviously strategy-proof (OSP), and explore its possibilities and limitations. OSP formalizes the concept of strategy-proofness for agents/machines with a certain kind of bounded rationality by making an agent's incentives to act truthfully obvious in some sense: roughly speaking, the worst possible outcome after providing information about her true type is at least as good as the best possible outcome after misreporting information about her type. Under the weaker constraint of strategyroofness, Koutsoupias [Theoret. Comput. Syst., 54 (2014), pp. 375-387 proves a tight approximation ratio of (Formula presented) for the makespan for one task, under the monitoring paradigm. We wish to examine how this guarantee is affected by the strengthening of the incentive compatibility constraint. The main message of our work is that there is essentially no worsening of the approximation guarantee corresponding to the significant strengthening of the guarantee of incentive compatibility from strategy-proofness to OSP, as long as the mechanism designer can implement a particular notion of monitoring. To achieve this, we introduce the notion of max-monitoring and prove that weaker monitoring frameworks do not suffice, thus providing a complete picture of OSP with monitoring in the context of scheduling a task without money.",

author = "Maria Kyropoulou and Carmine Ventre",

note = "Publisher Copyright: {\textcopyright} 2025 Society for Industrial and Applied Mathematics.",

year = "2025",

month = may,

day = "9",

doi = "10.1137/23M1563578",

language = "English",

volume = "39",

pages = "1102--1122",

journal = "SIAM JOURNAL ON DISCRETE MATHEMATICS",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "2",

}

TY - JOUR

T1 - Obviously Strategyproof Mechanisms without Money for Scheduling

AU - Kyropoulou, Maria

AU - Ventre, Carmine

PY - 2025/5/9

Y1 - 2025/5/9

N2 - We consider the scheduling problem when no payments are allowed and the machines are bound by their declarations. We are interested in a notion of incentive compatibility, stronger than the (standard) strategy-proofness, termed obviously strategy-proof (OSP), and explore its possibilities and limitations. OSP formalizes the concept of strategy-proofness for agents/machines with a certain kind of bounded rationality by making an agent's incentives to act truthfully obvious in some sense: roughly speaking, the worst possible outcome after providing information about her true type is at least as good as the best possible outcome after misreporting information about her type. Under the weaker constraint of strategyroofness, Koutsoupias [Theoret. Comput. Syst., 54 (2014), pp. 375-387 proves a tight approximation ratio of (Formula presented) for the makespan for one task, under the monitoring paradigm. We wish to examine how this guarantee is affected by the strengthening of the incentive compatibility constraint. The main message of our work is that there is essentially no worsening of the approximation guarantee corresponding to the significant strengthening of the guarantee of incentive compatibility from strategy-proofness to OSP, as long as the mechanism designer can implement a particular notion of monitoring. To achieve this, we introduce the notion of max-monitoring and prove that weaker monitoring frameworks do not suffice, thus providing a complete picture of OSP with monitoring in the context of scheduling a task without money.

AB - We consider the scheduling problem when no payments are allowed and the machines are bound by their declarations. We are interested in a notion of incentive compatibility, stronger than the (standard) strategy-proofness, termed obviously strategy-proof (OSP), and explore its possibilities and limitations. OSP formalizes the concept of strategy-proofness for agents/machines with a certain kind of bounded rationality by making an agent's incentives to act truthfully obvious in some sense: roughly speaking, the worst possible outcome after providing information about her true type is at least as good as the best possible outcome after misreporting information about her type. Under the weaker constraint of strategyroofness, Koutsoupias [Theoret. Comput. Syst., 54 (2014), pp. 375-387 proves a tight approximation ratio of (Formula presented) for the makespan for one task, under the monitoring paradigm. We wish to examine how this guarantee is affected by the strengthening of the incentive compatibility constraint. The main message of our work is that there is essentially no worsening of the approximation guarantee corresponding to the significant strengthening of the guarantee of incentive compatibility from strategy-proofness to OSP, as long as the mechanism designer can implement a particular notion of monitoring. To achieve this, we introduce the notion of max-monitoring and prove that weaker monitoring frameworks do not suffice, thus providing a complete picture of OSP with monitoring in the context of scheduling a task without money.

UR - http://www.scopus.com/inward/record.url?scp=105006533218&partnerID=8YFLogxK

U2 - 10.1137/23M1563578

DO - 10.1137/23M1563578

M3 - Article

SN - 0895-4801

VL - 39

SP - 1102

EP - 1122

JO - SIAM JOURNAL ON DISCRETE MATHEMATICS

JF - SIAM JOURNAL ON DISCRETE MATHEMATICS

IS - 2

ER -

Obviously Strategyproof Mechanisms without Money for Scheduling

Abstract

Access to Document

Other files and links

Fingerprint

Cite this