Tikalon Blog by Dev Gualtieri

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 satisfaction of dessert choice depending on the number of participants.

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.)

Percentange of participant's rank choice for five dessert choices.

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.)

Shared Dessert

References: