ﻻ يوجد ملخص باللغة العربية
In this paper we study envy-free division problems. The classical approach to such problems, used by David Gale, reduces to considering continuous maps of a simplex to itself and finding sufficient conditions for this map to hit the center of the simplex. The mere continuity of the map is not sufficient for reaching such a conclusion. Classically, one makes additional assumptions on the behavior of the map on the boundary of the simplex (for example, in the Knaster--Kuratowski--Mazurkiewicz and the Gale theorem). We follow Erel Segal-Halevi, Frederic Meunier, and Shira Zerbib, and replace the boundary condition by another assumption, which has the meaning in economy as the possibility for a player to prefer an empty part in the segment partition problem. We solve the problem positively when $n$, the number of players that divide the segment, is a prime power, and we provide counterexamples for every $n$ which is not a prime power. We also provide counterexamples relevant to a wider class of fair or envy-free division problems when $n$ is odd and not a prime power. In this arxiv version that appears after the official publication we have corrected the statement and the proof of Lemma 3.4.
A matching in a bipartite graph $G:=(X + Y,E)$ is said to be envy-free if no unmatched vertex in $X$ is adjacent to a mathced vertex in $Y$. Every perfect matching is envy-free, but envy-free matchings may exist even when perfect matchings do not.
In the budget-feasible allocation problem, a set of items with varied sizes and values are to be allocated to a group of agents. Each agent has a budget constraint on the total size of items she can receive. The goal is to compute a feasible allocati
We study the fair division of items to agents supposing that agents can form groups. We thus give natural generalizations of popular concepts such as envy-freeness and Pareto efficiency to groups of fixed sizes. Group envy-freeness requires that no g
We study the envy-free cake-cutting problem for $d+1$ players with $d$ cuts, for both the oracle function model and the polynomial time function model. For the former, we derive a $theta(({1overepsilon})^{d-1})$ time matching bound for the query comp
We consider fair division problems where indivisible items arrive one-by-one in an online fashion and are allocated immediately to agents who have additive utilities over these items. Many existing offline mechanisms do not work in this online settin