Matematické Fórum

halogan · 22. 12. 2011 12:59

Dobré odpoledne,

mějme 3 hráče, kteří navrhují policy, která se skládá ze dvou (odlišitelných, na pořadí záleží) složek, kombinace ideálních návrhů pro každého hráče je tedy bod v R^2. Hlasuje se v párové volbě s tím, že krom návrhů těchto tří hráčů (označme A[a_1,a_2], analogicky B a C) je možné návrhy kombinovat -- [a_1,b_2], [c_1,a_2], ...

Dokažte, že existuje Condorcet winner mezi těmito návrhy -- tedy že existuje taková kombinace [z_1,w_2], která nemůže být přehlasovaná v párové volbě (jdou proti sobě vždy jen dva návrhy).

Preference jsou euklidovské -- čím blíž, tím líp (v následujícím obrázku tedy B nejvíce preferuje BB, preferuje BC před CB apod.).

Pro lepší představivost přidávám obrázek (A znamená AA, B je BB, C je CC).

---

Měli jsme to jako domácí úkol a spolužáci se s tím poprali různě. Já mám takový dost neobecný důkaz, který se ani mně nelíbí, ale věřím, že vymyslíte něco hezčího.

check_drummer · 22. 12. 2011 19:29

Ahoj,

halogan napsal(a):
Dokažte, že existuje Condorcet winner mezi těmito návrhy -- tedy že existuje taková kombinace [z_1,w_2], která nemůže být přehlasovaná v párové volbě (jdou proti sobě vždy jen dva návrhy).

Co znamená (jak je definováno), že volba X je přehasována volbou Y?

halogan · 22. 12. 2011 21:13

Kazdy ze tri hracu dava jeden hlas jemu nejblizsi policy z tech dvou nabizenych. Pokud ma obe stejne daleko, tak nehlasuje (nebo da obema hlas, to je jedno).

Condorcet nesmi prohrat, muze remizovat.

check_drummer · 22. 12. 2011 21:32

↑ halogan:
Asi to stále nechápu. Co je to policy? Je to libovolný bod v R2 nebo jen nějaká pevně zvolená podmnožina R2? Ale nejspíš budou jen dvě - když vidím co píšeš, ale stejně tomu nerozumím. :-) Asi by bylo dbré definovat tu "policy" - nebo "polici"? Víme, že se skládá ze dvou složek, ale nevíme, jakých hodnot může každá složka nabývat...

halogan · 22. 12. 2011 21:41

Je to na obrazku. Xova souradnice je a_1, b_1, nebo c_1, y je a_2, b_2, nebo c_2.

Vemte to tak, ze se resi penize na dalnice a na zeleznici. Hrac A chce dat 30 na dalnice a 10 na zeleznici, jeho idealni kombinace je [30,10], ostatni analogicky.

Navrhuji se takove kombinace, ze kazdou ze souradnic navrhnul aspon jeden ze hracu. Je tedy 4-9 navrhu, podle rozestaveni tech preferenci.

---

Sorry za nejasnosti. Snad jsem to vysvetlil. Az budu u pocitace, tak to kdyztak doplnim.

check_drummer · 23. 12. 2011 15:26

↑ halogan:
Tak už to asi chápu - zatím se nebudu snažit to zobecnit pro více než 3 lidi a více dimezí než R2, ale asi to jednoduše lze.

1) Každý člověk i "volí" bod Pi:=[xi;yi] v R2.
2) Dále uvažujeme množinu M všech {[xi;yj]}, M obsahuje nejvýše 9 prvků a aspoň 1 prvek (tady se lišíme, protože ty tvrdíš, že osbahuje aspoň 4 prvky...)
3) Pro M1,M2 z M hlasuje hráč i pro ten bod, který je blíže k Pi (pokud je tato vzdálenost v obou případech stejná, hráč nehlasuje). Který bod z M1,M2 získá takto více hlasů, je "vítězem" duelu M1 vs. M2. Remíza není vyloučena.
4) Otázka zní, zda existuje takové M0 z M, které v postupu hlasování z bodu 3) nikdy neprohraje, ať za jeho soupeře z M zvolíme kohokoliv.

Je to tak?

halogan · 23. 12. 2011 20:33

↑ check_drummer:

1) Ano.

2) Moje chyba, bral jsem ale zajímavé kombinace (tj. P_i \neq P_j, pro i \neq j). I tak je minimum 3, ne čtyři.

3, 4) Ano.

Je to tak.

---

Ono to je v principu docela jednoduché, jen já to popisuju zbytečně nepřehledně.

check_drummer · 26. 12. 2011 21:03

↑ halogan:
Tak bohužel mě nenapadlo nic elegantního - jen rozbor možných případů a u každého případu volba onoho Con. winnera, možnosti jsou: A,B leží v protilehlých vrcholech obdélníka, C uvnitř něj. A nebo A leži ve vrcholu obdélníka a B,C na dvou hranách, které nesousedí s A.

Má se ukázat, že tvrzení platí jen pro 3 osoby nebo obecně pro k osob a n voleb (místo 2)?

Matematické Fórum

#1 22. 12. 2011 12:59

Condorcet winner při možnosti kombinovat soutěžní návrhy

#2 22. 12. 2011 19:29

Re: Condorcet winner při možnosti kombinovat soutěžní návrhy

halogan napsal(a):

#3 22. 12. 2011 21:13

Re: Condorcet winner při možnosti kombinovat soutěžní návrhy

#4 22. 12. 2011 21:32

Re: Condorcet winner při možnosti kombinovat soutěžní návrhy

#5 22. 12. 2011 21:41

Re: Condorcet winner při možnosti kombinovat soutěžní návrhy

#6 23. 12. 2011 15:26

Re: Condorcet winner při možnosti kombinovat soutěžní návrhy

#7 23. 12. 2011 20:33

Re: Condorcet winner při možnosti kombinovat soutěžní návrhy

#8 26. 12. 2011 21:03

Re: Condorcet winner při možnosti kombinovat soutěžní návrhy

Zápatí