* Dai and Huang (2018) Dai, Zeyu and Ruihong Huang. 2018.  Improving implicit discourse relation classification by modeling inter-dependencies of discourse units in a paragraph.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 141–151, Association for Computational Linguistics, New Orleans, Louisiana.
  * Das and Taboada (2014) Das, Debopam and Maite Taboada. 2014.  RST Signalling Corpus Annotation Manual.  Unpublished manuscript.
  * Das and Taboada (2017) Das, Debopam and Maite Taboada. 2017.  Signalling of coherence relations in discourse, beyond discourse markers.  _Discourse Processes_ , 55(8):743–770.
  * Das and Taboada (2018) Das, Debopam and Maite Taboada. 2018.  RST Signalling Corpus: a corpus of signals of coherence relations.  _Language Resources and Evaluation_ , 52(1):149–184.
  * Demberg, Asr, and Scholman (2019) Demberg, Vera, Fatemeh Torabi Asr, and Merel Scholman. 2019.  How compatible are our discourse annotation frameworks? insights from mapping RST-DT and PDTB annotations.  _Dialogue & Discourse_, 10(1):87–135.
  * Feng and Hirst (2014) Feng, Vanessa Wei and Graeme Hirst. 2014.  A linear-time bottom-up discourse parser with constraints and post-editing.  In _Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 511–521, Association for Computational Linguistics, Baltimore, Maryland.
  * Gessler et al. (2021) Gessler, Luke, Shabnam Behzad, Yang Janet Liu, Siyao Peng, Yilun Zhu, and Amir Zeldes. 2021.  DisCoDisCo at the DISRPT2021 shared task: A system for discourse segmentation, classification, and connective detection.  In _Proceedings of Discourse Relation Parsing and Treebanking 2021 (DISRPT 2021)_ , pages 51–62, Punta Cana, Dominican Republic.
  * Gessler, Liu, and Zeldes (2019) Gessler, Luke, Yang Liu, and Amir Zeldes. 2019.  A discourse signal annotation system for RST trees.  In _Proceedings of Discourse Relation Treebanking and Parsing (DISRPT 2019)_ , pages 56–61, Minneapolis, MN.
  * Gessler et al. (2020) Gessler, Luke, Siyao Peng, Yang Liu, Yilun Zhu, Shabnam Behzad, and Amir Zeldes. 2020.  AMALGUM – a free, balanced, multilayer English web corpus.  In _Proceedings of the Twelfth Language Resources and Evaluation Conference_ , pages 5267–5275, European Language Resources Association, Marseille, France.
  * Guz and Carenini (2020) Guz, Grigorii and Giuseppe Carenini. 2020.  Coreference for discourse parsing: A neural approach.  In _Proceedings of the First Workshop on Computational Approaches to Discourse_ , pages 160–167, Association for Computational Linguistics, Online.
  * Guz, Huber, and Carenini (2020) Guz, Grigorii, Patrick Huber, and Giuseppe Carenini. 2020.  Unleashing the power of neural discourse parsers - a context and structure aware approach using large scale pretraining.  In _Proceedings of the 28th International Conference on Computational Linguistics_ , pages 3794–3805, International Committee on Computational Linguistics, Barcelona, Spain (Online).
  * Hernault et al. (2010) Hernault, Hugo, Helmut Prendinger, David A. duVerle, and Mitsuru Ishizuka. 2010.  HILDA: A discourse parser using support vector machine classification.  _Dialogue and Discourse_ , 1(3):1–33.
  * Hirao et al. (2013) Hirao, Tsutomu, Yasuhisa Yoshida, Masaaki Nishino, Norihito Yasuda, and Masaaki Nagata. 2013.  Single-document summarization as a tree knapsack problem.  In _Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing_ , pages 1515–1520, Association for Computational Linguistics, Seattle, Washington, USA.
  * Hoek, Evers-Vermeul, and Sanders (2019) Hoek, Jet, Jacqueline Evers-Vermeul, and Ted J.M. Sanders. 2019.  Using the Cognitive approach to Coherence Relations for discourse annotation.  _Dialogue and Discourse_ , 10(2):1–33.
  * Hovy (1990) Hovy, Eduard H. 1990.  Parsimonious and profligate approaches to the question of discourse structure relations.  In _Proceedings of the Fifth International Workshop on Natural Language Generation_ , Association for Computational Linguistics, Linden Hall Conference Center, Dawson, Pennsylvania.
  * Hughes (1996) Hughes, Rebecca. 1996.  _English in Speech and Writing_.  Routledge, London.
  * Jurafsky and Martin (2023) Jurafsky, Daniel and James H. Martin. 2023.  _Speech and Language Processing. An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition_ , 3rd edition edition.  Online, Upper Saddle River, NJ.
  * Kamp, Van Genabith, and Reyle (2011) Kamp, Hans, Josef Van Genabith, and Uwe Reyle. 2011.  Discourse representation theory.  _Handbook of Philosophical Logic: Volume 15_ , pages 125–394.
  * Kim et al. (2020) Kim, Najoung, Song Feng, Chulaka Gunasekara, and Luis Lastras. 2020.  Implicit discourse relation classification: We need to talk about evaluation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 5404–5414, Association for Computational Linguistics, Online.
  * Kleijn, Pander Maat, and Sanders (2019) Kleijn, Suzanne, Henk L.W. Pander Maat, and Ted J.M. Sanders. 2019.  Comprehension Effects of Connectives Across Texts, Readers, and Coherence Relations.  _Discourse Processes_ , 56(5-6):447–464.
  * Knaebel (2021) Knaebel, René. 2021.  discopy: A neural system for shallow discourse parsing.  In _Proceedings of the 2nd Workshop on Computational Approaches to Discourse_ , pages 128–133, Association for Computational Linguistics, Punta Cana, Dominican Republic and Online.
  * Kobayashi et al. (2020) Kobayashi, Naoki, Tsutomu Hirao, Hidetaka Kamigaito, Manabu Okumura, and Masaaki Nagata. 2020.  Top-Down RST Parsing Utilizing Granularity Levels in Documents.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 34(05):8099–8106.
  * Kobayashi et al. (2022) Kobayashi, Naoki, Tsutomu Hirao, Hidetaka Kamigaito, Manabu Okumura, and Masaaki Nagata. 2022.  A simple and strong baseline for end-to-end neural RST-style discourse parsing.  In _Findings of the Association for Computational Linguistics: EMNLP 2022_ , pages 6725–6737, Association for Computational Linguistics, Abu Dhabi, United Arab Emirates.
  * Krause, Leser, and Lüdeling (2016) Krause, Thomas, Ulf Leser, and Anke Lüdeling. 2016.  graphANNIS: A fast query engine for deeply annotated linguistic corpora.  _Journal for Language Technology and Computational Linguistics_ , 31(1):1–25.
  * Krause and Zeldes (2016) Krause, Thomas and Amir Zeldes. 2016.  ANNIS3: A new architecture for generic corpus query and visualization.  _Digital Scholarship in the Humanities_ , 31(1):118–139.
  * Kurfalı and Östling (2021) Kurfalı, Murathan and Robert Östling. 2021.  Probing multilingual language models for discourse.  In _Proceedings of the 6th Workshop on Representation Learning for NLP (RepL4NLP-2021)_ , pages 8–19, Association for Computational Linguistics, Online.
  * Lascarides and Asher (2007) Lascarides, Alex and Nicholas Asher. 2007.  Segmented Discourse Representation Theory: Dynamic semantics with discourse structure.  In _Computing Meaning_ , Studies in Linguistics and Philosophy 3. Springer, Dordrecht, pages 87–124.
  * Li et al. (2020) Li, Jiaqi, Ming Liu, Min-Yen Kan, Zihao Zheng, Zekun Wang, Wenqiang Lei, Ting Liu, and Bing Qin. 2020.  Molweni: A challenge multiparty dialogues-based machine reading comprehension dataset with discourse structure.  In _Proceedings of the 28th International Conference on Computational Linguistics_ , pages 2642–2652, International Committee on Computational Linguistics, Barcelona, Spain (Online).
  * Li et al. (2014) Li, Sujian, Liang Wang, Ziqiang Cao, and Wenjie Li. 2014.  Text-level discourse dependency parsing.  In _Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 25–35, Association for Computational Linguistics, Baltimore, Maryland.
  * Liu, Fan, and Strube (2023) Liu, Wei, Yi Fan, and Michael Strube. 2023.  HITS at DISRPT 2023: Discourse segmentation, connective detection, and relation classification.  In _Proceedings of the 3rd Shared Task on Discourse Relation Parsing and Treebanking (DISRPT 2023)_ , pages 43–49, The Association for Computational Linguistics, Toronto, Canada.
  * Liu (2019) Liu, Yang. 2019.  Beyond the Wall Street Journal: Anchoring and comparing discourse signals across genres.  In _Proceedings of the Workshop on Discourse Relation Parsing and Treebanking 2019_ , pages 72–81, Association for Computational Linguistics, Minneapolis, MN.
  * Liu and Zeldes (2019) Liu, Yang and Amir Zeldes. 2019.  Discourse relations and signaling information: Anchoring discourse signals in RST-DT.  _Proceedings of the Society for Computation in Linguistics_ , 2(35):314–317.
  * Liu, Aoyama, and Zeldes (2023) Liu, Yang Janet, Tatsuya Aoyama, and Amir Zeldes. 2023.  What’s hard in English RST parsing? predictive models for error analysis.  In _Proceedings of the 24th Meeting of the Special Interest Group on Discourse and Dialogue_ , pages 31–42, Association for Computational Linguistics, Prague, Czechia.
  * Liu, Shi, and Chen (2021) Liu, Zhengyuan, Ke Shi, and Nancy Chen. 2021.  DMRST: A joint framework for document-level multilingual RST discourse segmentation and parsing.  In _Proceedings of the 2nd Workshop on Computational Approaches to Discourse_ , pages 154–164, Association for Computational Linguistics, Punta Cana, Dominican Republic and Online.
  * Mann and Thompson (1988) Mann, William C. and Sandra A. Thompson. 1988.  Rhetorical Structure Theory: Toward a functional theory of text organization.  _Text_ , 8(3):243–281.
  * Marcu (1997) Marcu, Daniel. 1997.  _The Rhetorical Parsing, Summarization, and Generation of Natural Language Texts_.  Phd thesis, University of Toronto.
  * Marcus, Santorini, and Marcinkiewicz (1993) Marcus, Mitchell P., Beatrice Santorini, and Mary Ann Marcinkiewicz. 1993.  Building a large annotated corpus of English: The Penn Treebank.  _Special Issue on Using Large Corpora, Computational Linguistics_ , 19(2):313–330.
  * de Marneffe et al. (2021) de Marneffe, Marie-Catherine, Christopher D. Manning, Joakim Nivre, and Daniel Zeman. 2021.  Universal Dependencies.  _Computational Linguistics_ , 47(2):255–308.
  * Mendes and Lejeune (2022) Mendes, Amália and Pierre Lejeune. 2022.  Crpc-db a discourse bank for portuguese.  In _Computational Processing of the Portuguese Language: 15th International Conference, PROPOR 2022, Fortaleza, Brazil, March 21–23, 2022, Proceedings_ , page 79–89, Springer-Verlag, Berlin, Heidelberg.
  * Metheniti et al. (2023) Metheniti, Eleni, Chloé Braud, Philippe Muller, and Laura Rivière. 2023.  DisCut and DiscReT: MELODI at DISRPT 2023.  In _Proceedings of the 3rd Shared Task on Discourse Relation Parsing and Treebanking (DISRPT 2023)_ , pages 29–42, The Association for Computational Linguistics, Toronto, Canada.
  * Mikulová et al. (2022) Mikulová, Marie, Milan Straka, Jan Štěpánek, Barbora Štěpánková, and Jan Hajic. 2022.  Quality and efficiency of manual annotation: Pre-annotation bias.  In _Proceedings of the Language Resources and Evaluation Conference_ , pages 2909–2918, European Language Resources Association, Marseille, France.
  * Moore and Paris (1993) Moore, Johanna D. and Cecile L. Paris. 1993.  Planning text for advisory dialogues: Capturing intentional and rhetorical information.  _Computational Linguistics_ , 19(4):651–694.
  * Moore and Pollack (1992) Moore, Johanna D. and Martha E. Pollack. 1992.  A problem for RST: The need for multi-level discourse analysis.  _Computational Linguistics_ , 18(4):537–544.
  * Morey, Muller, and Asher (2017) Morey, Mathieu, Philippe Muller, and Nicholas Asher. 2017.  How much progress have we made on RST discourse parsing? a replication study of recent results on the RST-DT.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 1319–1324, Association for Computational Linguistics, Copenhagen, Denmark.
  * Morey, Muller, and Asher (2018) Morey, Mathieu, Philippe Muller, and Nicholas Asher. 2018.  A dependency perspective on RST discourse parsing and evaluation.  _Computational Linguistics_ , 44(2):197–235.
  * Nishida and Matsumoto (2022) Nishida, Noriki and Yuji Matsumoto. 2022.  Out-of-domain discourse dependency parsing via bootstrapping: An empirical analysis on its effectiveness and limitation.  _Transactions of the Association for Computational Linguistics_ , 10:127–144.
  * Nivre et al. (2020) Nivre, Joakim, Marie-Catherine de Marneffe, Filip Ginter, Jan Hajič, Christopher D. Manning, Sampo Pyysalo, Sebastian Schuster, Francis Tyers, and Daniel Zeman. 2020.  Universal Dependencies v2: An evergrowing multilingual treebank collection.  In _Proceedings of the Twelfth Language Resources and Evaluation Conference_ , pages 4034–4043, European Language Resources Association, Marseille, France.
  * Peng (2023) Peng, Siyao. 2023.  _Cross-Paragraph Discourse Structure in Rhetorical Structure Theory Parsing and Treebanking for Chinese and English._ Ph.D. thesis, Georgetown University.
  * Peng, Liu, and Zeldes (2022) Peng, Siyao, Yang Janet Liu, and Amir Zeldes. 2022.  GCDT: A Chinese RST treebank for multigenre and multilingual discourse parsing.  In _Proceedings of the 2nd Conference of the Asia-Pacific Chapter of the Association for Computational Linguistics and the 12th International Joint Conference on Natural Language Processing (Volume 2: Short Papers)_ , pages 382–391, Association for Computational Linguistics, Online only.
  * Porter (2001) Porter, Martin F. 2001.  Snowball: A language for stemming algorithms.  Online.
  * Potter (2019) Potter, Andrew. 2019.  The rhetorical structure of attribution.  In _Proceedings of the Workshop on Discourse Relation Parsing and Treebanking 2019_ , pages 38–49, Association for Computational Linguistics, Minneapolis, MN.
  * Prasad et al. (2006) Prasad, Rashmi, Eleni Miltsakaki, Nikhil Dinesh, Alan Lee, Aravind Joshi, and Bonnie Webber. 2006.  The Penn Discourse TreeBank 1.0 annotation manual.  Technical report, University of Pennsylvania, PDTB Research Group.
  * Prasad, Webber, and Joshi (2014) Prasad, Rashmi, Bonnie Webber, and Aravind Joshi. 2014.  Reflections on the Penn Discourse TreeBank, comparable corpora, and complementary annotation.  _Computational Linguistics_ , 40(4):921–950.
  * Qin et al. (2017) Qin, Lianhui, Zhisong Zhang, Hai Zhao, Zhiting Hu, and Eric Xing. 2017.  Adversarial connective-exploiting networks for implicit discourse relation classification.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1006–1017, Association for Computational Linguistics, Vancouver, Canada.
  * Rehbein, Scholman, and Demberg (2016) Rehbein, Ines, Merel Scholman, and Vera Demberg. 2016.  Annotating discourse relations in spoken language: A comparison of the PDTB and CCR frameworks.  In _Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC’16)_ , pages 1039–1046, European Language Resources Association (ELRA), Portorož, Slovenia.
  * Rutherford, Demberg, and Xue (2017) Rutherford, Attapol, Vera Demberg, and Nianwen Xue. 2017.  A systematic study of neural discourse models for implicit discourse relation.  In _Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers_ , pages 281–291, Association for Computational Linguistics, Valencia, Spain.
  * Sanders, Spooren, and Noordman (1992) Sanders, Ted J. M., Wilbert P.M. Spooren, and Leo G.M. Noordman. 1992.  Towards a taxonomy of coherence relations.  _Discourse Processes_ , 15:1–35.
  * Sanders et al. (2021) Sanders, Ted J.M., Vera Demberg, Jet Hoek, C.J. Scholman, Merel, Fatemeh Torabi Asr, Sandrine Zufferey, and Jacqueline Evers-Vermeul. 2021.  Unifying dimensions in coherence relations: How various annotation frameworks are related.  _Corpus Linguistics and Linguistic Theory_ , 17(1):1–71.
  * Sanders, Land, and Mulder (2007) Sanders, Ted J.M., Jentine Land, and Gerben Mulder. 2007.  Linguistic markers of coherence improve text comprehension in functional contexts.  _Information Design Journal_ , 15(3):219–235.
  * Scholman et al. (2021) Scholman, Merel, Tianai Dong, Frances Yung, and Vera Demberg. 2021.  Comparison of methods for explicit discourse connective identification across various domains.  In _Proceedings of the 2nd Workshop on Computational Approaches to Discourse_ , pages 95–106, Association for Computational Linguistics, Punta Cana, Dominican Republic and Online.
  * Shen et al. (2022) Shen, Andrew, Fajri Koto, Jey Han Lau, and Timothy Baldwin. 2022.  Easy-first bottom-up discourse parsing via sequence labelling.  In _Proceedings of the 3rd Workshop on Computational Approaches to Discourse_ , pages 35–41, International Conference on Computational Linguistics, Gyeongju, Republic of Korea and Online.
  * Speer, Chin, and Havasi (2017) Speer, Robyn, Joshua Chin, and Catherine Havasi. 2017.  ConceptNet 5.5: An open multilingual graph of general knowledge.  In _Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence_ , AAAI’17, page 4444–4451, AAAI Press.
  * Stede (2008) Stede, Manfred. 2008.  RST revisited: Disentangling nuclearity.  In Cathrine Fabricius-Hansen and Wiebke Ramm, editors, _’Subordination’ versus ’Coordination’ in Sentence and Text: A cross-linguistic perspective_ , Studies in Language Companion Series 98. John Benjamins, Amsterdam, pages 33–58.
  * Stede (2012) Stede, Manfred. 2012.  _Discourse Processing_.  Synthesis Lectures on Human Language Technologies 4. Morgan & Claypool, [San Rafael, CA].
  * Stede et al. (2016) Stede, Manfred, Stergos Afantenos, Andreas Peldszus, Nicholas Asher, and Jérémy Perret. 2016.  Parallel discourse annotations on a corpus of short texts.  In _Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC’16)_ , pages 1051–1058, European Language Resources Association (ELRA), Portorož, Slovenia.
  * Stede and Neumann (2014) Stede, Manfred and Arne Neumann. 2014.  Potsdam Commentary Corpus 2.0: Annotation for discourse research.  In _Proceedings of the Language Resources and Evaluation Conference (LREC ’14)_ , pages 925–929, Reykjavik.
  * Sun and Wang (2022) Sun, Kun and Rong Wang. 2022.  Constructing the corpus of Chinese textual ’run-on’ sentences (CCTRS): Discourse corpus benchmark with multi-layer annotations.  In _International Conference on Natural Language and Speech Processing (ICNLSP)-2022_ , Trento, Italy.
  * Taboada and Lavid (2003) Taboada, Maite and Julia Lavid. 2003.  Rhetorical and thematic patterns in scheduling dialogues: A generic characterization.  _Functions of Language_ , 10(2):147–179.
  * Taboada and Mann (2006) Taboada, Maite and William C. Mann. 2006.  Rhetorical Structure Theory: Looking back and moving ahead.  _Discourse Studies_ , 8:423–459.
  * Teufel and Moens (2002) Teufel, Simone and Marc Moens. 2002.  Summarising scientific articles - experiments with relevance and rhetorical status.  _Computational Linguistics_ , 28(4):409–445.
  * Tonelli et al. (2010) Tonelli, Sara, Giuseppe Riccardi, Rashmi Prasad, and Aravind Joshi. 2010.  Annotation of discourse relations for conversational spoken dialogs.  In _Proceedings of the Seventh International Conference on Language Resources and Evaluation (LREC’10)_ , European Language Resources Association (ELRA), Valletta, Malta.
  * Vis, Sanders, and Spooren (2012) Vis, Kirsten, José Sanders, and Wilbert Spooren. 2012.  Diachronic changes in subjectivity and stance–a corpus linguistic study of dutch news texts.  _Discourse, Context & Media_, 1(2):95–102.  The view from here, there and nowhere: discursive approaches to journalistic stance.
  * Webber (2013) Webber, Bonnie. 2013.  What excludes an alternative in coherence relations?  In _Proceedings of the 10th International Conference on Computational Semantics (IWCS 2013) – Long Papers_ , pages 276–287, Association for Computational Linguistics, Potsdam, Germany.
  * Widlöcher and Mathet (2012) Widlöcher, Antoine and Yann Mathet. 2012.  The glozz platform: A corpus annotation and mining tool.  In _Proceedings of the 2012 ACM symposium on document engineering_ , pages 171–180.
  * Xue et al. (2016) Xue, Nianwen, Hwee Tou Ng, Sameer Pradhan, Attapol Rutherford, Bonnie Webber, Chuan Wang, and Hongmin Wang. 2016.  CoNLL 2016 shared task on multilingual shallow discourse parsing.  In _Proceedings of the CoNLL-16 shared task_ , pages 1–19, Association for Computational Linguistics, Berlin, Germany.
  * Yang and Li (2018) Yang, An and Sujian Li. 2018.  SciDTB: Discourse dependency TreeBank for scientific abstracts.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 444–449, Association for Computational Linguistics, Melbourne, Australia.
  * Yi, Sujian, and Yueyuan (2021) Yi, Cheng, Li Sujian, and Li Yueyuan. 2021.  Unifying discourse resources with dependency framework.  In _Proceedings of the 20th Chinese National Conference on Computational Linguistics_ , pages 1058–1065, Chinese Information Processing Society of China, Huhhot, China.
  * Yu et al. (2022) Yu, Nan, Meishan Zhang, Guohong Fu, and Min Zhang. 2022.  RST discourse parsing with second-stage EDU-level pre-training.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 4269–4280, Association for Computational Linguistics, Dublin, Ireland.
  * Yu et al. (2019) Yu, Yue, Yilun Zhu, Yang Liu, Yan Liu, Siyao Peng, Mackenzie Gong, and Amir Zeldes. 2019.  GumDrop at the DISRPT2019 shared task: A model stacking approach to discourse unit segmentation and connective detection.  In _Proceedings of the Workshop on Discourse Relation Parsing and Treebanking 2019_ , pages 133–143, Association for Computational Linguistics, Minneapolis, MN.
  * Zeldes (2016) Zeldes, Amir. 2016.  rstWeb - a browser-based annotation interface for Rhetorical Structure Theory and discourse relations.  In _Proceedings of NAACL-HLT 2016 System Demonstrations_ , pages 1–5, San Diego, CA.
  * Zeldes (2017) Zeldes, Amir. 2017.  The GUM corpus: Creating multilayer resources in the classroom.  _Language Resources and Evaluation_ , 51(3):581–612.
  * Zeldes (2022) Zeldes, Amir. 2022.  Can we fix the scope for coreference? problems and solutions for benchmarks beyond OntoNotes.  _Dialogue & Discourse_, 13(1):41–62.
  * Zeldes et al. (2021) Zeldes, Amir, Yang Janet Liu, Mikel Iruskieta, Philippe Muller, Chloé Braud, and Sonia Badene. 2021.  The DISRPT 2021 shared task on elementary discourse unit segmentation, connective detection, and relation classification.  In _Proceedings of Discourse Relation Parsing and Treebanking 2021 (DISRPT 2021)_ , pages 1–12, Punta Cana, Dominican Republic.
  * Zeyrek and Kurfalı (2017) Zeyrek, Deniz and Murathan Kurfalı. 2017.  TDB 1.1: Extensions on Turkish discourse bank.  In _Proceedings of the 11th Linguistic Annotation Workshop_ , pages 76–81, Association for Computational Linguistics, Valencia, Spain.
  * Zeyrek et al. (2019) Zeyrek, Deniz, Amalia Mendes, Yulia Grishina, Murathan Kurfali, Samuel Gibbon, and Maciej Ogrodniczuk. 2019.  Ted multilingual discourse bank (ted-mdb): a parallel corpus annotated in the pdtb style.  _Language Resources and Evaluation_ , pages 1–38.
  * Zeyrek, Mendes, and Kurfalı (2018) Zeyrek, Deniz, Amália Mendes, and Murathan Kurfalı. 2018.  Multilingual extension of PDTB-style annotation: The case of TED multilingual discourse bank.  In _Proceedings of the Eleventh International Conference on Language Resources and Evaluation (LREC 2018)_ , European Language Resources Association (ELRA), Miyazaki, Japan.
  * Zhang, Kong, and Zhou (2021) Zhang, Longyin, Fang Kong, and Guodong Zhou. 2021.  Adversarial learning for discourse rhetorical structure parsing.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 3946–3957, Association for Computational Linguistics, Online.
  * Zhou et al. (2014) Zhou, Yuping, Jill Lu, Jennifer Zhang, and Nianwen Xue. 2014.  Chinese Discourse Treebank 0.5 LDC2014T21.

