Megjelent Cseh Ágnes és Fleiner Tamás cikke az ACM Transactions on Algorithms folyóiratban

2020.06.29 | 14:22
Megjelent Cseh Ágnes és Fleiner Tamás cikke az ACM Transactions on Algorithms folyóiratban

Volume 16, Issue 3, June 2020

The Complexity of Cake Cutting with Unequal Shares

An unceasing problem of our prevailing society is the fair division of goods. The problem of proportional cake cutting focuses on dividing a heterogeneous and divisible resource, the cake, among n players who value pieces according to their own measure function. The goal is to assign each player a not necessarily connected part of the cake that the player evaluates at least as much as her proportional share. In this article, we investigate the problem of proportional division with unequal shares, where each player is entitled to receive a predetermined portion of the cake. Our main contribution is threefold. First we present a protocol for integer demands, which delivers a proportional solution in fewer queries than all known protocols. By giving a matching lower bound, we then show that our protocol is asymptotically the fastest possible. Finally, we turn to irrational demands and solve the proportional cake cutting problem by reducing it to the same problem with integer demands only. All results remain valid in a highly general cake cutting model, which can be of independent interest.

« Vissza a listához

Eseménynaptár

H

K

Sz

Cs

P

Szo

V

31
2
3
4
5
6
7
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
2020 Szeptember

Kiemelt híreink

Elhunyt Major Iván (1949-2020), a KRTK Közgazdaság-tudományi Intézet nyugalmazott tudományos tanácsadója.

Elhunyt Major Iván (1949-2020), a KRTK Közgazdaság-tudományi Intézet nyugalmazott tudományos tanácsadója. 2020. szeptember 25-én életének 71-ik évében elhunyt Major Iván, a KRTK Közgazdaság-tudományi Intézet nyugalmazott tudományos tanácsadója. Major Iván 1973-ban végzett a Közgazdaságtudományi Egyetem Elméleti-Gazdaságpolitikai szakán. 1976-ban egyetemi doktor, 1983-ban a közgazdaság-tudomány kandidátusa. 1996-ban nagydoktori címet szerzett. 1973 óta dolgozott az Intézetben.

Áldás vagy átok a gyémántvagyon? Biedermann Zsuzsánna cikke a Portfolio KRTK Blogjában

Áldás vagy átok a gyémántvagyon? Biedermann Zsuzsánna cikke a Portfolio KRTK Blogjában A nemzetközi sajtó 2020 elején szenzációs adásvételről tudósított: a Louis Vuitton luxusdivatház megvásárolta minden idők második legnagyobb nyersgyémántját, a Botswanában talált Sewelo ékkövet. De mennyire ismerjük a gyémánt lelőhelyének számító kis dél-afrikai országot és a nyersanyagban gazdag fejlődő országok gazdasági kihívásait?

Szabó John előadása az Alternative Economic Policy in Europe online konferencián

Szabó John előadása az Alternative Economic Policy in Europe online konferencián Az EuroMemo Group idén 26. alkalommal szervezi meg ″Alternative Economic Policy in Europe″ című konferenciáját 2020. szeptember 23-án és 24-én. A rendezvény keretében előadást tart a Világgazdasági Intézet tudományos segédmunkatársa, Szabó John ″Hydrogen as an impediment to socio-ecological transformation?″ címmel.

További híreink »