Tag Archives: Union College

Mathematicians, political scientists, and cake cutting

Leave a reply

If you have a sibling, you’ve likely fought at least once over who got the biggest or ‘best’ piece of cake.  (I do and I did.) In any event, it seems that mathematicians and political scientists have been working on a scheme to avoid disputes over cake.

[downloaded from http://link.springer.com/article/10.1007%2Fs00283-013-9442-0#page-1]

A July 16, 2014 Springer news release (also on EurekAlert) describes the quest for fairly sized cake slices and how that might apply to real life issues such as sharing property,

The next time your children quibble about who gets to eat which part of a cake, call in some experts on the art of sharing. Mathematician Julius Barbanel of Union College, and political scientist Steven Brams of New York University, both in the US, published an algorithm in Springer’s The Mathematical Intelligencer by which they show how to optimally share cake between two people efficiently, in equal pieces and in such a way that no one feels robbed.

The cut-and-choose method to share divisible goods has been regarded as fair and envy-free since Biblical times, when Abraham divided land equally, and Lot could choose the part he wanted. But being free of envy is not the only consideration when sharing something. What happens when more than two cuts can be made, or when people prefer different, specific sections of whatever is to be divided? Barbanel and Brams believe that with a giveback procedure it is possible to make a perfect division between two people that is efficient, equitable and void of jealousy.

An objective referee (such as a Mom or a computer) is essential to the plan. The potential cake eaters first tell the referee which parts of the delicacy they value most. In mathematical terms these are called someone’s probability density functions, or pdfs. The referee then marks out the cake at all points were the pdfs of the disgruntled would-be cake eaters cross, and assigns portions. If at this point the two parties receive the same size of cake, the task is over. If not, the giveback process starts.

The party who received the larger part of the cake during the first round must give a part of it back to the other person, starting with those parts in which the ratio of their pdfs is the smallest. This goes on until the parties value their portions equally, and have the same volume of cake to eat. This method only works with a finite number of cuts if the players’ pdfs are straight-lined, or are so-called piecewise linear sections.

The researchers believe the method can be used to share cake and other divisible goods such as land. In the case of beachfront property being co-owned by two developers, for example, it can help to determine who gets what strips of land to build on based on the pieces of land they value most.

“This allocation is not only equitable but also envy-free and efficient – that is, perfect,” says Barbanel.

“This approach focuses on proving the existence of efficient and envy-free divisions, not on providing algorithms to finding them,” emphasizes Brams.

Here’s a link to and a citation for the paper,

Two-Person Cake Cutting: The Optimal Number of Cuts by Julius B. Barbanel and Steven J. Brams. The Mathematical Intelligencer March 2014 DOI 10.1007/s00283-013-9442.

This paper is behind a paywall although there is a free preview available and a special summer discount (30%) on the purchase price until July 31, 2014.

Frozen smoke from Union College (New York state)

Leave a reply

I’m always a sucker for a good metaphor or analogy and this February 3, 2014 news item on ScienceDaily nicely fit the bill,

One day, Union College’s [New York state] Aerogel Team’s novel way of making “frozen smoke” could improve some of our favorite machines, including cars.

“When you hold aerogel it feels like nothing — like frozen smoke. It’s about 95 to 97 percent air,” said Ann Anderson, professor of mechanical engineering. “Nano-porous, solid and very low density, aerogel is made by removing solvents from a wet-gel. It’s used for many purposes, like thermal insulation (on the Mars Rover), in windows or in extreme-weather clothing and sensors.”

It seems the researchers have developed a new technique for fabricating aerogel which they are wanting to commercialize (from a Feb. 2014 [?] news release originally published as an article in the Union College Magazine’s Fall 2013 issue),

Together with Brad Bruno, Mary Carroll and others, Anderson is studying the feasibility of commercializing their aerogel fabrication process. A time and money-saver, it could appeal to industries already using aerogel made in other ways.

During rapid supercritical extraction (RSCE), chemicals gel together (like Jell-O) in a hot press; the resulting wet-gel is dried by removing solvents (the wet part). The remaining aerogel (dried gel), is created in hours, rather than the days or weeks alternative methods take.

RSCE, Anderson said, is also approximately seven times cheaper, requiring one hour of labor for every 8 hours the other methods need.

A good place for such a process, and Union aerogel, is the automotive industry.

“Our 3-way catalytic aerogels promote chemical reactions that convert the three major pollutants in automotive exhaust – unburned hydrocarbons, nitrogen oxides and carbon monoxide – into less harmful water, nitrogen and carbon dioxide,” Anderson said. “Because aerogels have very high surface areas and good thermal properties, we think they could replace precious metals, like platinum, used in current catalytic converters.”

Indeed, the surface area of one 0.5-gram bit of aerogel equals 250 square meters.

“That’s a lot of surface area for gases to come in contact with, facilitating very efficient pollution mitigation,” Anderson said.

I have mentioned aerogel before in several postings including this Aug. 20, 2012 posting titled: Solid smoke; a new generation of aerogels.