Relation Labels in GUM

Table 12 gives the full list of relation labels in GUM. Note that same-unit is
not a proper discourse relation, but rather a technical device used to connect
multiple parts of a discontinuous EDU. For a fuller description of the labels
and the most current GUM annotation guidelines, see
https://wiki.gucorpling.org/gum/rst/. All definitions refer to the Reader (or
hearer) as R, the Writer (or speaker) as W, a nucleus as N and a satellite as
S. The nuclearity of the direction is either $\leftarrow$ (for satellite
relations that only go left-to-right), $\rightarrow$ (the opposite),
$\rightarrow\leftarrow$ (a satellite relation in either direction), or
$\Lambda$ (multinuclear relation). Relation names all have the form <coarse-
class>-<fine-grained>, i.e. the first three relations in the table belong to
the coarse class adversative.

relation name | nuclearity | definition
---|---|---
adversative-antithesis | $\rightarrow\leftarrow$ | R is meant to prefer N as an alternative to S
adversative-concession | $\rightarrow\leftarrow$ | R is meant to look past an incompatibility of N with S
adversative-contrast | $\Lambda$ | W presents multiple Ns as incompatible, but of equal prominence
attribution-negative | $\rightarrow\leftarrow$ | S states that a potential source is NOT a source of the information in N
attribution-positive | $\rightarrow\leftarrow$ | S states a source for the information in N
causal-cause | $\rightarrow\leftarrow$ | S is the cause of N and N is more prominent)
causal-result | $\rightarrow\leftarrow$ | S is the result of N or: N is the cause of S, and N is more prominent)
context-background | $\rightarrow\leftarrow$ | S provides information to increase R’s understanding of N
context-circumstance | $\rightarrow\leftarrow$ | S details circumstances often spatio-temporal) under which N applies
contingency-condition | $\rightarrow\leftarrow$ | N occurs depending on S
elaboration-additional | $\leftarrow$ | is used in all other cases, when S is an elaboration on N as a whole
elaboration-attribute | $\leftarrow$ | is used when S elaborates on a participant within N, rather than on the entire proposition in N
evaluation-comment | $\rightarrow\leftarrow$ | S provides an assessment of N by W R does not have to share this assessment)
explanation-evidence | $\rightarrow\leftarrow$ | S provides evidence which increases R’s belief in N
explanation-justify | $\rightarrow\leftarrow$ | S increases R’s acceptance of W’s right to say N
explanation-motivation | $\rightarrow\leftarrow$ | S is meant to influence R’s willingness to act according to N
joint-disjunction | $\Lambda$ | W presents multiple Ns which can be regarded as interchangeable alternatives
joint-list | $\Lambda$ | W presents multiple Ns in parallel which can be regarded as additive to one another
joint-other | $\Lambda$ | any other collection of unlike discourse units of equal prominence at the same level of hierarchy
joint-sequence | $\Lambda$ | Multiple Ns form a temporally ordered sequence of events in order
mode-manner | $\rightarrow\leftarrow$ | S indicates the manner in which N happens
mode-means | $\rightarrow\leftarrow$ | S indicates the means by which N happens
organization-heading | $\rightarrow$ | explicit text organizing device such as a heading
organization-phatic | $\rightarrow\leftarrow$ | W holds the floor, without contributing propositional content
organization-preparation | $\rightarrow$ | covers all other forms of S units primarily used to signal an upcoming N
purpose-attribute | $\rightarrow\leftarrow$ | is used when S gives the purpose of a participant in N, rather than on the entire proposition in N
purpose-goal | $\rightarrow\leftarrow$ | the proposition in N as a whole is initiated or exists in order to realize S
restatement-partial | $\leftarrow$ | S partly realizes the same role and content as a previous N
restatement-repetition | $\Lambda$ | Multiple Ns realize the same role and content
same-unit | $\Lambda$ | indicates a discontinuous discourse unit this is not a discourse relation)
topic-question | $\rightarrow$ | N is the answer to the question posed by S
topic-solutionhood | $\rightarrow\leftarrow$ | N is a solution to a problem presented by S

