NDLI: Allocating indivisible goods

Please wait, while we are loading the content...

Allocating indivisible goods

Content Provider	ACM Digital Library
Author	Bezáková, Ivona Dani, Varsha
Abstract	The problem of allocating divisible goods has enjoyed a lot of attention in both mathematics (e.g. the cake-cutting problem) and economics (e.g. market equilibria). On the other hand, the natural requirement of indivisible goods has been somewhat neglected, perhaps because of its more complicated nature. In this work we study a fairness criterion, called the Max-Min Fairness problem, for k players who want to allocate among themselves m indivisible goods. Each player has a specified valuation function on the subsets of the goods and the goal is to split the goods between the players so as to maximize the minimum valuation. Viewing the problem from a game theoretic perspective, we show that for two players and additive valuations the expected minimum of the (randomized) cut-and-choose mechanism is a 1/2-approximation of the optimum. To complement this result we show that no truthful mechanism can compute the exact optimum.We also consider the algorithmic perspective when the (true) additive valuation functions are part of the input. We present a simple 1/(m - k + 1) approximation algorithm which allocates to every player at least 1/k fraction of the value of all but the k - 1 heaviest items. We also give an algorithm with additive error against the fractional optimum bounded by the value of the largest item. The two approximation algorithms are incomparable in the sense that there exist instances when one outperforms the other.
Starting Page	11
Ending Page	18
Page Count	8
File Format	PDF
ISSN	15519031
DOI	10.1145/1120680.1120683
Journal	ACM SIGecom Exchanges (SECO)
Volume Number	5
Issue Number	3
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2003-03-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Economics Algorithms Theory Approximation algorithms Game theory Cake-cutting Fairness Truthfulness
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Allocating indivisible goods (2005)

Allocating indivisible goods (2005)

On approximately fair allocations of indivisible goods

Characterizations of strategy-proof and fair mechanisms for allocating indivisible goods

Beyond Cake Cutting: Allocating Homogeneous Divisible Goods

An approximation algorithm for max-min fair allocation of indivisible goods

Manipulation games in economies with indivisible goods

On the truthfulness and the approximation for scheduling selfish tasks

Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness

Allocating indivisible goods

Similar Documents

Allocating indivisible goods (2005)

Allocating indivisible goods (2005)

On approximately fair allocations of indivisible goods

Characterizations of strategy-proof and fair mechanisms for allocating indivisible goods

Beyond Cake Cutting: Allocating Homogeneous Divisible Goods

An approximation algorithm for max-min fair allocation of indivisible goods

Manipulation games in economies with indivisible goods

On the truthfulness and the approximation for scheduling selfish tasks

Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness

Allocating indivisible goods