Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: cake cutting

Sortuj według:

Ogranicz wyniki do:

On a method of obtaining an approximate solution of an exact fair division problem

Legut J.

Mathematica Applicanda

2018

Vol. 46, no. 2

245--256

Let the unit interval [0; 1] represent a cake to be divided among n players estimating the measurable subsets of [0; 1] by non-atomic probability measures μ1,…, μn. An approximate method is presented of obtaining an exact fair division {A1,…, An} of the cake such that μi (Aj) ≈ 1/n for all i, j = 1,…, n and Ui Ai = [0, 1].

Niech odcinek jednostkowy [0; 1] reprezentuje tort, który ma być podzielony między n graczy, którzy oceniają mierzalne podzbiory odcinka [0; 1] przy pomocy bezatomowych miar probabilistycznych μ1,…, μn. W pracy pokazano przybliżoną metodę uzyskania ściśle sprawiedliwego podziału {A1,…, An}, takiego że μi (Aj) ≈ 1/n dla każdego i, j = 1,…, n oraz Ui Ai = [0, 1].

Strategy-proof Cake Cutting Mechanisms for All-or-nothing Utility

Ihara T., Tsuruta S., Todo T., Sakurai Y., Yokoo M.

Fundamenta Informaticae

2018

Vol. 158, nr 1/3

41--61

The cake cutting problem is concerned with the fair allocation of a divisible good among agents whose preferences vary over it. Recently, designing strategy-proof cake cutting mechanisms has caught considerable attention from AI and MAS researchers. Previous works assumed that an agent’s utility function is additive so that theoretical analysis becomes tractable. However, in practice, agents have non-additive utility over a resource. In this paper, we consider the all-or-nothing utility function as a representative example of non-additive utility because it can widely cover agents’ preferences for such real-world resources as the usage of meeting rooms, time slots for computational resources, bandwidth usage, and so on. We first show the incompatibility between envy-freeness and Pareto efficiency when each agent has all-or-nothing utility. We next propose two strategy-proof mechanisms that satisfy Pareto efficiency, which are based on the serial dictatorship mechanism, at the sacrifice of envy-freeness. To address computational feasibility, we propose a heuristic-based allocation algorithm to find a near-optimal allocation in time polynomial in the number of agents, since the problem of finding a Pareto efficient allocation is NP-hard. As another approach that abandons Pareto efficiency, we develop an envy-free mechanism and show that one of our serial dictatorship based mechanisms satisfies proportionality in expectation, which is a weaker definition of proportionality. Finally, we evaluate the efficiency obtained by our proposed mechanisms by computational experiments.

On Finding Optimal Partitions of Measurable Space

Dall’Aglio M., Legut J., Wilczyński M.

Mathematica Applicanda

2015

Vol. 43, No. 2

157--172

We present an algorithm for nding almost optimal partitions of the unit interval [0; 1) according to given nonatomic measures μ1, μ2, ... μn. This algorithm is based on the idea of Riemann integral and the linear programming method. We also discuss the number of cuts needed for nding the optimal partitions.

W pracy zaprezentowano algorytm uzyskania prawie optymalnego podziału odcinka jednostkowego [0; 1) według danych probabilistycznych miar bezatomowych μ1, μ2, ... μn. Algorytm ten oparty jest na idei całki Riemanna oraz wykorzystuje metodę programowania liniowego. Ponadto autorzy podają wystarczającą liczbę cięć potrzebnych do uzyskania podziałów optymalnych.