Table 12: Relation Labels in the GUM Corpus.


# Optimal Protocols for 2-Party Contention Resolution

Dingyu Wang

###### Abstract

_Contention Resolution_ is a fundamental symmetry-breaking problem in which
$n$ devices must acquire temporary and exclusive access to some _shared
resource_ , without the assistance of a mediating authority. For example, the
$n$ devices may be sensors that each need to transmit a single packet of data
over a broadcast channel. In each time step, devices can (probabilistically)
choose to acquire the resource or remain idle; if exactly one device attempts
to acquire it, it succeeds, and if two or more devices make an attempt, none
succeeds. The complexity of the problem depends heavily on what types of
_collision detection_ are available. In this paper we consider
_acknowledgement-based protocols_ , in which devices only learn whether their
own attempt succeeded or failed; they receive no other feedback from the
environment whatsoever, i.e., whether other devices attempted to acquire the
resource, succeeded, or failed.

Nearly all work on the Contention Resolution problem evaluated the performance
of algorithms _asymptotically_ , as $n\rightarrow\infty$. In this work we
focus on the simplest case of $n=2$ devices, but look for _precisely_ optimal
algorithms. We design provably optimal algorithms under three natural cost
metrics: minimizing the expected average of the waiting times (avg), the
expected waiting time until the first device acquires the resource (min), and
the expected time until the last device acquires the resource (max). We first
prove that the optimal algorithms for $n=2$ are _periodic_ in a certain sense,
and therefore have finite descriptions, then we design optimal algorithms
under all three objectives.

  * avg.

The optimal contention resolution algorithm under the avg objective has
expected cost $\sqrt{3/2}+3/2\approx 2.72474$.

  * min.

The optimal contention resolution algorithm under the min objective has
expected cost $2$. (This result can be proved in an ad hoc fashion, and may be
considered folklore.)

  * max.

The optimal contention resolution algorithm under the max objective has
expected cost $1/\gamma\approx 3.33641$, where $\gamma\approx 0.299723$ is the
smallest root of $3x^{3}-12x^{2}+10x-2$.111We may also express $\gamma$ in
radical form:
$\gamma=-\frac{1}{6}\left(1-i\sqrt{3}\right)\sqrt[3]{13+i\sqrt{47}}+\frac{4}{3}-\frac{1+i\sqrt{3}}{\sqrt[3]{13+i\sqrt{47}}}$.

##  1 Introduction

The goal of a contention resolution scheme is to allow multiple devices to
eventually obtain exclusive access to some shared resource. In this
paper222This is the full version of [24].  we will use often use the
terminology of one particular application, namely, wireless devices that wish
to broadcast messages on a multiple-access channel. However, contention
resolution schemes are used in a variety of areas [16, 21, 13], not just
wireless networking. We consider a model of contention resolution that is
distinguished by the following features.

Discrete Time.

Time is partitioned into discrete _slots_. It is the goal of every device to
obtain exclusive access to the channel for exactly one slot, after which it no
longer participates in the protocol. We assume that all $n$ devices begin at
the same time, and therefore agree on slot zero. (Other work considers an
infinite-time model in which devices are injected adversarially [8, 10, 3], or
according to a Poisson distribution [18, 23] with some constant mean.)

Feedback.

At the beginning of each time slot each device can choose to either transmit
its message or remain idle. If it chooses to idle, it receives no feedback
from the environment; if it chooses to transmit, it receives a signal
indicating whether the transmission was successful (all other devices remained
idle). (“Full sensing” protocols like [18, 23, 8, 10, 3], in contrast, depend
on receiving ternary feedback at each time slot indicating whether there was
no transmission, some successful transmission, or a collision.)

Noiseless operation.

The system is errorless; there is no environmental noise.

Anonymity.

Devices are indistinguishable and run the same algorithm, but can break
symmetry by generating (private) random bits.

There are many ways to measure the time-efficiency of contention resolution
protocols. In infinite-time models, we want to avoid deadlock [2, 6, 7, 8, 5,
10], minimize the latency of devices in the system, and generally make
productive use of a (large) constant fraction of the slots [8, 5, 10]. When
all $n$ devices begin at the same time [6, 7], there are still several natural
measures of efficiency. In this paper we consider three: minimizing the time
until the _first_ successful transmission (min), the _last_ successful
transmission time (max, a.k.a. the _makespan_), and the _average_ transmission
time (avg).

###  1.1 Prior Work

Classic infinite-time protocols like ALOHA [1] and binary exponential backoff
algorithms [15, 14] are simple but suffer from poor worst case performance and
eventual deadlock [2, 6, 7], even under _non_ -adversarial injection rates,
e.g., Poisson injection rates with arbitrary small means. These are
_acknowledgement-based_ protocols which do not require constant (ternary)
channel feedback. One line of work aimed to achieve deadlock-freeness under
Poisson arrivals [9, 12, 18, 23], assuming ternary channel feedback. The
maximum channel usage rate is known to be between 0.48776 [18, 23] and 0.5874
[17]. A different line of work aimed at achieving deadlock-freeness and
constant rate of efficiency under _adversarial_ injections and possibly
adversarial _jamming_ , also assuming ternary feedback. See [8, 10, 3] for
robust protocols that can tolerate a jamming adversary. One problem with both
of these lines of work is that all devices must monitor the channel constantly
(for the ternary silence/success/collision feedback). Bender et al. [5]
considered adversarial injection rates and showed that it is possible to
achieve a constant efficiency rate while only monitoring/participating in
$O(\log(\log^{*}n))$ time slots. This was later shown to be optimal [11].

When all $n$ devices start at the same time slot ($n$ unknown), we have a
pretty good understanding of the avg, min, and max objectives. Here there are
still variants of the problem, depending on whether the protocol is full-
sensing (requiring ternery feedback) or merely acknowledgement-based. Willard
[25] and Nakano and Olariu [19] gave full sensing protocols for the min
objective when $n$ is unknown that takes time $O(\log\log n+\log f^{-1})$ with
probability $1-f$, which is optimal. The _decay_ algorithm [4] is an
acknowledgement-based protocol for the min objective that runs in $O(\log
n\log f^{-1})$ time with probability $1-f$, which is also known to be optimal
[20]. When $n$ is unknown, binary exponential backoff achieves optimal $O(n)$
time under the avg objective, but suboptimal $\Theta(n\log n)$ time under the
max objective [6, 7]. The _sawtooth_ protocol of Bender et al. [6, 7] is
optimal $O(n)$ under both avg and max; it is acknowledgement-based.

###  1.2 New Results

In this paper we consider what seems to be the _simplest non-trivial symmetry
breaking problem_ , namely, resolving contention among two parties ($n=2$) via
an acknowledgement-based protocol. The _asymptotic_ complexity of this problem
is not difficult to derive: $O(1)$ time suffices, under any reasonable
objective function, and $O(\log f^{-1})$ time suffices with probability $1-f$.
However, our goal is to discover _precisely_ optimal algorithms.

We derive the optimal protocols for the avg, min, and max objectives, in
expectation, which are produced below. The optimal min protocol is easy to
obtain using _ad hoc_ arguments; it has expected cost $2$. However, the
optimal protocols for avg and max require a more principled, rigorous approach
to the problem. We show that the protocol minimizing avg has expected cost
$\sqrt{3/2}+3/2\approx 2.72474$, and that the optimal protocol minimizing max
has expected cost $1/\gamma\approx 3.33641$, where $\gamma\approx 0.299723$ is
the unique root of $3x^{3}-12x^{2}+10x-2$ in the interval $[1/4,1/3]$.

avg-Contention Resolution: Step 1. Transmit with probability
$\frac{4-\sqrt{6}}{3}\approx 0.516837$. If successful, halt; if there was a
collision, repeat Step 1; otherwise proceed to Step 2. Step 2. Transmit with
probability $\frac{1+\sqrt{6}}{5}\approx 0.689898$. If successful, halt; if
there was a collision, go to Step 1; otherwise proceed to Step 3. Step 3.
Transmit with probability 1. If successful, halt; otherwise go to Step 1.

min-Contention Resolution: • In each step, transmit with probability 1/2 until
successful.

max-Contention Resolution: Step 1. Transmit with probability $\alpha\approx
0.528837$, where $\alpha$ is the unique root of $x^{3}+7x^{2}-21x+9$ in
$[0,1]$. If successful, halt; if there was a collision, repeat Step 1;
otherwise proceed to Step 2. Step 2. Transmit with probability $\beta\approx
0.785997$, where $\beta$ is the unique root of $4x^{3}-8x^{2}+3$ in $[0,1]$.
If successful, halt; if there was a collision, go to Step 1; otherwise proceed
to Step 3. Step 3. Transmit with probability 1. If successful, halt; otherwise
go to Step 1.

One may naturally ask: what is the point of understanding Contention
Resolution problems with $n=O(1)$ devices? The most straightforward answer is
that in some applications, contention resolution instances between $n=O(1)$
devices are commonplace.333For a humorous example, consider the Canadian
Standoff problem https://www.cartoonstock.com/cartoonview.asp?catref=CC137954.
However, even if one is only interested in the asymptotic case of
$n\rightarrow\infty$ devices, understanding how to resolve $n=O(1)$ optimally
is essential. For example, the protocols of [9, 12, 18, 23] work by repeatedly
isolating subsets of the $n^{\prime}$ active devices, where $n^{\prime}$ is
Poisson distributed with mean around 1.1, then resolving conflicts within this
set (if $n^{\prime}>1$) using a near-optimal procedure. The channel usage rate
of these protocols ($\approx 0.48776$) depends critically on the efficiency of
Contention Resolution among $n^{\prime}$ devices, where
$\mathbb{E}[n^{\prime}]=O(1)$. Moreover, _improving_ these algorithms will
likely require a much better understanding of $O(1)$-size contention
resolution.

