Note on Equitable Round-Robin Tournaments

(1)

2−F−8

2001年度日本オペレーションズ・リサーチ学会秋季研究発表会

NoteonEquitableRound−RobinTournaments

O2602190 UniversityofTokyo ＊MIYASHIRORyuhei

O1605000 UniversityofTbkyo MATSUITbmomi

（HAT），Whichexpressesstadiumassignment・In HAT，ahome−gameOftheteamcorresponding totherowisrepresentedby’H’，andaway−game by’A，．Home−aWayPattern（HA−pattern）is a rowofHAT．Figure2isHATcorrespondingto Figurel・ 1 2 3 4 5 1．Introduction

Around−rObintournamentisapopulartour−

namenttypeforsportscompetition，andoften heldwithstadiumasslgnment．Inthetourna− ment，eVeryteamhasitshomestadium．Inthis

paper，We COnSider around robintournament withstadiumasslgnmentCOnSistingof2Nteam− sand2N−1slots（Figurel）． 1 2 3 4 5 A一A H一A H A H H H一A H一H A一A H A A H H A 1 2 3 4 5 6 H A一A 45回口］［且3 2［山［且3回5 6同］［且2 1 2 H ［且2回1 A 皇 H H 3 4 A H Figure2・HATcorrespondingtoFig・1 Ifthereexistsaschedulecorrespondingtoa

given HAT，the HATis calledfeasible・Note that thereareirホasibleHAT，i．e．，HATwhich

doesnotcorrespondtoanyschedules．

When there are consecutive‘A，s or（H†sina

particularHA−pattern，WeSaytheHA−pattern hasabreak．Asabove，WeeXPreSSabreakby lineunderlatter’A’or’H，inHA−Pattern． Ingeneral，playersofateamlikeahome−game

ratherthananaway−game・HA−patterninclud−

1ngCOnSeCutive’A’s，e．g・“A皇AAHAH”，isnot desirableforanyteams．HA−patternWhichcon− tainsconsecutive‘H’sisnotpreferableneither． Theorganizerusuallywantstoreducethenum− berofbreaksinHAT．

Itis already known that existence ofHAT

with2N breaks［1］．We callsuch HAT equi−

lable HAT．Henceforth，We COnSider equitable

HATsinceequitableHAThavegoodproperties intermsoffairnesstoallteams［2］・ Inaddition，WerequirethatHATmustsatisfy

fo1lowlngCOnditionsforapracticalreason・Ina

round−rObintournamentconsistingof2Nteams 3［司

口回

5 6 Fig11rel．Round−RobinTburnament InFigurel，eVeryGOlumnshowsgamesona slotandeveryrowshowsopponentsofateam． Eachgameisheldatoneofthehomegrounds Ofthe correspondingpalrOfteams．Ifagame between teamsiand jis played at the home

groundofi，thegameisahome−9ameforiand

an away−9amefor］・Boxed cellsin Figurel

denoteaway−gameS Ofthe team corresponding

to the row．

Stadiumasslgnmenthasaseriouseffbctona

resultofthetournament．Therefore，atOurna−

mentorganizerwouldliketoconstructstadium asslgnmentin order to satisfyrequired condi−

tions．Inthis paper，We COnSider stadium as−

Slgnmentintermsoffairnesstoallteams・We

StateSeVeralconditionsfor“good”stadiumas−

(2)

HAThaveexactlyonebreak．Ifx，yandzsatis− fytheconditionsthatxhas‘A’onslotss，S＋1，y has’A，onslotss＋1，S＋2，andzhas’A’onslots

s＋2，S＋3ataslots∈（1，2，…，2N−4），thenit

isnotdifRculttoshowthatthegivenHATisin− feasible．Theabove constraintiscalleda

break constraint．By applyingthis constraint，

the number ofcandidates offeasible HAT de−

creases drastically（Tablel）・ThenwesoIved

theIP problemstocheckfeasibilityofthere−

