(Almost) Envy-Free, Proportional and Efficient Allocations of an Indivisible Mixed Manna

• URL: http://arxiv.org/abs/2202.02672v1
• Date: Sun, 6 Feb 2022 01:29:50 GMT
• Title: (Almost) Envy-Free, Proportional and Efficient Allocations of an Indivisible Mixed Manna
• Authors: Vasilis Livanos, Ruta Mehta, Aniket Murhekar
• Abstract summary: We study the problem of finding fair and efficient allocations of a set of indivisible items to a set of agents. As fairness notions, we consider arguably the strongest possible relaxations of envy-freeness and proportionality.
• Score: 10.933894827834825
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of finding fair and efficient allocations of a set of indivisible items to a set of agents, where each item may be a good (positively valued) for some agents and a bad (negatively valued) for others, i.e., a mixed manna. As fairness notions, we consider arguably the strongest possible relaxations of envy-freeness and proportionality, namely envy-free up to any item (EFX and EFX$_0$), and proportional up to the maximin good or any bad (PropMX and PropMX$_0$). Our efficiency notion is Pareto-optimality (PO). We study two types of instances: (i) Separable, where the item set can be partitioned into goods and bads, and (ii) Restricted mixed goods (RMG), where for each item $j$, every agent has either a non-positive value for $j$, or values $j$ at the same $v_j>0$. We obtain polynomial-time algorithms for the following: (i) Separable instances: PropMX$_0$ allocation. (ii) RMG instances: Let pure bads be the set of items that everyone values negatively. - PropMX allocation for general pure bads. - EFX+PropMX allocation for identically-ordered pure bads. - EFX+PropMX+PO allocation for identical pure bads. Finally, if the RMG instances are further restricted to binary mixed goods where all the $v_j$'s are the same, we strengthen the results to guarantee EFX$_0$ and PropMX$_0$ respectively.

Related papers

• Pushing the Frontier on Approximate EFX Allocations [14.101164748526159]
  We study the problem of allocating a set of indivisible goods to a set of agents with additive valuation functions. We get existence results for strict generalizations of the settings for which exact EFX allocations are known to exist. Our results push the emphfrontier of existence and computation of approximate EFX allocations.
  arXiv  Detail & Related papers  (2024-06-18T09:01:37Z)
• Fair Allocation in Dynamic Mechanism Design [57.66441610380448]
  We consider a problem where an auctioneer sells an indivisible good to groups of buyers in every round, for a total of $T$ rounds. The auctioneer aims to maximize their discounted overall revenue while adhering to a fairness constraint that guarantees a minimum average allocation for each group.
  arXiv  Detail & Related papers  (2024-05-31T19:26:05Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  We propose a novelgreedy bandit (SGB) algorithm for multi-armed bandit problems when no extra information other than the joint reward of the selected set of $n$ arms at each time $tin [T]$ is observed. SGB adopts an optimized-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms.
  arXiv  Detail & Related papers  (2023-12-13T11:08:25Z)
• Dividing Good and Better Items Among Agents with Bivalued Submodular Valuations [20.774185319381985]
  We study the problem of fairly allocating a set of indivisible goods among agents with bivalued submodular valuations. We show that neither the leximin nor the MNW allocation is guaranteed to be envy free up to one good.
  arXiv  Detail & Related papers  (2023-02-06T19:41:28Z)
• Fair Shares: Feasibility, Domination and Incentives [6.878547831852427]
  We consider fair allocation of a set $M$ of indivisible goods to $n$ equally-entitled agents, with no monetary transfers. For additive valuations we present shares that are feasible, self-maximizing and time computable.
  arXiv  Detail & Related papers  (2022-05-16T08:52:42Z)
• Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness [16.187873844872637]
  We consider the problem of fairly allocating a set of indivisible goods to a set of strategic agents with additive valuation functions. Our main goal is to explore whether there exist mechanisms that have pure Nash equilibria for every instance. We show that the corresponding allocations not only are EFX but also satisfy maximin share fairness, something that is not true for this algorithm in the non-strategic setting!
  arXiv  Detail & Related papers  (2021-09-17T16:57:20Z)
• Robust Learning of Optimal Auctions [84.13356290199603]
  We study the problem of learning revenue-optimal multi-bidder auctions from samples when the samples of bidders' valuations can be adversarially corrupted or drawn from distributions that are adversarially perturbed. We propose new algorithms that can learn a mechanism whose revenue is nearly optimal simultaneously for all true distributions'' that are $alpha$-close to the original distribution in Kolmogorov-Smirnov distance.
  arXiv  Detail & Related papers  (2021-07-13T17:37:21Z)
• Weighted QMIX: Expanding Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning [66.94149388181343]
  We present a new version of a popular $Q$-learning algorithm for MARL. We show that it can recover the optimal policy even with access to $Q*$. We also demonstrate improved performance on predator-prey and challenging multi-agent StarCraft benchmark tasks.
  arXiv  Detail & Related papers  (2020-06-18T18:34:50Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  We study the efficient learnability of high-dimensional Gaussian mixtures in the adversarial-robust setting. We provide an algorithm that learns the components of an $epsilon$-corrupted $k$-mixture within information theoretically near-optimal error proofs of $tildeO(epsilon)$. Our main technical contribution is a new robust identifiability proof clusters from a Gaussian mixture, which can be captured by the constant-degree Sum of Squares proof system.
  arXiv  Detail & Related papers  (2020-05-13T16:44:12Z)
• Jealousy-freeness and other common properties in Fair Division of Mixed Manna [2.28438857884398]
  We consider a fair division setting where indivisible items are allocated to agents. We make a distinction between items that are good for some agents and bad for others.
  arXiv  Detail & Related papers  (2020-04-23T21:39:12Z)
• Improved Sleeping Bandits with Stochastic Actions Sets and Adversarial Rewards [59.559028338399855]
  We consider the problem of sleeping bandits with action sets and adversarial rewards. In this paper, we provide a new computationally efficient algorithm inspired by EXP3 satisfying a regret of order $O(sqrtT)$.
  arXiv  Detail & Related papers  (2020-04-14T00:41:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.