#### Organization.

In Section 2 we give a formal definition of the model and state Theorem 1 on
the _existence_ of an optimal protocol for any reasonable objective function.
In Section 3 we prove another structural result on optimal protocols for $n=2$
devices under the avg, min, and max objectives (Theorem 2), and use it to
characterize what the optimal protocols for avg (Theorem 3), min (Theorem 4),
and max (Theorem 5) should look like. Corollary 1 derives that avg-Contention
Resolution is the optimal protocol under the avg objective, and Corollary 2
does the same for max-Contention Resolution under max. The proofs of Theorems
1 and 2 and Corollaries 1 and 2 appear in the Appendix.

##  2 Problem Formulation

After each time step the channel issues responses to the devices from the set
$\mathcal{R}=\\{0,1,2_{+}\\}$. If the device idles, it always receives $0$. If
it attempts to transmit, it receives $1$ if successful and $2_{+}$ if
unsuccessful. A _history_ is word over $\mathcal{R}^{*}$. We use exponents for
repetition and $*$ as short for $\mathcal{R}^{*}$; e.g., the history
$0^{3}2_{+}^{2}$ is short for $0002_{+}2_{+}$ and $*1*$ is the set of all
histories containing a $1$. The notation $a\in w$ means that symbol $a$ has at
least one occurrence in word $w$.

Devices choose their action (transmit or idle) at time step $t\in\mathbb{N}$
and receive feedback at time $t+0.5$. A _policy_ is a function $f$ for
deciding the probability of transmitting. Define
$\mathcal{F}=\\{f:\mathcal{R}^{*}\to[0,1]\mid\forall w\in\mathcal{R}^{*},1\in
w\implies f(w)=0\\}$ to be the set of all proper policies, i.e., once a device
is successful ($1\in w$), it must halt ($f(w)=0$).444A policy may have no
finite representation, and therefore may not be an _algorithm_ in the usual
sense. Every particular policy $f\in\mathcal{F}$ induces a distribution on
decisions $\\{D_{k,t}\\}_{k\in[n],t\in\mathbb{N}}$ and responses
$\\{R_{k,t}\\}_{k\in[n],t\in\mathbb{N}}$, where $D_{k,t}=1$ iff the $k$th
device transmits at time $t$ and $R_{k,t}\in\mathcal{R}$ is the response
received by the $k$th device at time $t+0.5$. In particular,

$\displaystyle\mathbb{P}(D_{k,t}=1\mid R_{k,0}R_{k,1}\cdots
R_{k,t-1}=h)=f(h),$ (1) $\displaystyle
R_{k,{t}}(w)=\begin{cases}0,&D_{k,t}(w)=0\\\ 1,&(D_{k,t}(w)=1)\land(\forall
j\neq k,D_{j,t}(w)=0)\\\ 2^{+},&(D_{k,t}(w)=1)\land(\exists j\neq
k,D_{j,t}(w)=1)\end{cases}$ (2)

Define $X_{i}$ to be the random variable of the number of time slots until
device $i$ succeeds. Note that since we number the slots starting from zero,

$\displaystyle X_{i}$ $\displaystyle=1+\min\\{t\geq 0\mid R_{i,t}=1\\}.$

Note that $\\{X_{i}\\}_{i\in[n]}$ are identically distributed but not
independent. For example, minimizing the average of $\\{X_{i}\\}_{i\in[n]}$ is
equivalent to minimizing $X_{1}$ since:

$\displaystyle\mathbb{E}\frac{\sum_{i=1}^{n}X_{i}}{n}=\frac{\sum_{i=1}^{n}\mathbb{E}X_{i}}{n}=\frac{n\mathbb{E}X_{1}}{n}=\mathbb{E}X_{1}.$

###  2.1 Performance Metrics and Existence Issues

For our proofs it is helpful to assume the existence of an _optimal protocol_
but it is not immediate that there _exists_ such an optimal protocol. (Perhaps
there is just an infinite succession of protocols, each better than the next.)
In Appendix A.2 we prove that optimal protocols exist for all “reasonable”
objectives. A _cost function_ $T:\mathbb{Z}_{+}^{n}\rightarrow\mathbb{R}_{+}$
is one that maps the vector of device latencies to a single (positive) cost.
The objective is to minimize $\mathbb{E}T(X_{1},\ldots,X_{n})$.

######  Definition 1 (Informal).

A function $T:\mathbb{Z}_{+}^{n}\to\mathbb{R}^{+}$ is _reasonable_ if for any
$s>0$ there exists some $N>0$ such that $T(x_{1},\ldots,x_{n})<s$ can be known
if each of $x_{1},x_{2},\ldots,x_{n}$ is either known or known to be greater
than $N$.

For example, $T_{1}(x_{1},\ldots,x_{n})=\frac{\sum_{k=1}^{n}x_{k}}{n}$ (avg),
$T_{2}(x_{1},\ldots,x_{n})=\min(x_{1},\ldots,x_{n})$ (min), and
$T_{3}(x_{1},\ldots,x_{n})=\max(x_{1},\ldots,x_{n})$ (max) are all reasonable,
as are all $\ell_{p}$ norms, etc.

######  Theorem 1.

Given the number of users $n$ and a reasonable objective function $T$, there
exists an optimal policy $f^{*}\in\mathcal{F}$ that minimizes
$\mathbb{E}T(X_{1},X_{2},\ldots,X_{n})$.

##  3 Contention Resolution Between Two Parties

In this section we restrict our attention to the case $n=2$. One key
observation that makes the $n=2$ case special is that whenever one device
receives $2_{+}$ (collision) feedback, it knows that its history and the other
device’s history are identical. For many reasonable objective functions the
best response to a collision is to restart the protocol. This is proved
formally in Theorem 2 for a class of objective functions that includes avg,
min, and max. See Appendix A.3 for proof.

######  Theorem 2.

Let $n=2$, $T$ be a reasonable objective function, and $f$ be an optimal
policy for $T$. Another policy $f^{*}$ is defined as follows.

$\displaystyle f^{*}(0^{k})$ $\displaystyle=f(0^{k}),\quad\forall
k\in\mathbb{N}$ $\displaystyle f^{*}(*2_{+}0^{k})$
$\displaystyle=f(0^{k}),\quad\forall k\in\mathbb{N}$ $\displaystyle
f^{*}(*1*)$ $\displaystyle=0$

If $T(x+c,y+c)=T(x,y)+c$ for any $c$ (scalar additivity), then $f^{*}$ is also
an optimal policy for $T$.

Theorem 2 tells us that for the objectives that are scalar additive (including
avg, min, and max), we can restrict our attention to policies
$f\in\mathcal{F}$ defined by a vector of probabilities $(p_{i})_{i\geq 0}$,
such that $f(w0^{k})=p_{k}$, where $w$ is empty or ends with $2_{+}$, i.e.,
the transmission probability cannot depend on anything that happened _before_
the last collision.

###  3.1 Avg: Minimizing the Average Transmission Time

Let $(p_{k})_{k\geq 0}$ be the probability sequence corresponding to an
optimal policy $f$ for avg. We first express our objective $\mathbb{E}X_{1}$
in terms of the sequence $(p_{k})$. Then, using the optimality of $f$, we
deduce that $(p_{k})_{k\geq 0}$ must take on the special form described in
Theorem 3. This Theorem does not completely specify what the optimal protocol
looks like. Further calculations (Corollary 1) show that choosing $N=2$ is the
best choice, and that avg-Contention Resolution (see Section 1) is an optimal
protocol.

######  Theorem 3.

There exists an integer $N>0$ and $a_{0},a_{1},a_{2}\in\mathbb{R}$ where
$a_{0}-a_{1}+a_{2}=1$ and $a_{0}+a_{1}N+a_{2}N^{2}=0$ such that the following
probability sequence

$\displaystyle
p_{k}=1-\frac{a_{0}+a_{1}k+a_{2}k^{2}}{a_{0}+a_{1}(k-1)+a_{2}(k-1)^{2}},\quad
0\leq k\leq N,$

induces an optimal policy that minimizes $\mathbb{E}X_{1}$.

######  Remark.

Note that defining $p_{0},\ldots,p_{N}$ is sufficient, since $p_{N}=1$ induces
a certain collision if there are still 2 devices in the system, which causes
the algorithm to reset. In the next time slot both devices would transmit with
probability $p_{0}$.

###### Proof.

Assume we are using an optimal policy $f^{*}$ induced by a probability
sequence $(p_{i})_{i=1}^{\infty}$. Define $S_{1},S_{2}\geq 0$ to be the random
variables indicating the _index_ of the first slot in which devices 1 and 2
first transmit. Observe that $S_{1}$ and $S_{2}$ are i.i.d. random variables,
where
$\mathbb{P}(S_{1}=k)=\mathbb{P}(S_{2}=k)=p_{k}\prod_{i=0}^{k-1}(1-p_{i})$.555We
use the convention that $\prod_{i=0}^{-1}a_{k}=1$, where
$(a_{k})_{k=0}^{\infty}$ is any sequence. We have

$\displaystyle\mathbb{E}X_{1}$
$\displaystyle=\sum_{k=0}^{\infty}\left[\mathbb{P}(S_{1}=k)(k+1+\mathbb{P}(S_{2}=k)\cdot\mathbb{E}X_{1})\right]$
$\displaystyle\iff\mathbb{E}X_{1}$
$\displaystyle=\sum_{k=0}^{\infty}\left[p_{k}\left(\prod_{i=0}^{k-1}(1-p_{i})\right)\cdot\left(k+1+p_{k}\left(\prod_{i=0}^{k-1}(1-p_{i})\right)\cdot\mathbb{E}X_{1}\right)\right].$
(3)

Define $m_{k}=\prod_{i=0}^{k}(1-p_{i})$ to be the probability that a device
idles in time steps $0$ through $k$, where $m_{-1}=1$. Note that
$p_{k}m_{k-1}=m_{k-1}-m_{k}$ is true for all $k\geq 0$. We can rewrite Eqn.
(3) as:

$\displaystyle\mathbb{E}X_{1}$
$\displaystyle=\sum_{k=0}^{\infty}\left[(m_{k-1}-m_{k})(k+1+(m_{k-1}-m_{k})\cdot\mathbb{E}X_{1})\right]$
$\displaystyle\iff\mathbb{E}X_{1}$
$\displaystyle=\mathbb{E}X_{1}\cdot\sum_{k=0}^{\infty}(m_{k-1}-m_{k})^{2}+\sum_{k=0}^{\infty}(m_{k-1}-m_{k})(k+1)$
$\displaystyle\iff\mathbb{E}X_{1}$
$\displaystyle=\frac{\sum_{k=0}^{\infty}m_{k-1}}{1-\sum_{k=0}^{\infty}(m_{k-1}-m_{k})^{2}}.$
(4)

By definition, $(m_{k})_{k=-1}^{\infty}$ is a non-increasing sequence with
$m_{-1}=1$ and $m_{k}\geq 0$. There is no optimal policy with
$m_{k-1}=m_{k}\neq 0$ (meaning $p_{k}=0$), since otherwise we can delete
$m_{k}$ from the sequence, leaving the denominator unchanged but reducing the
numerator. This implies $(m_{k})_{k=-1}^{\infty}$ is either an infinite,
positive, strictly decreasing sequence or a finite, positive, strictly-
decreasing sequence followed by a tail of zeros. Pick any index $k_{0}\geq 0$
such that $m_{k_{0}}>0$. We know $m_{k_{0}-1}>m_{k_{0}}>m_{k_{0}+1}$. By the
optimality of $f^{*}$, $m_{k_{0}}$ must, holding all other parameters fixed,
be the optimal choice for this parameter in its neighborhood. In other words,

$\displaystyle\frac{\partial\mathbb{E}X_{1}}{\partial m_{k_{0}}}=0$
$\displaystyle\iff$
$\displaystyle\frac{1-\sum_{k=0}^{\infty}(m_{k-1}-m_{k})^{2}+\sum_{k=0}^{\infty}m_{k-1}(-2(m_{k_{0}-1}-m_{k_{0}})+2(m_{k_{0}}-m_{k_{0}+1}))}{(1-\sum_{k=0}^{\infty}(m_{k-1}-m_{k})^{2})^{2}}=0$

Therefore we have for any $k_{0}\geq 0$ such that $m_{k_{0}}>0$,

$\displaystyle 2m_{k_{0}}-m_{k_{0}+1}-m_{k_{0}-1}=C$ $\displaystyle\iff$
$\displaystyle m_{k_{0}}-m_{k_{0}+1}=m_{k_{0}-1}-m_{k_{0}}+C$ (5)

where
$C=\frac{\sum_{k=0}^{\infty}(m_{k-1}-m_{k})^{2}-1}{2\sum_{k=0}^{\infty}m_{k-1}}$
is a real constant. Note that $C=-\frac{1}{2\mathbb{E}X_{1}}<0$. Fix any
$k_{1}\geq 0$ such that $m_{k_{1}}>0$. By summing up Eqn. (5) for
$k_{0}=0,1,\ldots,k_{1}$ and rearranging terms, we have

