Publication:

On the Manipulability of Tournament Rules by Throwing Matches

datacite.rightsopen.access
dc.contributor.advisorWeinberg, Matt
dc.contributor.authorSathyanarayanan, Sacheth
dc.contributor.otherComputer Science Department
dc.date.accessioned2023-08-04T15:47:01Z
dc.date.accessioned2026-09-30T10:34:18Z
dc.date.available2023-08-04T15:47:01Z
dc.date.available2026-09-30T10:34:18Z
dc.date.created2023-01-01
dc.date.issued2023
dc.description.abstractA Tournament Rule takes as input a set of $\binom{n}{2}$ pairwise match results on $n$ teams and (possibly randomly) selects a ranking of teams, with a prize associated to each place in the ranking. Two teams may manipulate their match outcomes to try and improve their expected prize winnings. [SSW17] and subsequent works seek to understand the minimum manipulability among all ``reasonable'' tournament rules (i.e. tournament rules so that if team $x$ defeats every other team, it is ranked first with probability $1$), when these two teams fix the match between them. Our work instead considers the possibility that two teams may both fix the match between them, and additionally throw matches to outside teams (that is, they can intentionally lose a match to a non-colluding team that they could have won). Our main result establishes that no two teams can gain more than $1/3$ in expected prize winnings in Nested Randomized King of the Hill (introduced in [DaleFRSW22], similar to QuickSort), by together fixing their match and throwing matches to external teams. This is optimal, as any ``reasonable'' tournament admits the possibility of two teams gaining $1/3$ in expected prize-winnings just by fixing the match between them.
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/dsp01h128nj00z
dc.identifier.urihttps://theses-dissertations.princeton.edu/handle/88435/dsp01h128nj00z
dc.language.isoen
dc.publisherPrinceton, NJ : Princeton University
dc.subject.classificationComputer science
dc.titleOn the Manipulability of Tournament Rules by Throwing Matches
dc.typeAcademic dissertations (M.S.E.)
dspace.entity.typePublication
pu.date.classyear2023
pu.departmentComputer Science

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Sathyanarayanan_princeton_0181G_14576.pdf
Size:
835.62 KB
Format:
Adobe Portable Document Format