Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFair-Share Allocations for Agents with Arbitrary Entitlements
175
0
0.0
(
0
)
Added by
Tomer Ezra
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We consider the problem of fair allocation of indivisible goods to $n$ agents, with no transfers. When agents have equal entitlements, the well established notion of the maximin share (MMS) serves as an attractive fairness criterion, where to qualify as fair, an allocation needs to give every agent at least a substantial fraction of her MMS. In this paper we consider the case of arbitrary (unequal) entitlements. We explain shortcomings in previous attempts that extend the MMS to unequal entitlements. Our conceptual contribution is the introduction of a new notion of a share, the AnyPrice share (APS), that is appropriate for settings with arbitrary entitlements. Even for the equal entitlements case, this notion is new, and satisfies $APS ge MMS$, where the inequality is sometimes strict. We present two equivalent definitions for the APS (one as a minimization problem, the other as a maximization problem), and provide comparisons between the APS and previous notions of fairness. Our main result concerns additive valuations and arbitrary entitlements, for which we provide a polynomial-time algorithm that gives every agent at least a $frac{3}{5}$-fraction of her APS. This algorithm can also be viewed as providing strategies in a certain natural bidding game, and these strategies secure each agent at least a $frac{3}{5}$-fraction of her APS.
rate research
Read More
We consider the problem of fair allocation of indivisible items among $n$ agents with additive valuations, when agents have equal entitlements to the goods, and there are no transfers. Best-of-Both-Worlds (BoBW) fairness mechanisms aim to give all agents both an ex-ante guarantee (such as getting the proportional share in expectation) and an ex-post guarantee. Prior BoBW results have focused on ex-post guarantees that are based on the up to one item paradigm, such as envy-free up to one item (EF1). In this work we attempt to give every agent a high value ex-post, and specifically, a constant fraction of his maximin share (MMS). The up to one item paradigm fails to give such a guarantee, and it is not difficult to present examples in which previous BoBW mechanisms give agents only a $frac{1}{n}$ fraction of their MMS. Our main result is a deterministic polynomial time algorithm that computes a distribution over allocations that is ex-ante proportional, and ex-post, every allocation gives every agent at least his proportional share up to one item, and more importantly, at least half of his MMS. Moreover, this last ex-post guarantee holds even with respect to a more demanding notion of a share, introduced in this paper, that we refer to as the truncated proportional share (TPS). Our guarantees are nearly best possible, in the sense that one cannot guarantee agents more than their proportional share ex-ante, and one cannot guarantee agents more than a $frac{n}{2n-1}$ fraction of their TPS ex-post.
We study the problem of computing maximin share guarantees, a recently introduced fairness notion. Given a set of $n$ agents and a set of goods, the maximin share of a single agent is the best that she can guarantee to herself, if she would be allowed to partition the goods in any way she prefers, into $n$ bundles, and then receive her least desirable bundle. The objective then in our problem is to find a partition, so that each agent is guaranteed her maximin share. In settings with indivisible goods, such allocations are not guaranteed to exist, so we resort to approximation algorithms. Our main result is a $2/3$-approximation, that runs in polynomial time for any number of agents. This improves upon the algorithm of Procaccia and Wang, which also produces a $2/3$-approximation but runs in polynomial time only for a constant number of agents. To achieve this, we redesign certain parts of their algorithm. Furthermore, motivated by the apparent difficulty, both theoretically and experimentally, in finding lower bounds on the existence of approximate solutions, we undertake a probabilistic analysis. We prove that in randomly generated instances, with high probability there exists a maximin share allocation. This can be seen as a justification of the experimental evidence reported in relevant works. Finally, we provide further positive results for two special cases that arise from previous works. The first one is the intriguing case of $3$ agents, for which it is already known that exact maximin share allocations do not always exist (contrary to the case of $2$ agents). We provide a $7/8$-approximation algorithm, improving the previously known result of $3/4$. The second case is when all item values belong to ${0, 1, 2}$, extending the ${0, 1}$ setting studied in Bouveret and Lema^itre. We obtain an exact algorithm for any number of agents in this case.
We study fair allocation of indivisible public goods subject to cardinality (budget) constraints. In this model, we have n agents and m available public goods, and we want to select $k leq m$ goods in a fair and efficient manner. We first establish fundamental connections between the models of private goods, public goods, and public decision making by presenting polynomial-time reductions for the popular solution concepts of maximum Nash welfare (MNW) and leximin. These mechanisms are known to provide remarkable fairness and efficiency guarantees in private goods and public decision making settings. We show that they retain these desirable properties even in the public goods case. We prove that MNW allocations provide fairness guarantees of Proportionality up to one good (Prop1), $1/n$ approximation to Round Robin Share (RRS), and the efficiency guarantee of Pareto Optimality (PO). Further, we show that the problems of finding MNW or leximin-optimal allocations are NP-hard, even in the case of constantly many agents, or binary valuations. This is in sharp contrast to the private goods setting that admits polynomial-time algorithms under binary valuations. We also design pseudo-polynomial time algorithms for computing an exact MNW or leximin-optimal allocation for the cases of (i) constantly many agents, and (ii) constantly many goods with additive valuations. We also present an O(n)-factor approximation algorithm for MNW which also satisfies RRS, Prop1, and 1/2-Prop.
In this paper, we investigate the effect of brand in market competition. Specifically, we propose a variant Hotelling model where companies and customers are represented by points in an Euclidean space, with axes being product features. $N$ companies compete to maximize their own profits by optimally choosing their prices, while each customer in the market, when choosing sellers, considers the sum of product price, discrepancy between product feature and his preference, and a companys brand name, which is modeled by a function of its market area of the form $-betacdottext{(Market Area)}^q$, where $beta$ captures the brand influence and $q$ captures how market share affects the brand. By varying the parameters $beta$ and $q$, we derive existence results of Nash equilibrium and equilibrium market prices and shares. In particular, we prove that pure Nash equilibrium always exists when $q=0$ for markets with either one and two dominating features, and it always exists in a single dominating feature market when market affects brand name linearly, i.e., $q=1$. Moreover, we show that at equilibrium, a companys price is proportional to its market area over the competition intensity with its neighbors, a result that quantitatively reconciles the common belief of a companys pricing power. We also study an interesting wipe out phenomenon that only appears when $q>0$, which is similar to the undercut phenomenon in the Hotelling model, where companies may suddenly lose the entire market area with a small price increment. Our results offer novel insight into market pricing and positioning under competition with brand effect.
In this paper, we consider how to fairly allocate $m$ indivisible chores to a set of $n$ (asymmetric) agents. As exact fairness cannot be guaranteed, motivated by the extensive study of EF1, EFX and PROP1 allocations, we propose and study {em proportionality up to any item} (PROPX), and show that a PROPX allocation always exists. We argue that PROPX might be a more reliable relaxation for proportionality in practice than the commonly studied maximin share fairness (MMS) by the facts that (1) MMS allocations may not exist even with three agents, but PROPX allocations always exist even for the weighted case when agents have unequal obligation shares; (2) any PROPX allocation ensures 2-approximation for MMS, but an MMS allocation can be as bad as $Theta(n)$-approximation to PROPX. We propose two algorithms to compute PROPX allocations and each of them has its own merits. Our first algorithm is based on a recent refinement for the well-known procedure -- envy-cycle elimination, where the returned allocation is simultaneously PROPX and $4/3$-approximate MMS. A by-product result is that an exact EFX allocation for indivisible chores exists if all agents have the same ordinal preference over the chores, which might be of independent interest. The second algorithm is called bid-and-take, which applies to the weighted case. Furthermore, we study the price of fairness for (weighted) PROPX allocations, and show that the algorithm computes allocations with the optimal guarantee on the approximation ratio to the optimal social welfare without fairness constraints.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