$\displaystyle m_{k_{1}}-m_{k_{1}+1}=(k_{1}+1)C+m_{-1}-m_{0}.$ (6)

Fix any $k_{2}\geq 0$ such that $m_{k_{2}}>0$. By summing up Eqn. (6) for
$k_{1}=0,1,\ldots,k_{2}$, we have

$\displaystyle m_{k_{2}+1}$
$\displaystyle=(m_{0}-m_{-1})(k_{2}+2)+m_{-1}-\frac{(k_{2}+1)(k_{2}+2)}{2}C$
(7)
$\displaystyle=-\frac{C}{2}k_{2}^{2}+\left(-\frac{3C}{2}+m_{0}-m_{-1}\right)k_{2}+2m_{0}-m_{-1}-C.$
(8)

Recall that $C<0$ and $m_{k}\in[0,1]$. This rules out the possibility that the
sequence $(m_{k})_{k=0}^{\infty}$ is an infinite strictly decreasing sequence,
since a non-degenerate quadratic function is unbounded as $k$ goes to
infinity. As a result, there must be a positive integer $N\geq 1$ for which
$m_{N-1}>0$ and $m_{N}=0$. Also note that Eqn. (7) is not only true for
$k_{2}=0,1,\ldots N-1$, but also true for $k_{2}=-1$ and $-2$. (This can be
checked by directly setting $k_{2}=-1$ and $-2$.) We conclude that it is
possible to write $(m_{k})$ as

$\displaystyle m_{k}$ $\displaystyle={a_{0}+a_{1}k+a_{2}k^{2}},\quad-1\leq
k\leq N,$ for some constants $a_{0},a_{1},a_{2}$ satisfying $\displaystyle
m_{-1}$ $\displaystyle=a_{0}-a_{1}+a_{2}=1$ $\displaystyle m_{N}$
$\displaystyle=a_{0}+a_{1}N+a_{2}N^{2}=0.$

Writing $p_{k}=1-\frac{m_{k}}{m_{k-1}}$ gives the statement of the theorem. ∎

Based on Theorem 3, we can find the optimal probability sequence for each
fixed $N$ by choosing the best $a_{2}$. It turns out that $N=2$ is the best
choice, though $N=3$ is only marginally worse. The proof of Corollary 1 is in
Appendix A.4.

######  Corollary 1.

avg-Contention Resolution is an optimal protocol for $n=2$ devices under the
avg objective. The expected average time is $\sqrt{3/2}+3/2\approx 2.72474$.

###  3.2 Min: Minimizing the Earliest Transmission Time

It is straightforward to show $\mathbb{E}\min(X_{1},X_{2})=2$ under the
optimal policy. Nonetheless, it is useful to have a general closed form
expression for $\mathbb{E}\min(X_{1},X_{2})$ in terms of the $(m_{k})$
sequence of an arbitrary (suboptimal) policy, as shown in the proof of Theorem
4. This will come in handy later since $\mathbb{E}\max(X_{1},X_{2})$ can be
expressed as $2\mathbb{E}X_{1}-\mathbb{E}\min(X_{1},X_{2})$.

######  Theorem 4.

The policy that minimizes $\mathbb{E}\min(X_{1},X_{2})$, min-Contention
Resolution, transmits with constant probability $1/2$ until successful. Using
the optimal policy, $\mathbb{E}\min(X_{1},X_{2})=2$.

###### Proof.

By Theorem 2 we can consider an optimal policy defined by a sequence of
transmission probabilities $(p_{k})_{k\geq 0}$. Let $H_{j,k}$ be the
transmission/idle history of player $j\in\\{1,2\\}$ up to time slot $k$. Then
we have

$\displaystyle\mathbb{E}\min(X_{1},X_{2})$
$\displaystyle=\sum_{k=0}^{\infty}\mathbb{P}(H_{1,k}=H_{2,k}=0^{k}1)(k+1+\mathbb{E}\min(X_{1},X_{2}))$
$\displaystyle\;\;\;\;\;\;\;\;+\sum_{k=0}^{\infty}\mathbb{P}(\\{H_{1,k},H_{2,k}\\}=\\{0^{k}1,0^{k}0\\})(k+1)$
$\displaystyle=\sum_{k=0}^{\infty}\left(\prod_{i=0}^{k-1}(1-p_{i})^{2}\cdot
p_{k}^{2}(k+1+\mathbb{E}\min(X_{1},X_{2}))\right)$
$\displaystyle\;\;\;\;\;\;\;\;+\sum_{k=0}^{\infty}\left(\prod_{i=0}^{k-1}(1-p_{i})^{2}\cdot
2p_{k}(1-p_{k})(k+1)\right)$
$\displaystyle=\sum_{k=0}^{\infty}\left(\prod_{i=0}^{k-1}(1-p_{i})^{2}\cdot\left((1-(1-p_{k})^{2})(k+1)+p_{k}^{2}\cdot\mathbb{E}\min(X_{1},X_{2})\right)\right).$
Defining $m_{k}=\prod_{i=0}^{k}(1-p_{i})$ as before, we have
$\displaystyle=\sum_{k=0}^{\infty}\left((m_{k-1}^{2}-m_{k}^{2})(k+1)+m_{k-1}^{2}p_{k}^{2}\cdot\mathbb{E}\min(X_{1},X_{2})\right)$
As $m_{k-1}p_{k}=m_{k-1}-m_{k}$, we can write $\mathbb{E}\min(X_{1},X_{2})$ in
closed form as $\displaystyle\mathbb{E}\min(X_{1},X_{2})$
$\displaystyle=\frac{\sum_{k=0}^{\infty}(m_{k-1}^{2}-m_{k}^{2})(k+1)}{1-\sum_{k=0}^{\infty}(m_{k-1}-m_{k})^{2}}$
$\displaystyle=\frac{\sum_{k=0}^{\infty}m_{k-1}^{2}}{1-\sum_{k=0}^{\infty}(m_{k-1}-m_{k})^{2}}$
(9)
$\displaystyle=\frac{\sum_{k=0}^{\infty}m_{k-1}^{2}}{2\sum_{k=0}^{\infty}(m_{k-1}-m_{k})m_{k}}$
$\displaystyle\geq\frac{\sum_{k=0}^{\infty}m_{k-1}^{2}}{2\sum_{k=0}^{\infty}\left(\frac{m_{k-1}}{2}\right)^{2}}=2\;\;\;\;\;\;\mbox{($(m_{k-1}-m_{k})m_{k}$
maximized when $m_{k}=m_{k-1}/2$.)}$

$\mathbb{E}\min(X_{1},X_{2})$ attains minimum $2$ if and only if for all
$k\in\mathbb{N}$, $m_{k-1}-m_{k}=m_{k}$, i.e. $m_{k}=\frac{m_{k-1}}{2}$ and
$m_{0}=\frac{1}{2}$. Thus $p_{k}=1-\frac{m_{k}}{m_{k-1}}=\frac{1}{2}$ for all
$k$. This constant probability sequence corresponds to the constant policy
with sending probability $\frac{1}{2}$ (i.e., min-Contention Resolution). ∎

###  3.3 Max: Minimizing the Last Transmission Time

Before determining the optimal policy under the max objective, it is useful to
have a crude estimate for its cost.

######  Lemma 1.

Let $f$ be the optimal policy for the max objective and $X_{1}^{f},X_{2}^{f}$
be the latencies of the two devices. Then
$\mathbb{E}\max(X_{1}^{f},X_{2}^{f})\in[3,4]$.

###### Proof.

The optimal policy under the min objective, $f^{*}$, sends with probability
1/2 until successful. It is easy to see that
$\mathbb{E}\max(X_{1}^{f^{*}},X_{2}^{f^{*}})=4$, so $f$ can do no worse. Under
$f$ (or any policy), $\mathbb{E}\max(X_{1}^{f},X_{2}^{f})\geq
1+\mathbb{E}\min(X_{1}^{f},X_{2}^{f})$. By the optimality of $f^{*}$ for min,
$\mathbb{E}\min(X_{1}^{f},X_{2}^{f})\geq\mathbb{E}\min(X_{1}^{f^{*}},X_{2}^{f^{*}})=2$,
so $\mathbb{E}\max(X_{1}^{f},X_{2}^{f})\geq 3$. ∎

######  Theorem 5.

Let $f$ be the optimal policy for the max objective and define
$1/\gamma=\mathbb{E}\max(X_{1}^{f},X_{2}^{f})$ to be its expected cost. Let
$x_{1},x_{2}$ be the roots of the polynomial

$\displaystyle x^{2}-(2-\gamma)x+1.$ (10)

There exists an integer $N\geq 0$ and reals $C_{1},C_{2}$ where
$C_{1}x_{1}^{-1}+C_{2}x_{2}^{-1}=0$ and
$C_{1}x_{1}^{N+1}+C_{2}x_{2}^{N+1}=-1$, such that the following probability
sequence

$\displaystyle
p_{k}=1-\frac{C_{1}x_{1}^{k}+C_{2}x_{2}^{k}+1}{C_{1}x_{1}^{k-1}+C_{2}x_{2}^{k-1}+1},\quad
0\leq k\leq N+1,$

induces an optimal policy that minimizes $\mathbb{E}\max(X_{1},X_{2})$.

######  Remark.

Note that $p_{N+1}=1$, thus it is sufficient to only define
$p_{0},p_{1},\ldots,p_{N+1}$.

###### Proof.

Assume the optimal policy $f$ is characterized by the probability sequence
$(p_{k})_{k=0}^{\infty}$. Using the derived expressions (Eqn. (4) and Eqn.
(9)) in Theorem 3 and 4, we have

$\displaystyle\mathbb{E}\max(X_{1},X_{2})$
$\displaystyle=2\mathbb{E}X_{1}-\mathbb{E}\min(X_{1},X_{2})$
$\displaystyle=2\frac{\sum_{k=0}^{\infty}m_{k-1}}{1-\sum_{k=0}^{\infty}(m_{k-1}-m_{k})^{2}}-\frac{\sum_{k=0}^{\infty}m_{k-1}^{2}}{1-\sum_{k=0}^{\infty}(m_{k-1}-m_{k})^{2}}$
$\displaystyle=\frac{2\sum_{k=0}^{\infty}m_{k-1}-\sum_{k=0}^{\infty}m_{k-1}^{2}}{1-\sum_{k=0}^{\infty}(m_{k-1}-m_{k})^{2}},$
(11)

where $m_{k}=\prod_{i=0}^{k}(1-p_{i})$ with $m_{-1}=1$.

The only requirement on the sequence $(m_{k})_{k=-1}^{\infty}$ is that it is
strictly decreasing with $m_{k}\in[0,1]$. First we observe if $m_{k}=m_{k+1}$,
we must have both of them equal to zero. Otherwise, we can remove $m_{k}$
which will leave the denominator unchanged but reduce the numerator.
Therefore, the optimal sequence is either a strictly decreasing sequence or a
strictly decreasing sequence followed by a tail of zeros. Fix any $v\geq 0$
for which $m_{v}>0$ we have, by the optimality of $(m_{k})_{k=-1}^{\infty}$,

$\displaystyle\frac{\partial\mathbb{E}\max(X_{1},X_{2})}{\partial
m_{v}}=\frac{(2-2m_{v})B-2A(m_{v-1}-m_{v}-(m_{v}-m_{v+1}))}{D}=0,$ (12)

where $B=1-\sum_{k=0}^{\infty}(m_{k-1}-m_{k})^{2}$ and
$A=2\sum_{k=0}^{\infty}m_{k-1}-\sum_{k=0}^{\infty}m_{k-1}^{2}$. Let
$\gamma=\frac{B}{A}=\frac{1}{\mathbb{E}\max(X_{1},X_{2})}$, then we have, from
Eqn. (12)

$\displaystyle m_{v+1}=(2-\gamma)m_{v}-m_{v-1}+\gamma$ (13)
$\displaystyle\iff$ $\displaystyle(m_{v+1}-1)=(2-\gamma)(m_{v}-1)-(m_{v-1}-1)$
(14)

Eqn. (14) defines a linear homogeneous recurrence relation for the sequence
$(m_{v+1}-1)$, whose characteristic roots are
$x_{1},x_{2}=\frac{2-\gamma\pm\sqrt{\gamma^{2}-4\gamma}}{2}$. One may verify
that they satisfy the following identities.

$\displaystyle x_{1}+x_{2}=2-\gamma$ (15) $\displaystyle x_{1}x_{2}=1$ (16)

From Lemma 1 we know $\gamma\in[\frac{1}{4},\frac{1}{3}]$. Thus we have
$\gamma^{2}-4\gamma<0$ which implies $x_{1}$ and $x_{2}$ are distinct
conjugate numbers and of the same norm $\sqrt{x_{1}x_{2}}=1$. Then
$m_{k}-1=C_{1}x_{1}^{k}+C_{2}x_{2}^{k}$ for all $k$ for which at least one of
$m_{k-1},m_{k}$ or $m_{k+1}$ is greater than zero.

If it were the case that $m_{k}>0$ for all $k$, then by summing (13) up for
all $v\in\mathbb{N}$, we have

