Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEnvy-free division using mapping degree
100
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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. We provide a polynomial-time algorithm for finding an envy-free matching of maximum cardinality. For edge-weighted bipartite graphs, we provide a polynomial-time algorithm for finding a maximum-cardinality envy-free matching of minimum weight. We show how envy-free matchings can be used in various fair division problems with either continuous resources (cakes) or discrete ones. In particular, we show a symmetric algorithm for proportional cake-cutting, an algorithm for $1$-out-of-$(2n-2)$ maximin-share allocation of discrete goods, and an algorithm for $1$-out-of-$lfloor 2n/3rfloor$ maximin-share allocation of discrete bads (chores) among $n$ agents.
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 allocation that is envy-free (EF), in which the agents do not envy each other for the items they receive, nor do they envy a charity, who is endowed with all the unallocated items. Since EF allocations barely exist even without budget constraints, we are interested in the relaxed notion of envy-freeness up to one item (EF1). The computation of both exact and approximate EF1 allocations remains largely open, despite a recent effort by Wu et al. (IJCAI 2021) in showing that any budget-feasible allocation that maximizes the Nash Social Welfare (NSW) is 1/4-approximate EF1. In this paper, we move one step forward by showing that for agents with identical additive valuations, a 1/2-approximate EF1 allocation can be computed in polynomial time. For the uniform-budget and two-agent cases, we propose efficient algorithms for computing an exact EF1 allocation. We also consider the large budget setting, i.e., when the item sizes are infinitesimal compared with the agents budgets, and show that both the NSW maximizing allocation and the allocation our polynomial-time algorithm computes have an approximation close to 1 regarding EF1.
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 group envies another group. Group Pareto efficiency requires that no group can be made better off without another group be made worse off. We study these new group properties from an axiomatic viewpoint. We thus propose new fairness taxonomies that generalize existing taxonomies. We further study ne
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 complexity of $d+1$ player cake cutting with Lipschitz utilities for any $d> 1$. When the utility functions are given by a polynomial time algorithm, we prove the problem to be PPAD-complete. For measurable utility functions, we find a fully polynomial-time algorithm for finding an approximate envy-free allocation of a cake among three people using two cuts.
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 setting. In addition, many existing axiomatic results often do not transfer from the offline to the online setting. For this reason, we propose here three new online mechanisms, as well as consider the axiomatic properties of three previously proposed online mechanisms. In this paper, we use these mechanisms and characterize classes of online mechanisms that are strategy-proof, and return envy-free and Pareto efficient allocations, as well as combinations of these properties. Finally, we identify an important impossibility result.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
