Acceptable Utility Bounds in Sequencing Problems with Incentives
Authors: Sreoshi Banerjee, Parikshit De, Manipushpak Mitra
Abstract: In a sequencing environment with incomplete information, we study the impact of imposing a lower bound on the utility function of agents. We call this the “acceptable utility bound”. Such a bound guarantees a minimum acceptable utility to every agent and acts as a veil of protection. Our primary motive is to identify the class of outcome efficient and strategy-proof mechanisms which satisfy the “acceptable utility bound”. We identify a necessary and sufficient condition to obtain such a class of mechanisms. This is followed by our characterization result where the set of mechanisms satisfying outcome efficiency, strategy-proofness and the acceptable utility bound are termed as “relative pivotal mechanisms”. The paper also provides relevant theoretical applications involving specific lower bounds namely; bounds with initial order, identical cost bounds and expected cost bounds. We also offer insights on the issue of feasibility and/or budget balance.