When Does Schwartz Conjecture Hold?

Mnich, Matthias; Shrestha, Yash Raj; Yang, Yongjie

When Does Schwartz Conjecture Hold?

Matthias Mnich, Yash Raj Shrestha, Yongjie Yang

Download BibTeX Cite

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

Abstract

In 1990, Thomas Schwartz proposed the conjecture that every nonempty tournament has a unique minimal TEQ-retentive set (TEQ stands for tournament equilibrium set). A weak variant of Schwartz's Conjecture was recently proposed by Felix Brandt. However, both conjectures were disproved very recently by two counterexamples. In this paper, we prove sufficient conditions for infinite classes of tournaments that satisfy Schwartz's Conjecture and Brandt's Conjecture. Moreover, we prove that TEQ can be calculated in polynomial time in several infinite classes of tournaments. Furthermore, our results reveal some structures that are forbidden in every counterexample to Schwartz's Conjecture.

Matthias Mnich, Yash Raj Shrestha, and Yongjie Yang. 2015. When Does Schwartz Conjecture Hold?. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 603–608. https://ijcai.org/proceedings/2015/91

@inproceedings{ijcai2015p91,
  title     = {When Does Schwartz Conjecture Hold?},
  author    = {Mnich, Matthias and Shrestha, Yash Raj and Yang, Yongjie},
  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     = {603--608},
  year      = {2015},
  month     = {7},
  note      = {Main Track},
  url       = {https://ijcai.org/proceedings/2015/91},
}

TY  - CPAPER
TI  - When Does Schwartz Conjecture Hold?
AU  - Mnich, Matthias
AU  - Shrestha, Yash Raj
AU  - Yang, Yongjie
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 603
EP  - 608
UR  - https://ijcai.org/proceedings/2015/91
ER  -