$\displaystyle\sum_{k=0}^{\infty}m_{k+1}=(2-\gamma)\sum_{k=0}^{\infty}m_{k}-\sum_{k=0}^{\infty}m_{k-1}+\gamma\cdot\infty$

which implies $\sum_{k=0}^{\infty}m_{k}=\infty$. This is impossible since, by
the upper bound of Lemma 1,

$4\geq\mathbb{E}\max(X_{1},X_{2})=\frac{1+2\sum_{k=0}^{\infty}m_{k}-\sum_{k=0}^{\infty}m^{2}_{k}}{1-\sum_{k=0}^{\infty}(m_{k-1}-m_{k})^{2}}\geq\frac{1+\sum_{k=0}^{\infty}m_{k}}{1}.$

Therefore the optimal sequence must be of the form

$\displaystyle m_{k}=(C_{1}x_{1}^{k}+C_{2}x_{2}^{k}+1)\mathbbm{1}_{k\leq N}$

for some integer $N\geq 0$, where $C_{1}x_{1}^{N}+C_{2}x_{2}^{N}+1=0$ and
$C_{1}x_{1}^{-1}+C_{2}x_{2}^{-1}+1=1$. Writing $p_{k}=1-\frac{m_{k}}{m_{k-1}}$
gives the statement of the theorem. ∎

The proof of Corollary 2 is in Appendix A.5.

######  Corollary 2.

max-Contention Resolution is an optimal protocol for $n=2$ devices under the
max objective. The expected maximum latency is $1/\gamma\approx 3.33641$,
where $\gamma$ is the unique root of $3x^{3}-12x^{2}+10x-2$ in the interval
$[1/4,1/3]$.

##  4 Conclusion

In this paper we established the existence of optimal contention resolution
policies for any _reasonable_ cost metric, and derived the first optimal
protocols for resolving conflicts between $n=2$ parties under the avg, min,
and max objectives.

Generalizing our results to $n\geq 3$ or to more complicated cost metrics
(e.g., the $\ell_{2}$ norm) is a challenging problem. Unlike the $n=2$ case,
it is not clear, for example, whether the optimal protocols for $n=3$ select
their transmission probabilities from a finite set of reals. It is also
unclear whether the optimal protocols for $n=3$ satisfy some analogue of
Theorem 2, i.e., that they are “recurrent” in some way.

## References

  * [1] Norman Abramson.  The ALOHA system: another alternative for computer communications.  In Proceedings of the November 17-19, 1970, fall joint computer conference, pages 281–285. ACM, 1970.
  * [2] D. J. Aldous.  Ultimate instability of exponential back-off protocol for acknowledgment-based transmission control of random access communication channels.  IEEE Trans. Information Theory, 33(2):219–223, 1987.
  * [3] B. Awerbuch, A. W. Richa, and C. Scheideler.  A jamming-resistant MAC protocol for single-hop wireless networks.  In Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 45–54, 2008.
  * [4] R. Bar-Yehuda, O. Goldreich, and A. Itai.  On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization.  Journal of Computer and System Sciences, 45(1):104–126, 1992.
  * [5] M. Bender, T. Kopelowitz, S. Pettie, and M. Young.  Contention resolution with constant throughput and log-logstar channel accesses.  SIAM Journal on Computing, 47(5):1735–1754, 2018.
  * [6] M. A. Bender, M. Farach-Colton, S. He, B. C. Kuszmaul, and C. E. Leiserson.  Adversarial analyses of window backoff strategies.  In Proceedings 18th International Parallel and Distributed Processing Symposium (IPDPS), 2004.
  * [7] M. A. Bender, M. Farach-Colton, S. He, B. C. Kuszmaul, and C. E. Leiserson.  Adversarial contention resolution for simple channels.  In Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 325–332, 2005.
  * [8] M. A. Bender, J. T. Fineman, S. Gilbert, and M. Young.  Scaling exponential backoff: Constant throughput, polylogarithmic channel-access attempts, and robustness.  J. ACM, 66(1):6:1–6:33, 2019.
  * [9] J. Capetanakis.  Tree algorithms for packet broadcast channels.  IEEE Trans. Information Theory, 25(5):505–515, 1979.
  * [10] Y.-J. Chang, W. Jin, and S. Pettie.  Simple contention resolution via multiplicative weight updates.  In Proceedings 2nd Symposium on Simplicity in Algorithms (SOSA), pages 16:1–16:16, 2019.
  * [11] Y.-J. Chang, T. Kopelowitz, S. Pettie, R. Wang, and W. Zhan.  Exponential separations in the energy complexity of leader election.  In Proceedings 49th Annual ACM Symposium on Theory of Computing (STOC), pages 771–783, 2017.
  * [12] R. G. Gallager.  Conflict resolution in random access broadcast networks.  In Proceedings AFOSR Workshop on Communications Theory Applications, Provincetown, MA, Sept 17–20, pages 74–76, 1978.
  * [13] Van Jacobson.  Congestion avoidance and control.  In ACM SIGCOMM computer communication review, volume 18, pages 314–329. ACM, 1988.
  * [14] B.-J. Kwak, N.-O. Song, and L. E. Miller.  Performance analysis of exponential backoff.  IEEE/ACM Transactions on Networking (TON), 13(2):343–355, 2005\.
  * [15] R. M. Metcalfe and D. R. Boggs.  Ethernet: Distributed packet switching for local computer networks.  Communications of the ACM, 19(7):395–404, 1976.
  * [16] Robert M Metcalfe and David R Boggs.  Ethernet: Distributed packet switching for local computer networks.  Communications of the ACM, 19(7):395–404, 1976.
  * [17] V. A. Mikhailov and B. S. Tsybakov.  Upper bound for the capacity of a random multiple access system.  Problemy Peredachi Informatsii, 17(1):90–95, 1981.
  * [18] J. Mosely and P. A. Humblet.  A class of efficient contention resolution algorithms for multiple access channels.  IEEE Trans. Communications, 33(2):145–151, 1985.
  * [19] K. Nakano and S. Olariu.  Uniform leader election protocols for radio networks.  IEEE Trans. Parallel Distrib. Syst., 13(5):516–526, 2002.
  * [20] C. Newport.  Radio network lower bounds made easy.  In Proceedings of the 28th International Symposium on Distributed Computing (DISC), pages 258–272, 2014.
  * [21] Ravi Rajwar and James R Goodman.  Speculative lock elision: Enabling highly concurrent multithreaded execution.  In Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, pages 294–305. IEEE Computer Society, 2001.
  * [22] H. L. Royden and P. Fitzpatrick.  Real analysis, volume 32.  Macmillan, New York, 1988.
  * [23] B. S. Tsybakov and V. A. Mikhailov.  Slotted multiaccess packet broadcasting feedback channel.  Problemy Peredachi Informatsii, 14(4):32–59, 1978.
  * [24] Dingyu Wang.  Optimal protocols for 2-party contention resolution.  In International Symposium on Stabilization, Safety, and Security of Distributed Systems, 2021.
  * [25] D. E. Willard.  Log-logarithmic selection resolution protocols in a multiple access channel.  SIAM J. Comput., 15(2):468–477, 1986.

##  Appendix A Proof of Theorems

###  A.1 Deduction on Random Board Model

In order to implement a contention resolution policy we need to generate
biased random bits, e.g., in order to transmit with probability $1/3$.
However, the bias of each time step could be different and depend on the
outcome of previous time steps. It will be convenient if we can generate all
randomness in advance and dynamically set the biases as we go. To that end we
define the Random Board model, which is just an infinite number of uniform and
i.i.d. random reals in $[0,1]$. If device $k$ in time step $t$ wants to
generate a biased random bit $b$ with probability $1/3$ of 1, it sets
$b=\mathbbm{1}(U_{k,t}<1/3)$, where $(U_{k,t})$ is the random board.

######  Definition 2 (Random Board).

A random board $U$ with $n$ rows are a set of i.i.d. uniformly distributed
random variables $(U_{k,t})_{k\in[n],t\in\mathbb{N}}$ with range $[0,1]$.

######  Definition 3 (Deduction on Random Board).

Given a policy $f\in\mathcal{F}$ and an outcome
$(u_{k,t})_{k\in[n],t\in\mathbb{N}}$ of an $n$-row random board where
$u_{k,t}\in[0,1]$, we deduce
$(\bar{d}_{k,t},\bar{r}_{k,t})_{k\in[n],t\in\mathbb{N}}$ iteratively by the
following rule.

$\displaystyle\bar{d}_{k,t}$
$\displaystyle=\mathbbm{1}(u_{k,t}<f((\bar{r}_{k,0}\bar{r}_{k,1}\ldots\bar{r}_{k,t-1})))$
(1 iff device $k$ transmits at time $t$) $\displaystyle\bar{r}_{k,t}$
$\displaystyle=\begin{cases}0,&\bar{d}_{k,t}=0\\\
1,&(\bar{d}_{k,t}=1)\land(\forall j\neq k,\bar{d}_{j,t}=0)\\\
2_{+},&(\bar{d}_{k,t}=1)\land(\exists j\neq k,\bar{d}_{j,t}=1)\end{cases}$
(the response at time $t+0.5$)

We define $\bar{D}_{k,t}$ and $\bar{R}_{k,t}$ be the random variables that
maps outcomes to the deduced $\bar{d}_{k,t}$ and $\bar{r}_{k,t}$ respectively.

We demonstrate the deduction on random board by the following example.

######  Example 1.

Let Table 1 be an outcome $w_{0}$ of a 3-row random board.

0.23371 | 0.281399 | 0.375409 | 0.927202 | 0.0824814 | 0.0473227 | …
---|---|---|---|---|---|---
0.216321 | 0.4534 | 0.377702 | 0.573771 | 0.704855 | 0.497943 | …
0.888769 | 0.939998 | 0.261829 | 0.343283 | 0.830001 | 0.43118 | …
Table 1: An outcome $w_{0}$ of a 3-row random board

Let $f_{1}$ be the policy with constant sending probability $\frac{1}{2}$
until the message gets successfully transmitted. Let $f_{2}$ be the policy
with constant sending probability $\frac{1}{3}$ before success. Then the
results of deduction are shown in the following two tables
$(\bar{d}_{k,t},\bar{r}_{k,t})_{k\in[n],t\in\mathbb{N}}$ (successful
transmissions are marked by a star $*$).

(send,$2^{+}$) | (send,$2^{+}$) | (send,$2^{+}$) | (idle,0) | (send*,1) | (idle,0) | …
---|---|---|---|---|---|---
(send,$2^{+}$) | (send,$2^{+}$) | (send,$2^{+}$) | (idle,0) | (idle,0) | (send*,1) | …
(idle,0) | (idle,0) | (send,$2^{+}$) | (send*,1) | (idle,0) | (idle,0) | …
Table 2: Deduction on $w_{0}$ using policy $f_{1}$ (constant sending probability $\frac{1}{2}$) (send,$2^{+}$) | (send*,1) | (idle,0) | (idle,0) | (idle,0) | (idle,0) | …
---|---|---|---|---|---|---
(send,$2^{+}$) | (idle,0) | (idle,0) | (idle,0) | (idle,0) | (idle,0) | …
(idle,0) | (idle,0) | (send*,1) | (idle,0) | (idle,0) | (idle,0) | …
Table 3: Deduction on $w_{0}$ using policy $f_{2}$ (constant sending
probability $\frac{1}{3}$)

######  Lemma 2.

Given an $n$-row random board $U$, for any policy $f\in\mathcal{F}$, the
deduced set of random variables
$(\bar{D}_{k,t},\bar{R}_{k,t})_{k\in[n],t\in\mathbb{N}}$ satisfies both
equations (1) and (2).

###### Proof.

Equation (2) follows directly by the definition of deduction. For equation
(1), we have

$\displaystyle\mathbb{P}(\bar{D}_{k,t}=1\mid\bar{R}_{k,1}\bar{R}_{k,2}\ldots\bar{R}_{k,t}=h)$
$\displaystyle=\mathbb{P}(U_{k,t}<f(h))$ $\displaystyle=f(h).$

∎

From Lemma 2 we know, using the same $f$, the random processes
$(D_{k,t},R_{k,t})_{k\in[n],t\in\mathbb{N}}$ and
$(\bar{D}_{k,t},\bar{R}_{k,t})_{k\in[n],t\in\mathbb{N}}$ are of identical
distributions and thus $(X_{i})_{i\in[n]}$ and $(\bar{X}_{i})_{i\in[n]}$ are
also identically distributed. Having this, we now can consider all the
policies working on a same sample space, i.e. the sample space of the random
board.

###  A.2 Existence Issues

For notation, we denote any random variable $X$ (e.g. $X_{i}$, $D_{k,t}$ and
$R_{k,t}$) induced by policy $f$ as $X^{f}$.

Having the random board model set up, we now can go on proving the existence
theorem. We first formally define the class of _reasonable_ objective
functions.

######  Definition 4.

