On Approximately Strategy-Proof Tournament Rules for Collusions of Size at Least Three

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10493145" target="_blank" >RIV/00216208:11320/24:10493145 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.1007/978-3-031-73903-3_3" target="_blank" >https://doi.org/10.1007/978-3-031-73903-3_3</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-031-73903-3_3" target="_blank" >10.1007/978-3-031-73903-3_3</a>

Result language

angličtina

Original language name

On Approximately Strategy-Proof Tournament Rules for Collusions of Size at Least Three

Original language description

Any (probabilistic) rule for selecting the winner from n teams after observing the outcomes of all matches among them should be Condorcet consistent (i.e., a team that wins all its matches is always selected as the winner) and monotone (i.e., no team can increase its chance of being selected as the winner by throwing matches). Moreover, the rule should be k-SNM-p (i.e., no subset of at most k teams can fix the matches among themselves in order to increase the collective chance that one of them is selected as the winner by at most p) for p as small as possible.We designed and analyzed two new rules satisfying all these properties. The first rule satisfies k-SNM-p for k=3 and p=1/2. The second rule satisfies it for general k and some p (depending on k) that is strictly less than 1. In both cases, we achieved the state-of-the-art results.Finally, given any rule for n teams satisfying k-SNM-p, we constructed a rule for n&apos;&gt;n teams satisfying k-SNM-p&apos; with only a slightly worse guarantee on p&apos;.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2024

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Algorithmic Decision Theory

ISBN

978-3-031-73903-3

ISSN

0302-9743

e-ISSN

—

Number of pages

15

Pages from-to

33-47

Publisher name

Springer

Place of publication

Cham

Event location

Piscataway

Event date

Oct 14, 2024

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—