Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Thue–Morse sequence
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
===Equitable sequencing=== In their book on the problem of [[fair division]], [[Steven Brams]] and [[Alan D. Taylor|Alan Taylor]] invoked the Thue–Morse sequence but did not identify it as such. When allocating a contested pile of items between two parties who agree on the items' relative values, Brams and Taylor suggested a method they called ''balanced alternation'', or ''taking turns taking turns taking turns . . . '', as a way to circumvent the favoritism inherent when one party chooses before the other. An example showed how a divorcing couple might reach a fair settlement in the distribution of jointly-owned items. The parties would take turns to be the first chooser at different points in the selection process: Ann chooses one item, then Ben does, then Ben chooses one item, then Ann does.{{sfnp|Brams|Taylor|1999}} [[Lionel Levine]] and [[Katherine E. Stange]], in their discussion of how to fairly apportion a shared meal such as an [[Ethiopian cuisine|Ethiopian dinner]], proposed the Thue–Morse sequence as a way to reduce the advantage of moving first. They suggested that “it would be interesting to quantify the intuition that the Thue–Morse order tends to produce a fair outcome.”{{sfnp|Levine|Stange|2012}} Robert Richman addressed this problem, but he too did not identify the Thue–Morse sequence as such at the time of publication.<ref name="richman">{{harvtxt|Richman|2001}}</ref> He presented the sequences [[#Characterization using bitwise negation|''T<sub>n</sub>'']] as [[step function]]s on the interval [0,1] and described their relationship to the [[Walsh function|Walsh]] and [[Hans Rademacher|Rademacher]] functions. He showed that the ''n''th [[derivative]] can be expressed in terms of ''T<sub>n</sub>''. As a consequence, the step function arising from ''T<sub>n</sub>'' is [[Orthogonality|orthogonal]] to [[polynomial]]s of [[Degree of a polynomial|order]] ''n'' − 1. A consequence of this result is that a resource whose value is expressed as a [[Monotonic function|monotonically]] decreasing [[continuous function]] is most fairly allocated using a sequence that converges to Thue–Morse as the function becomes [[Flat function|flatter]]. An example showed how to pour cups of [[Drip brew|coffee]] of equal strength from a carafe with a [[Nonlinear system|nonlinear]] [[concentration]] [[gradient]], prompting a whimsical article in the popular press.{{sfnp|Abrahams|2010}} Joshua Cooper and Aaron Dutle showed why the Thue–Morse order provides a fair outcome for discrete events.<ref name="cooper">{{harvtxt|Cooper|Dutle|2013}}</ref> They considered the fairest way to stage a [[Évariste Galois|Galois]] duel, in which each of the shooters has equally poor shooting skills. Cooper and Dutle postulated that each dueler would demand a chance to fire as soon as the other's [[a priori probability|''a priori'' probability]] of winning exceeded their own. They proved that, as the duelers’ hitting probability approaches zero, the firing sequence converges to the Thue–Morse sequence. In so doing, they demonstrated that the Thue–Morse order produces a fair outcome not only for sequences [[#Characterization using bitwise negation|''T<sub>n</sub>'']] of length ''2<sup>n</sup>'', but for sequences of any length. Thus the mathematics supports using the Thue–Morse sequence instead of alternating turns when the goal is fairness but earlier turns differ monotonically from later turns in some meaningful quality, whether that quality varies continuously<ref name="richman" /> or discretely.<ref name="cooper" /> Sports competitions form an important class of equitable sequencing problems, because strict alternation often gives an unfair advantage to one team. [[Ignacio Palacios-Huerta]] proposed changing the sequential order to Thue–Morse to improve the ''[[ex post]]'' fairness of various tournament competitions, such as the kicking sequence of a [[Penalty shoot-out (association football)#Procedure|penalty shoot-out]] in soccer.{{sfnp|Palacios-Huerta|2012}} He did a set of field experiments with pro players and found that the team kicking first won 60% of games using ABAB (or ''T''<sub>1</sub>), 54% using ABBA (or ''T''<sub>2</sub>), and 51% using full Thue–Morse (or ''T''<sub>n</sub>). As a result, ABBA is undergoing [[Penalty shoot-out (association football)#Advantage to team kicking first?|extensive trials]] in [[FIFA#FIFA competitions|FIFA (European and World Championships)]] and English Federation professional soccer ([[EFL Cup]]).{{sfnp|Palacios-Huerta|2014}} An ABBA serving pattern has also been found to improve the fairness of [[Tennis scoring system#Scoring a tiebreak game|tennis tie-breaks]].{{sfnp|Cohen-Zada|Krumer|Shapir|2018}} In [[Rowing (sport)|competitive rowing]], ''T''<sub>2</sub> is the only arrangement of [[Port and starboard|port- and starboard-rowing]] crew members that eliminates transverse forces (and hence sideways wiggle) on a four-membered coxless racing boat, while ''T''<sub>3</sub> is one of only four [[Boat rigging|rigs]] to avoid wiggle on an eight-membered boat.{{sfnp|Barrow|2010}} Fairness is especially important in [[Draft (sports)|player drafts]]. Many professional sports leagues attempt to achieve [[Parity (sports)|competitive parity]] by giving earlier selections in each round to weaker teams. By contrast, [[Fantasy football (American)|fantasy football leagues]] have no pre-existing imbalance to correct, so they often use a “snake” draft (forward, backward, etc.; or ''T''<sub>1</sub>).<ref>{{cite web |url=http://www.nfl.com/fantasyfootball/help/drafttypes |archive-url=https://web.archive.org/web/20181012053900/http://www.nfl.com/fantasyfootball/help/drafttypes |archive-date=October 12, 2018 |title=Fantasy Draft Types |work=[[National Football League|NFL.com]]}}</ref> Ian Allan argued that a “third-round reversal” (forward, backward, backward, forward, etc.; or ''T''<sub>2</sub>) would be even more fair.<ref>{{cite web |first=Ian |last=Allan |url=https://www.fantasyindex.com/2014/07/16/fantasy-news/third-round-reversal-drafts |title=Third-Round Reversal Drafts |date=July 16, 2014 |work=Fantasy Index |access-date=September 1, 2020}}</ref> Richman suggested that the fairest way for “captain A” and “captain B” to choose sides for a [[Streetball|pick-up game of basketball]] mirrors ''T''<sub>3</sub>: captain A has the first, fourth, sixth, and seventh choices, while captain B has the second, third, fifth, and eighth choices.<ref name="richman" />
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)