Text

New Constructions of Obviously Strategyproof Mechanisms

Catering to the incentives of people with limited rationality is a challenging research direction that requires novel paradigms to design mechanisms. Obviously strategy-proof (OSP) mechanisms have recently emerged as the concept of interest to this research agenda. However, the majority of the literature in the area has either highlighted the shortcomings of OSP or focused on the “right” definition rather than on the construction of these mechanisms. Here, we give the first set of tight results on the approximation guarantee of OSP mechanisms for scheduling related machines and a characterization of set system instances for which OSP mechanisms that return optimal solutions exist. By extending the well-known cycle monotonicity technique, we are able to concentrate on the algorithmic component of OSP mechanisms and provide some novel paradigms for their design, when private types belong to a set with few values. In essence, we prove that OSP encompasses careful interleaving of ascending and descending auctions.

Ketersediaan

Informasi Detail

Judul Seri

MATHEMATICS OF OPERATIONS RESEARCH; Vol.48 No.1 February 2023

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 332-362

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

MACHINE SCHEDULING
OBVIOUSLY STRATEGY MECHANISMS
SET SYSTEMS
DEFERRED ACCEPTANCE ALGORITHMS
EXTENSIVE FORM MECHANISME

Info Detail Spesifik

https://doi.org/10.1287/moor.2022.1264

Pernyataan Tanggungjawab

Diodato Ferraioli, Adrian Meier, Paolo Penna, Carmine Ventre

Versi lain/terkait

Lampiran Berkas

Komentar