mained HAT．

Tablel．NumberoffeasibleHAT

＃teams ＃0．＆c．＃triple ＃feasible

（N≧3），gameSOnSlotland2andgameson

slot2N−2and2N−1arerelativelyimportant

forthefans．Thus，theorganizerdoesnotprefer

HAT which contains HA−pattern Whose slotl

and2（2N−1and2N）are‘A’・IfHATsatisfies

thatatleastoneofthefirstandsecondelements

ofeachrow（HA−pattern）is‘H’，WeSaythatthe HATsatisfies openmg condition・Similarly，We define closing condition.

The number of equitable HAT which meet

openingandclosingconditionis2N−4CN［2］（Ta−

ble2）．However，the numberis obtained by

takingbothfeasibleandinfeasibleHATintoac− count．Inthenextsection，Weperformcompu− tationalexperimentstoenumerateallthefeasi− bleHAT． 3．ComputationalExperiments Weformulatetheproblemtodecidethefea− sibilityofgivenHATasIP［2］．GivenHAT，We

definethefo1lowlngnOtations・LetPbetheset

ofallthetriplets（i，j，S）satisfyingthatthecell oftheglVenHATcorrespondingtoteamiand

slot sis‘A，and the ce1lofteam］andslot s is（H，・WeintroduceaO−1variablexijsforeach triplets（i，j，S）∈Pwhosevalueisequaltolif

andonlyifteamiandjplaysagameonslots・

Thentheproblemforcheckingthefeasibilityof theglVenHATisformulatedasaproblemfor findingasolutionofthefo1lowlngSyStem；

∑頼，再）∈P勘恒＋∑抽，i，β）∈P彗両＝1

（∀五∈r，∀β∈5），

∑頼，再）∈Pごijβ＋∑β‥（j，i，β）∈P彗恒＝1

（∀五∈r，∀j∈r，壱＜j），

ごijβ∈（0，1）（叫，j，β）∈P），

whereTdenotesthesetofteamsandSdenotes thesetofslots，i．e．，T竺（1，2，．‥，2N）and g竺（1，2，…，2Ⅳ−1）．

By means ofsoIving theIP，We Can Check

feasibility ofany glVen HAT・However，When 2N＝20，We haveto soIve8008IP problems

anditistootimeconsumlng．Weintroducea simplenecessaryconditionforfeasibleHAT［2］・ AssumethatHA−patternX，y，andzofthegiven 0 0 0 0 0 1 0 4 6 0 0 8 1 0 10 6 0 12 28 1 14 120 4 16 495 15 18 2002 50 20 8008 161 ＃0．＆c．：thenumberofequitableHATsatisfying Openlngandclosingconditions，

＃triple：thenumberoftheremainedHATafter

applyingtriplebreakconstraint，＃feasible：thenumberoffeasibleHAT・ Tablelis aresultofcomputationalexperi− ments．Tbtalcomputationaltimeiswithin3・5

hours on Windows98PC（CPU：PentiumII

300MHz，RAM：128MB）・Theresultindicates thatfor2N∈（6，8，10，12，14，18），thereisno

feasible equitable HAT satisfying allthe con− ditions，andfewfeasible HAT arefoundfor

2Ⅳ∈（16，20）・ Weshowthat therearefewfeasibleHATfor

thepracticalnumberofteams？andittakesac−

ceptabletimetoenumerateallfeasibleHAT・

Refbrences ［1］D・deWerra：Geography，gameSandgraphs・ βiβCγe亡eApp．〟α軋，2（1980），327−337・［2】R・MiyashiroandT・Matsui：Noteonequita− bleround−rObintournaments．Proceedingsqf β班∬0月βA−JAPAⅣJo慮れfⅣ0γたβんopoれAJ一夕0γ鵡mβα托dComp視ね如m，2001，135−140・ −269− © 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

Note on Equitable Round-Robin Tournaments

2−F−8