We say an objective function $T:\mathbb{R}^{n}\to\mathbb{R}^{+}$ is
_reasonable_ if for any $s>0$, there exists some $N_{s}>0$ such that
$\mathbbm{1}(T(X_{1},X_{2},\ldots,X_{n})<s)$ only depends on the deduction of
the first $N_{s}$ time slots. In other words, there exists a function $h$ such
that
$\mathbbm{1}(T(X_{1},X_{2},\ldots,X_{n})<s)=h(\\{D_{k,t},R_{k,t}\\}_{k\in[n],t\in[N_{s}]})$.

###### Proof of Theorem 1.

Let $g:\mathcal{F}\to\mathbb{R}_{+}\cup\\{\infty\\}$ be the function that maps
policy $f$ to $\mathbb{E}T(X_{1}^{f},X_{2}^{f},\ldots,X_{n}^{f})$. For
simplicity, we denote $(X_{1}^{f},X_{2}^{f},\ldots,X_{n}^{f})$ by $X^{f}$.

Define $J$ as $\inf\\{g(f)\mid f\in\mathcal{F}\\}$ which exists since $g$ is
bounded below ($g$ is non-negative). Since the set of finite strings is
countable, we can identify $\mathcal{F}$ by $[0,1]^{\mathbb{N}}$. Note that
$[0,1]$ is compact and thus, by diagonalization argument, we can find a
sequence of $(f_{i})_{i\in\mathbb{N}}$ where $f_{i}\in\mathcal{F}$ converges
to $f^{*}$ point-wisely with $\lim_{i\to\infty}g(f_{i})=J$. We have to show
$g(f^{*})=J$. By definition, we have

$\displaystyle g(f^{*})$ $\displaystyle=\mathbb{E}T(X^{f^{*}})$
$\displaystyle=\int_{0}^{\infty}\mathbb{P}(T(X^{f^{*}})\geq s)ds$
$\displaystyle=\int_{0}^{\infty}(1-\mathbb{P}(T(X^{f^{*}})<s))ds$

For a fixed $s>0$, by the definition of a reasonbale objective function, there
exists a constant $N_{s}>0$ such that $\mathbbm{1}(T(X^{f})<s)$ only depends
on the deduction of the first $N_{s}$ time slots. Since $f_{j}$ converges to
$f^{*}$ point-wisely and the set of strings $\\{w\mid|w|<N_{s}\\}$ is
finite666$|w|$ is equal to the length of the string $w$., we can choose
$\epsilon$ and $N$ so that for any $j>N$ and $w$ with $|w|<N_{s}$, we have
$|f_{j}(w)-f^{*}(w)|<\epsilon$. Then for the two policies $f_{j}$ and $f^{*}$,
the probability that the deduction of the first $N_{s}$ time slots will not
change is larger than $(1-\epsilon)^{nN_{s}}$. In fact, let $w$ be the history
of a user with $|w|<N_{s}$ and $U$ be the cell on the random board that will
be used by the user, we have
$\mathbb{P}(\mathbbm{1}(U<f(w))=\mathbbm{1}(U<f^{*}(w)))=1-|f(w)-f^{*}(w)|\geq(1-\epsilon)$.
Therefore, $\mathbb{P}(E_{k}\mid E_{k-1})\geq(1-\epsilon)^{n}$, where $E_{k}$
is the event that the deductions of the first $k$ columns are identical. We
get the estimation we want by writing out

$\displaystyle\mathbb{P}(E_{N_{s}-1})$
$\displaystyle=\mathbb{P}(E_{N_{s}-1}\mid
E_{N_{s}-2})\mathbb{P}(E_{N_{s}-2}\mid E_{N_{s}-3})\cdots\mathbb{P}(E_{1}\mid
E_{0})\mathbb{P}(E_{0})$ $\displaystyle\geq(1-\epsilon)^{nN_{s}}$

Thus, let $\Omega$ be the sample space of the random board,

$\displaystyle|\mathbb{P}(T(X^{f_{j}})<s)-\mathbb{P}(T(X^{f^{*}})<s)|$
$\displaystyle=\left|\int_{\Omega}\mathbbm{1}(T(X^{f_{j}}(w))<s)-\mathbbm{1}(T(X^{f^{*}}(w))<s)dw\right|$
$\displaystyle\leq\int_{\Omega}\left|\mathbbm{1}(T(X^{f_{j}}(w))<s)-\mathbbm{1}(T(X^{f^{*}}(w))<s)\right|dw$
$\displaystyle=\mathbb{P}\left(\mathbbm{1}\left((T(X^{f_{j}})<s\right)\neq\mathbbm{1}\left(T(X^{f^{*}})<s)\right)\right)$
$\displaystyle=1-\mathbb{P}\left(\mathbbm{1}\left((T(X^{f_{j}})<s\right)=\mathbbm{1}\left(T(X^{f^{*}})<s)\right)\right)$
$\displaystyle\leq 1-\mathbb{P}(E_{N_{s}})$ $\displaystyle\leq
1-(1-\epsilon)^{nN_{s}}$

which can be made arbitrarily small by choosing $\epsilon$ small enough. Thus
we have
$\mathbb{P}(T(X^{\lim_{j\to\infty}f_{j}})<s)=\lim_{j\to\infty}\mathbb{P}(T(X^{f_{j}})<s)$.
Therefore we have

$\displaystyle g(f^{*})$
$\displaystyle=\int_{0}^{\infty}(1-\mathbb{P}(T(X^{f^{*}})<s))ds$
$\displaystyle=\int_{0}^{\infty}(1-\lim_{j\to\infty}\mathbb{P}(T(X^{f_{j}})<s))ds$
$\displaystyle=\int_{0}^{\infty}\lim_{j\to\infty}\mathbb{P}(T(X^{f_{j}})\geq
s)ds$
$\displaystyle\leq\lim_{j\to\infty}\int_{0}^{\infty}\mathbb{P}(T(X^{f_{j}})\geq
s)ds$ $\displaystyle=J$

Note that we have used the Fatou’s Lemma [22] to change the order of
integration and the limit. We have $g(f^{*})\leq J$ but $J$ is the infimum.
Thus $f^{*}$ is an optimal policy.

∎

###  A.3 Optimal Recurrent Policies — Proof of Theorem 2

###### Proof of Theorem 2.

Let $C$ be the random variable indicating the time of the first collision. We
define $C=-1$ if there is no collision. By the definition of $f^{*}$, we know
$C^{f^{*}}=C^{f}$ since $f^{*}(w)=f(w)$ if $2_{+}\not\in w$. Also, if there is
no collision, the deduction of the two policies should be identical. Thus we
have $\mathbb{E}(T(X_{1}^{f},X_{2}^{f})\mid
C^{f}=-1)=\mathbb{E}(T(X_{1}^{f^{*}},X_{2}^{f^{*}})\mid
C^{f^{*}}=-1)=\vcentcolon M$. Let
$\mathbb{P}(C^{f}=k)=\mathbb{P}(C^{f^{*}}=k)=q_{k}$ and
$f_{k}(w)=f(0^{k}2_{+}w)$ for any $w\in\mathcal{R}^{*}$. Note that both users
must keep idle before the first collision (if there is a collision). Therefore
if the first collision happens at time $k$, after time $k$, the two users
would behave as if they have restarted the process with a new policy $f_{k}$.
Then we have,

$\displaystyle\mathbb{E}T(X_{1}^{f},X_{2}^{f})$
$\displaystyle=Mq_{-1}+\sum_{k=0}^{\infty}\mathbb{E}(T(X_{1}^{f},X_{2}^{f})\mid
C^{f}=k)q_{k}$
$\displaystyle=Mq_{-1}+\sum_{k=0}^{\infty}\mathbb{E}T(k+1+X_{1}^{f_{k}},k+1+X_{2}^{f_{k}})q_{k}$
$\displaystyle=Mq_{-1}+\sum_{k=0}^{\infty}(k+1)q_{k}+\sum_{k=0}^{\infty}\mathbb{E}T(X_{1}^{f_{k}},X_{2}^{f_{k}})q_{k}$
$\displaystyle\geq
Mq_{-1}+\sum_{k=0}^{\infty}(k+1)q_{k}+\mathbb{E}T(X_{1}^{f},X_{2}^{f})\sum_{k=0}^{\infty}q_{k}$

Note that if $\sum_{k=0}^{\infty}q_{k}=1$, then $q_{-1}=0$ and we would have
$\sum_{k=0}^{\infty}(k+1)q_{k}\leq 0$, which is impossible. Thus we must have
$\sum_{k=0}^{\infty}q_{k}<1$.

Now by the definition of $f^{*}$, we have $f^{*}(w)=f^{*}(0^{k}2_{+}w)$.
Similarly, we have

$\displaystyle\mathbb{E}T(X_{1}^{f^{*}},X_{2}^{f^{*}})$
$\displaystyle=Mq_{-1}+\sum_{k=0}^{\infty}\mathbb{E}(T(X_{1}^{f^{*}},X_{2}^{f^{*}})\mid
C^{f^{*}}=k)q_{k}$
$\displaystyle=Mq_{-1}+\sum_{k=0}^{\infty}\mathbb{E}T(k+1+X_{1}^{f^{*}},k+1+X_{2}^{f^{*}})q_{k}$
$\displaystyle=Mq_{-1}+\sum_{k=0}^{\infty}(k+1)q_{k}+\sum_{k=0}^{\infty}\mathbb{E}T(X_{1}^{f^{*}},X_{2}^{f^{*}})q_{k}$

We conclude that
$\mathbb{E}T(X_{1}^{f},X_{2}^{f})\geq\frac{Mq_{-1}+\sum_{k=0}^{\infty}(k+1)q_{k}}{1-\sum_{k=0}^{\infty}q_{k}}=\mathbb{E}T(X_{1}^{f^{*}},X_{2}^{f^{*}})$.
Since $f$ is optimal, then $f^{*}$ is also optimal. ∎

###  A.4 Proof of Corollary 1 — The Avg Objective

###### Proof of Corollary 1.

By Theorem 3, the optimal sequence $(m_{k})_{k=-1}^{\infty}$ is given by
$m_{k}=(a_{0}+a_{1}k+a_{2}k^{2})\mathbbm{1}_{k\leq N}$, for some integer
$N>0$, where

$\displaystyle a_{0}-a_{1}+a_{2}$ $\displaystyle=1$ (17) $\displaystyle
a_{0}+a_{1}N+a_{2}N^{2}$ $\displaystyle=0$ (18)

Note that by the definition, we must have $m_{k-1}\leq m_{k}$ for all
$k=0,1,\ldots,N$. We necessarily have

$\displaystyle m_{-1}\geq m_{0}\implies a_{0}-a_{1}+a_{2}\geq a_{0}$ (19)
$\displaystyle m_{N-1}\geq m_{N}\implies a_{0}+a_{1}(N-1)+a_{2}(N-1)^{2}\geq
a_{0}+a_{1}N+a_{2}N^{2}$ (20)

From Eqn. (17) and (18), we have $a_{0}=\frac{N-a_{2}(N^{2}+N)}{N+1}$ and
$a_{1}=\frac{-a_{2}(N^{2}-1)-1}{N+1}$. Insert both expressions into Eqn. (19)
and (20), we get the constraints on $a_{2}$:

$\displaystyle a_{2}\in\left[-\frac{1}{N+N^{2}},\frac{1}{N+N^{2}}\right].$
(21)

In fact, the conditions that $m_{-1}\geq m_{0}$ and $m_{N-1}\geq m_{N}$ are
sufficient for $m_{k-1}\leq m_{k}$ for all $k=0,1,\ldots,N$. To see this, let
$g(x)=a_{0}+a_{1}x+a_{2}x^{2}$ be the quadratic function where $g(k)=m_{k}$
for all $k=-1,0,1,\ldots,N$. Once we know $g(-1)\geq g(0)$ and $g(N-1)\geq
g(N)$, we know there exist $x_{1}\in[-1,0]$ and $x_{2}\in[N-1,N]$ such that
$g^{\prime}(x_{1})\leq 0$ and $g^{\prime}(x_{2})\leq 0$. Since
$g^{\prime}(x)=a_{1}+2a_{2}x$ is a linear function,
$g^{\prime}(x_{1}),g^{\prime}(x_{2})\leq 0$ implies $g^{\prime}(x)\leq 0$ for
any $x\in[x_{1},x_{2}]$. Thus $g^{\prime}(x)\leq 0$ for any $x\in[0,N-1]$. We
conclude that $m_{k-1}=g(k-1)\leq g(k)=m_{k}$ is also true for any
$k=1,\ldots,N-1$.

Using Eqn. (4) derived in Theorem 3, we have

$\displaystyle\mathbb{E}X_{1}$
$\displaystyle=\frac{\sum_{k=-1}^{N-1}(a_{0}+a_{1}k+a_{2}k^{2})}{1-\sum_{k=0}^{N}(-a_{1}+a_{2}(-2k+1))^{2}}$
$\displaystyle=\frac{(N+1)(N+2)(a_{2}N(N+1)-3)}{2N\left(a_{2}^{2}(N+1)^{2}(N+2)-3\right)}$
(22)

Fixing $N$, to minimize $\mathbb{E}X_{1}$, we have

