A Characterization of n-Player Strongly Monotone Scheduling Mechanisms

Kovács, Annamária; Vidali, Angelina

A Characterization of n-Player Strongly Monotone Scheduling Mechanisms

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 568-573.

Abstract

Our work deals with the important problem of globally characterizing truthful mechanisms where players have multi-parameter, additive valuations, like scheduling unrelated machines or additive combinatorial auctions. Very few mechanisms are known for these settings and the question is: Can we prove that no other truthful mechanisms exist? We characterize truthful mechanisms for n players and 2 tasks or items, as either task-independent, or a player-grouping minimizer, a new class of mechanisms we discover, which generalizes affine minimizers. We assume decisiveness, strong monotonicity and that the truthful payments (The (normalized) payments are uniquely determined by the allocation function of the mechanism; thus the assumptions concern properties of the allocation.) are continuous functions of players' bids.

Annamária Kovács, and Angelina Vidali. 2015. A Characterization of n-Player Strongly Monotone Scheduling Mechanisms. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 568–573. https://ijcai.org/proceedings/2015/86

@inproceedings{ijcai2015p86,
  title     = {A Characterization of n-Player Strongly Monotone Scheduling Mechanisms},
  author    = {Kovács, Annamária and Vidali, Angelina},
  booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-15}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Qiang Yang and Michael Wooldridge},
  pages     = {568--573},
  year      = {2015},
  month     = {7},
  note      = {Main Track},
  url       = {https://ijcai.org/proceedings/2015/86},
}

TY  - CPAPER
TI  - A Characterization of n-Player Strongly Monotone Scheduling Mechanisms
AU  - Kovács, Annamária
AU  - Vidali, Angelina
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 568
EP  - 573
UR  - https://ijcai.org/proceedings/2015/86
ER  -