Shared Dessert
October 30, 2023
There's much
wisdom in the
adages carved into the
plaques that
festoon the
walls of
country stores. The most important adages are rendered in
song, as in the 1969 song by
The Rolling Stones, "
You Can't Always Get What You Want."[1] The song's
recording is unusual in opening with the
The Bach Choir, whose present
patron is
King Charles III.
Everyday life is all about
compromise. A trip to the local
supermarket involves such things as the difficult
choice of which
spaghetti sauce to select from so many
options to minimize
complaints from
family members. One of the most important daily
decisions in both my
graduate school days and my days
working in a large
corporate research center was deciding with my
colleagues where to have
lunch. In the
sciences, the typically
eclectic mix of
nationalities makes this decision much more difficult.
A plate of American Chinese food.
A Chinese colleague once convinced us to have lunch at an authentic Chinese restaurant. The menu was in Chinese; so, selection was difficult.
One participant asked about chicken and was directed to a particular item. He was quite surprised when he was served a plate of chicken feet.
(Wikimedia Commons image (modified) by Suiren2022.)
One area of
personal compromise involves the
fair scheduling for
drivers in a
carpool. An
equitable arrangement would be one in which carpool participants just
consecutively cycled through
days, and there would be no problems. However, some participants will miss driving days, or even
weeks, as a
consequence of
business travel,
vacations,
illness,
religious holidays, or
vacations. The first
paper on this scheduling topic is the 1983 paper, "A Fair Carpool Scheduling Algorithm," by Ronald Fagin and John H. Williams of
IBM.[2] This paper is a
classic, and it has tens of thousands of
citations.
The essential problem is who should drive on those days when the designated driver is away; and, how would this absent driver repay his colleagues for his lack of service on those days. The paper proposes an
economic model that uses a
balance sheet in which driving is considered to have a
fixed cost. To keep
accounting in the
integer realm, this cost
U is a number that's the
least common multiple of the number of carpool participants; that is, in a carpool with 4 participants,
U would be 12, a number that's divisible by 1, 2, 3, and 4.[2]
If a particular trip has
k participants, the participants who are not drivers need to "
pay" the driver
U/k units, and everyone's personal account is updated on the balance sheet. The balance sheet will always indicate which participant has the smallest amount in his/her account, and that person should be the next driver.[2] From my own experience in
New Jersey, nearly every
vehicle on the
road at
rush hour has a single
occupant, and such an
algorithm would seldom be used.
I haven't seen a sign like this in more than a decade.
It may have mitigated global warming to some extent, but much more than this is needed at this time.
(United States Department of Transportation image.[3])
Among what are called, "
first world problems," is the problem of equitably selecting a
dessert item, such as a type of
cake, for a group to share. A recent paper on
arXiv throws a lot of
mathematics at this problem, which is essentially a problem in
ranked choice voting.[4] Since I've been doing
experimental mathematics long before I discovered the term, I decided to address this problem with a
computer simulation.
Within a possible selection of
n dessert items, each participant
p will have a declining
preference from his first choice to his last choice. For
convenience, let's say that his second choice is 80% less desirable than his first choice, his third choice is 80% less desirable than his second choice, etc.. For each dessert choice we can
sum over the preferences for all participants to get an overall
satisfaction. Our dessert choice will be the dessert item that gives the greatest total satisfaction.
Some participants in a large group will get their lowest ranked choice; so, you can't always get what you want. However, who can complain about any dessert item. The
source code for my simulation program, written in the
C programming language, can be downloaded as
this zip file that also includes a
statistical analysis program. An essential part of the program is the generation of all the
permutations of the choices and assignment of a
random permutation to each participant. The following
graphs show some results of the simulation. This method can be easily made into into a
smartphone app, which would be the perfect
companion to a
tip calculator. However, the presumed
target audience of
technophiles is limited.
Values of satisfaction for five dessert choices and 2, 3, 4, 5, and 10 participants as determined by my computer simulation.
As expected, two participants will have a high overall satisfaction when the optimum dessert choice is made. Many participants results in a lower overall satisfaction.
(Created using Gnumeric. Click for larger image.)
Percentage of participant's ranked choice for five dessert choices when ten participants are involved.
With the optimum dessert choice, about a third of participants get their first choice, and only one out of ten gets his last choice. There appears to be a linear trend.
(Created using Gnumeric.)
References:
- The Rolling Stones, "You Can't Always Get What You Want (Remastered 2019)," YouTube video by Universal Music Group, October 31, 2019.
- R. Fagin and J. H. Williams, "A Fair Carpool Scheduling Algorithm," IBM Journal of Research and Development, vol. 27, no. 2 (1983), pp. 133 ff..
- Manual on Uniform Traffic Control Devices for Streets and Highways, Page 256, Figure 2G-1, Preferential Lane Regulatory Signs and Plaques, May 15, 2023.
- Tanya Khovanova and Daniel A. Klain, "What's for dessert?," arXiv, August 30, 2023, https://doi.org/10.48550/arXiv.2308.16324.
Linked Keywords: Wisdom; proverb; adage; carving; carved; plaque; festoon; wall; general store; country store; song; The Rolling Stones; You Can't Always Get What You Want; sound recording; The Bach Choir; patronage; patron; King Charles III; everyday life; compromise; supermarket; choice; Neapolitan sauce; spaghetti sauce; option; complaining; complaint; family member; decision-making; decision; graduate school; employment; working; corporation; corporate; research center; colleague; lunch; science; eclectic mix; nationality; plate (dishware); America; American; Chinese cuisine; Chinese food; Chinese people; authentic; Chinese restaurant; menu; Chinese language; chicken; surprise (emotion); surprised; foot; feet; Wikimedia Commons; Suiren2022; individualism; personal; social justice; fair; schedule; driving; driver; carpool; equitable; consecutive; consecutively; periodic sequence; cycle; day; week; logical consequence; business travel; vacation; disease; illness; religious holiday; vacation; scientific literature; paper; IBM; classic; citation; economic model; balance sheet; fixed cost; accounting; integer realm; least common multiple; wage; pay; New Jersey; vehicle; road; rush hour; occupant; algorithm; traffic sign; decade; mitigation; mitigate; global warming; United States Department of Transportation; first world problem; dessert; cake; arXiv; mathematics; ranked choice voting; experimental mathematics; computer simulation; preference; convenience; addition; sum; contentment; satisfaction; source code; C programming language; dessert choice.zip; zip file; statistics; statistical analysis; permutation; randomness; random; Cartesian coordinate system; graph; smartphone; mobile app; companion; gratuity; tip; calculator; target audience; technophilia; technophile; mathematical optimization; optimum; Gnumeric; percentage; linear regression; linear trend.