$\displaystyle\frac{\partial\mathbb{E}X_{1}}{\partial
a_{2}}=-\frac{(N+1)^{2}(N+2)(a_{2}^{2}N(N+2)(N+1)^{2}-6a_{2}(N+2)(N+1)+3N)}{2N\left(a_{2}^{2}(N+1)^{2}(N+2)-3\right)^{2}}=0$

Then
$a_{2}=\frac{3N^{2}+9N+6\pm\sqrt{3}\sqrt{-N^{5}-N^{4}+13N^{3}+37N^{2}+36N+12}}{N^{4}+4N^{3}+5N^{2}+2N}.$
It is easy to check that $a_{2}$ becomes complex for all $N\geq 5$, which
implies $\frac{\partial\mathbb{E}X_{1}}{\partial a_{2}}\leq 0$ for any
$a_{2}$. That is to say for $N\geq 5$, the larger $a_{2}$ is, the smaller
$\mathbb{E}X_{1}$ is. Thus the best $a_{2}$ one can pick under the constraint
(21) is $\frac{1}{N+N^{2}}$. In this case, by inserting
$a_{2}=\frac{1}{N+N^{2}}$ into Eqn. (22) we have

$\displaystyle\mathbb{E}X_{1}$
$\displaystyle=\frac{(N+1)(N+2)(1-3)}{2N\left(\frac{N+2}{N^{2}}-3\right)}$
$\displaystyle=\frac{N(N+1)(N+2)}{3N^{2}-N-2}.$ (23)

Then we differentiate Eqn. (23) by $N$:

$\displaystyle\frac{\partial\mathbb{E}X_{1}}{\partial
N}=\frac{1}{15}\left(-\frac{8}{(3N+2)^{2}}-\frac{18}{(N-1)^{2}}+5\right)>0$

for $N\geq 5$. Therefore, in the case where $N\geq 5$, it it best to choose
$N=5$, yielding
$\mathbb{E}X_{1}=\frac{N(N+1)(N+2)}{3N^{2}-N-2}=\frac{105}{34}\approx 3.09$.

Now we consider the cases where $N\in\\{1,2,3,4\\}$. We give the optimal
results for each case in the Table 4. Note that we have
$a_{2}\in[-\frac{1}{N+N^{2}},\frac{1}{N+N^{2}}]$ for each $N$.

$N$ |  $\mathbb{E}X_{1}$ (Eqn. (22)) | optimal $a_{2}$ | optimal $\mathbb{E}X_{1}$
---|---|---|---
$1$ | $\displaystyle\frac{3-2a_{2}}{1-4a_{2}^{2}}$ | $\displaystyle\frac{3}{2}-\sqrt{2}$ | $\displaystyle\sqrt{2}+\frac{3}{2}\approx 2.91421$
$2$ | $\displaystyle\frac{3-6a_{2}}{1-12a_{2}^{2}}$ | $\displaystyle\frac{1}{2}-\frac{1}{\sqrt{6}}$ | $\displaystyle\frac{1}{2}(\sqrt{6}+3)\approx 2.72474$
$3$ | $\displaystyle\frac{10-40a_{2}}{3-80a_{2}^{2}}$ | $\displaystyle\frac{1}{12}$ | $\displaystyle\frac{30}{11}\approx 2.72727$
$4$ | $\displaystyle\frac{5\left(20a_{2}-3\right)}{200a_{2}^{2}-4}$ | $\displaystyle\frac{1}{20}$ | $\displaystyle\frac{20}{7}\approx 2.85714$
Table 4: Solutions for $N\in\\{1,2,3,4\\}$

Combining all previous results we conclude that a globally optimal algorithm
that minimizes the average waiting time of a two-party contention is obtained
when $N=2$ and $a_{2}=\frac{1}{2}-\frac{1}{\sqrt{6}}$. In this case, we have
$a_{0}=\frac{N-a_{2}(N^{2}+N)}{N+1}=\frac{1}{3}(\sqrt{6}-1)$ and
$a_{1}=\frac{-a_{2}(N^{2}-1)-1}{N+1}=\frac{\sqrt{6}-5}{6}$. Then we have
$m_{0}=a_{0}=\frac{1}{3}(\sqrt{6}-1)$,
$m_{1}=a_{0}+a_{1}+a_{2}=\frac{1}{3}(\sqrt{6}-2)$ and $m_{2}=0$. Finally we
get the optimal probability sequence.

$\displaystyle p_{0}=1-m_{0}=\frac{4-\sqrt{6}}{3}\approx 0.516837,$
$\displaystyle p_{1}=1-\frac{m_{1}}{m_{0}}=\frac{1+\sqrt{6}}{5}\approx
0.689898,$ $\displaystyle p_{2}=1-\frac{m_{2}}{m_{1}}=1.$

This is precisely the avg-Contention Resolution protocol. ∎

###  A.5 Proof of Corollary 2 — The Max Objective

###### Proof of Corollary 2.

We continue to use all the derived results in Theorem 5. Remember that $x_{1}$
and $x_{2}$ depend on $\gamma$, and satisfy the equalities
$x_{1}+x_{2}=2-\gamma$ and $x_{1}x_{2}=1$. Recall that
$1/\gamma=\mathbb{E}\max(X_{1},X_{2})$. Using the fact that $m_{-1}=1$, it
follows from Eqn. (11) that $\gamma$ can be written as

$\displaystyle\gamma$
$\displaystyle=\frac{1-\sum_{k=0}^{N+1}(m_{k-1}-m_{k})^{2}}{1+2\sum_{k=0}^{N}m_{k}-\sum_{k=0}^{N}m^{2}_{k}}$
$\displaystyle=\frac{1-(1-m_{0})^{2}-\sum_{k=0}^{N}\left(C_{1}x_{1}^{k}(1-x_{1})+C_{2}x_{2}^{k}(1-x_{2})\right)^{2}}{1+2\sum_{k=0}^{N}\left(C_{1}x_{1}^{k}+C_{2}x_{2}^{k}+1\right)-\sum_{k=0}^{N}\left(C_{1}x_{1}^{k}+C_{2}x_{2}^{k}+1\right)^{2}}$
Since $x_{1}x_{2}=1$, this can be written as follows.
$\displaystyle=\frac{1-(1-m_{0})^{2}-\sum_{k=0}^{N}\left(C_{1}^{2}\left(1-x_{1}\right)^{2}\left(x_{1}^{2}\right)^{k}+2C_{1}C_{2}(1-x_{1})(1-x_{2})+C_{2}^{2}(1-x_{2})^{2}\left(x_{2}^{2}\right)^{k}\right)}{N+2-\sum_{k=0}^{N}\left(C_{1}^{2}\left(x_{1}^{2}\right)^{k}+C_{2}^{2}\left(x_{2}^{2}\right)^{k}+2C_{1}C_{2}\right)}$

By organizing the terms we have (using identities (15), (16), the polynomial
(10) that defines $x_{1}$ and $x_{2}$ and the definition
$m_{k}=C_{1}x_{1}^{k}+C_{2}x_{2}^{k}+1$)

$\displaystyle 0$
$\displaystyle=\gamma(N+2)-1+(1-m_{0})^{2}-2(N+1)C_{1}C_{2}(-(1-x_{1})(1-x_{2})+\gamma)$
$\displaystyle\hskip
28.45274pt+C_{1}^{2}\left((1-x_{1})^{2}-\gamma\right)\sum_{k=0}^{N}\left(x_{1}^{2}\right)^{k}+C_{2}^{2}\left((1-x_{2})^{2}-\gamma\right)\sum_{k=0}^{N}\left(x_{2}^{2}\right)^{k}$
Using the fact that $(1-x_{1})(1-x_{2})=2-(x_{1}+x_{2})=\gamma$ and that
$-\gamma(1+x_{1})=(x_{1}+x_{2}-2)(1+x_{1})=x_{1}^{2}-x_{1}-1+x_{2}=(1-x_{1})^{2}-2+x_{1}+x_{2}=(1-x_{1})^{2}-\gamma$,
we can simplify this as follows.
$\displaystyle=\gamma(N+2)-1+(1-m_{0})^{2}-C_{1}^{2}\gamma(1+x_{1})\sum_{k=0}^{N}\left(x_{1}^{2}\right)^{k}-C_{2}^{2}\gamma(1+x_{2})\sum_{k=0}^{N}\left(x_{2}^{2}\right)^{k}$
$\displaystyle=\gamma(N+2)-1+(1-m_{0})^{2}-C_{1}^{2}\gamma\frac{1-\left(x_{1}^{2}\right)^{N+1}}{1-x_{1}}-C_{2}^{2}\gamma\frac{1-\left(x_{2}^{2}\right)^{N+1}}{1-x_{2}}$
We will now put the last two terms under the common denominator
$(1-x_{1})(1-x_{2})=\gamma$, thereby cancelling the $\gamma$ factors in both
terms. $\displaystyle=\gamma(N+2)-1+(1-m_{0})^{2}$ $\displaystyle\hskip
28.45274pt-\left(C_{1}^{2}+C_{2}^{2}-C_{1}^{2}x_{2}-C_{2}^{2}x_{1}-C_{1}^{2}x_{1}^{2(N+1)}-C_{2}^{2}x_{2}^{2(N+1)}+C_{1}^{2}x_{1}^{2N+1}+C_{2}^{2}x_{2}^{2N+1}\right)$
Since $m_{0}=C_{0}+C_{1}+1$, we have $\displaystyle=\gamma(N+2)-1+2C_{1}C_{2}$
$\displaystyle\hskip
28.45274pt-(-C_{1}^{2}x_{2}-C_{2}^{2}x_{1}-C_{1}^{2}x_{1}^{2(N+1)}-C_{2}^{2}x_{2}^{2(N+1)}+C_{1}^{2}x_{1}^{2N+1}+C_{2}^{2}x_{2}^{2N+1})$
$\displaystyle=\gamma(N+2)-1+(m_{N+1}-1)^{2}-(-C_{1}^{2}x_{2}-C_{2}^{2}x_{1}+C_{1}^{2}x_{1}^{2N+1}+C_{2}^{2}x_{2}^{2N+1})$
$\displaystyle=\gamma(N+2)-1+(m_{N+1}-1)^{2}-(m_{N}-1)(m_{N+1}-1)+(m_{0}-1)(m_{-1}-1)$
Note that we have $m_{-1}=1$ and $m_{N+1}=0$, hence
$\displaystyle=\gamma(N+2)+m_{N}-1.$

Rearranging terms, we have:

$\displaystyle N$ $\displaystyle=\frac{1-m_{N}}{\gamma}-2<2$ (24)

The last inequality follows from the fact that $m_{N}\in(0,1]$ and
$\frac{1}{\gamma}\in[3,4]$. Thus the only possible values of $N$ are $0$ and
$1$.

If $N=0$, we have the following set of equations. 777We have used the algebra
software _Mathematica_ to give the exact form of the solutions for both cases.

$\displaystyle\gamma(N+2)+m_{N}-1=2\gamma+C_{1}+C_{2}$ $\displaystyle=0$
$\displaystyle C_{1}x_{1}^{-1}+C_{2}x_{2}^{-1}+1$ $\displaystyle=1$
$\displaystyle(m_{-1}=1)$ $\displaystyle C_{1}x_{1}+C_{2}x_{2}+1$
$\displaystyle=0$ $\displaystyle(m_{1}=0)$

whose solution is $\gamma=\frac{2-\sqrt{2}}{2}$ where $\frac{1}{\gamma}\approx
3.41421$.

If $N=1$, we have the following set of equations.

$\displaystyle\gamma(N+2)+m_{N}-1=3\gamma+C_{1}x_{1}+C_{2}x_{2}$
$\displaystyle=0$ (25) $\displaystyle C_{1}x_{1}^{-1}+C_{2}x_{2}^{-1}+1$
$\displaystyle=1$ $\displaystyle(m_{-1}=1)$ (26) $\displaystyle
C_{1}x_{1}^{2}+C_{2}x_{2}^{2}+1$ $\displaystyle=0$ $\displaystyle(m_{2}=0)$
(27)

whose solution gives

$\gamma\approx 0.299723,\text{ where }3\gamma^{3}-12\gamma^{2}+10\gamma-2=0$

We see in this case $\frac{1}{\gamma}\approx 3.33641$, which is better than
the case where $N=0$. The corresponding $C_{1}\approx-0.264419-0.426908i$ and
$C_{2}\approx-0.264419+0.426908i$, which are a pair of conjugate roots of
polynomial $76x^{6}-532x^{5}+664x^{4}+3288x^{3}+4680x^{2}+2268x+729$.

Finally we get

$\displaystyle p_{0}=1-m_{0}=-C_{1}-C_{2}=\alpha\approx 0.528837,\text{ where
}\alpha^{3}+7\alpha^{2}-21\alpha+9=0,$ $\displaystyle
p_{1}=1-\frac{m_{1}}{m_{0}}=1-\frac{C_{1}x_{1}+C_{2}x_{2}+1}{C_{1}+C_{2}+1}=\beta\approx
0.785997,\text{ where }4\beta^{3}-8\beta^{2}+3=0,$ $\displaystyle
p_{2}=1-\frac{m_{2}}{m_{1}}=1.$

This is precisely the max-Contention Resolution protocol. ∎