Sreoshi Banerjee (QSMS Research Group, BME) will be presenting her paper “GENERALIZED WELFARE LOWER BOUNDS AND STRATEGYPROOFNESS IN
SEQUENCING PROBLEMS “ on October 25th at 10 AM, room QA405. One-to-one meetings with the speaker can be arranged; please contact the seminar organizers, Dr. Noémie Cabau (firstname.lastname@example.org) and Dr. Arseniy Samsonov (email@example.com).
Abstract: In an environment with private information, we study the class of sequencing problems with welfare lower bounds. The ‘generalized welfare lower bound’ is a universal representation of some of the specific lower bounds that have been previously studied in the literature. Every agent is offered protection in the form of a minimum guarantee on their utilities. We provide a necessary and sufficient condition to identify an outcome-efficient and strategyproof mechanism that satisfies the generalized welfare lower bound. We then characterize the entire class of mechanisms that satisfy outcome efficiency, strategyproofness, and generalized welfare lower bound. These are termed as ‘relative pivotal mechanisms’. Our paper proposes relevant theoretical applications namely; ex-ante initial order, identical costs bound and expected cost bound. We also give insights on the issues of feasibility and/or budget balance.