Excuse me! or the courteous theatregoers' problem

DOI10.1016/J.TCS.2015.01.053MaRDI QIDQ2347004zbMATH OpenOpenAlexFDO

Authors Konstantinos Georgiou, Evangelos Kranakis, D. Krizanc

Publication date 26 May 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.1988

zbMATH Keywords

courteousgeometric distributionselfishtheatre occupancytheatregoersuniform distributionZipf distribution

Mathematics Subject Classification ID

Combinatorial probability (60C05)

Abstract: Consider a theatre consisting of $m$ rows each containing $n$ seats. Theatregoers enter the theatre along aisles and pick a row which they enter along one of its two entrances so as to occupy a seat. Assume they select their seats uniformly and independently at random among the empty ones. A row of seats is narrow and an occupant who is already occupying a seat is blocking passage to new incoming theatregoers. As a consequence, occupying a specific seat depends on the courtesy of theatregoers and their willingness to get up so as to create free space that will allow passage to others. Thus, courtesy facilitates and may well increase the overall seat occupancy of the theatre. We say a theatregoer is courteous if (s)he will get up to let others pass. Otherwise, the theatregoer is selfish. A set of theatregoers is $p$-courteous if each theatregoer in the set is courteous with probability $p$, randomly and independently. It is assumed that the behaviour of a theatregoer does not change during the occupancy of the row. In this paper, we are interested in the following question: what is the expected number of occupied seats as a function of the total number of seats in a theatre, $n$, and the probability that a theatregoer is courteous, $p$? We study and analyze interesting variants of this problem reflecting behaviour of the theatregoers as entirely selfish, and $p$-courteous for a row of seats with one or two entrances and as a consequence for a theatre with $m$ rows of seats with multiple aisles. We also consider the case where seats in a row are chosen according to the geometric distribution and the Zipf distibrution (as opposed to the uniform distribution) and provide bounds on the occupancy of a row (and thus the theatre) in each case.

Recommendations

• scientific article; zbMATH DE number 3875286
• ``All the world's a stage: incongruity humour revisited
• Problem-posing: a look behind the scenes
• Polite theories revisited
• The kissing problem: how to end a gathering when everyone kisses everyone else goodbye

Cites work

• A Markov chain model for the kinetics of reactant isolation
• Combinatorics of bicubic maps with hard particles
• Critical and tricritical hard objects on bicolourable random lattices: exact solutions
• scientific article; zbMATH DE number 3863589 (Why is no real title available?)
• scientific article; zbMATH DE number 1178976 (Why is no real title available?)
• Maintaining privacy on a line
• Planar lattice gases with nearest-neighbor exclusion
• Probability and Computing
• Random maximal independent sets and the unfriendly theater seating arrangement problem
• Randomized greedy matching
• Randomized greedy matching. II
• Several constants arising in statistical mechanics
• The Number of Independent Sets in a Grid Graph

Cited in

(1)

• Coverage fluctuations in theater models

This page was built for publication: Excuse me! or the courteous theatregoers' problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2347004)