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

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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;.

Název v anglickém jazyce

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

Popis výsledku anglicky

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;.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

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

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2024

Kód důvěrnosti údajů

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

Název statě ve sborníku

Algorithmic Decision Theory

ISBN

978-3-031-73903-3

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

15

Strana od-do

33-47

Název nakladatele

Springer

Místo vydání

Cham

Místo konání akce

Piscataway

Datum konání akce

14. 10. 2024

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—