Algorithmic Game Theory - Fair division with Money and Prices
Script error: No such module "AfC submission catcheck".
The problem of Fair division is the problem of allocating a set of non-disposable goods between agents. This page describes an extension of that problem, in which the agents have exogenous rights on the manna , with rights typically being equal, and cash compensations for the "losing" agens.
This article proposes the Seller-Buyer mechanism as a way of dividing the goods among the agents and compensating the losing agents that attains desirable guarantees on the utility of agents that bid safely according to the model.
Based on "On the fair division of a random object"[1]
Problem Definition[edit]
Let be a set of non-disposable goods, and let be agents, each with a Quasilinear utility function on any set of goods, bidding on the goods.
At the end of the bid each agent receives a partition of (which may be empty), and transfers a cash compensation , such that agent 's utility is and the total money being transfered equals 0, i.e., .
The Case of Additive Utilities[edit]
The problem is simple under the assumption of additive utilities, i.e., . The solution is simply the multi-auction Combinatorial auction mechanism:
Each object is sold in a separate auction, and each agent bids for each obejct, . Each object goes to the highest bidder . Their bid is then equally split among all agents, including the winner. So each agents receives th of price each agent payed for each object.
In this case:
- The unique safe play of agent is the truthful bid , for each .
- Ex-ante fairness is achieved; each agent is guaranteed her fair share,
- Ex-post fairness is achieved, in the form of Envy-freeness; For every , .
- If all agents play safe, the allocation has optimal Pareto efficiency, it maximizes totla utility.
The General Case[edit]
Assume each agent 's utility is weakly monotone, , and for every .
In the general case, two types of issues arise:
- The first type is coneptual: What does it mean to be ex-ante and ex-post fair? Fair share and Envy-freeness don't apply in the general case.
- The second is practical: Agents can only elicit simple messages on their utilities, either because the complexity of reporting the utility on each subset of items is too large, or because that information is sensitive and needs to remain private for as much as possible.
Guarantees[edit]
In order to describe the effectiveness of the Seller-Buyer mechanism the concept of guarantees is needed.
Definition[edit]
A guarantee is a mapping of an agent's utility to a level of utility that the agent can achieve by eliciting a certain legal message, irrespective of what the other agents do.
Formally, let be the set of n-partitions of , and let be a partition. Let , and denote .
For each , a guarantee is such that for every profile , , where is the efficient way of distributing the objects so as to maximize the total surplus. Denote the set of -guarantees on a set of goods as .
Maximal Guarantee[edit]
A high guarantee is desirable for the mechanism - the higher the guaratnee, the more protected the agent's welfare is in the worst case, against unknown vairables, e.g., jointly adversarial agents, etc.
A maximal guarantee is one that cannot be improves. Formally, an -guarantee is maximal, if for any such that for all , than .
Positive and Discriminating Guarantees[edit]
A Simple Guarantee[edit]
A simple guarantee is the fair share guarantee: . It is implementable by auctioning all the items in a bundle as a single item, and using a simple single-item auction or a Texas Shoot Out. Since the items are bundled as a single object, the agent's utilities can be viewed as additive, and therefore the guarantee is feasable.
That guaratnee, however, cannot be used in the general case of utilities. Consider an agent with the greedy (maximally superadditive) utility , for which for any , , and , i.e., wants all or nothing, and consider an agent witht the frugal (maximally subadditive) utility , for which for any , , and , i.e., wants no more than a single item. For these agents, their fair-share guarantee is the same, namely, . This guarantee fails to convey the fact that the greedy agent deserves to be compensated less than the frugal, and should therefore have a lower guarantee.
Properties[edit]
The following defintions capture the desirable properties of a guarantee for a mechanism:
- A guarantee is Positive if given that . In other words, if the objects in the auction aren't worhtless to an agent, they should be compensated.
- A guarantee is Discriminating if .
There's a tradeoff between guarantees that are Positive and Discriminating, and envy-freeness: If , than guarantees that are Positive and Discriminating are incompatible with envy-freeness. For example, consider a greedy and a frugal agents, with 2 goods. Then there are exactly 2 types of envy-free allocations; one agent gets all the goods and pays the other half of the utility to the other agent, and so both agents receive gets the same utility, which is not discriminating; or they each get at least one object, and there is no money transfer, which is not positive, because the greedy agent receives no utility (but is not envious of the other agent's object, because they only desire both objects together).
Maxmin and minMax Bounds[edit]
The Divide and choose procedure inspires two critical welfare levels which will be shown to bound the possible guarantees.
Denote by the unanimous profile where each individual utility is the same, .
The Maxmin utility, , is what a divider choosing last can guarantee for themselves.
It can be shown that the Maxmin utility is an upper bound on all guarantees, but it not a guarantee itself.
The minMax utility, , is what a Choose choosing first can guarantee against an adversarial divider.
It can be shown that minMax utility is a guarantee, albeit a low one - it is dominated by the naive fair share guarantee, and others. In addition, it is not Positive.
Desirable Guarantees[edit]
The effective guarantees for the Seller-Buyer mechanism have the following properties:
- is Positive and Discriminating
- is maximal
These properties imply that
- if is additive, i.e., the fair share,
- if is sub-additive, i.e., if an agent is less greedy, they'll get more than their fair share, and
- if is super-additive, i.e., if an agent is more greedy, they'll get less than their fair share.
The Seller-Buyer Mechanism[edit]
Two-Agents Case[edit]
Denote by the 2-agents Seller-Buyer mechanism on the set of goods, which is as follows:
- The two agents bid to become the seller.
- The lower bidder wins, with a bid , and becomes the seller. The other agent becomes the buyer.
- The seller chooses a price such that the total price of all items is exactly , i.e., .
- The buyer now buys a share of objects at the price , and the seller gets the remaining items.
- The allocations is: to the buyer (their cash transfer is negative because they paid), and to the seller.
Guaranteed Safe Bidding in the Two-Agents Case[edit]
In these settings, how should an agent bid safely to maximize their utility?
Denote by the Simplex of non-negative prices summing up to .
Denote the worst utility if the agent wins (with the lowest bid) and becomes the seller by .
Denote the worst utility if the agent loses (with a bid that is higher by a hair), and becomes the buyer by .
Lemma: It can be shown that is concave and strictly increasing from to , and that is convex and strictly decreasing from to . This implies that they intersect uniquely at . The value at the intersection is the guarantee and the safe bid for the agent.
n-Agents Case[edit]
The Seller-Buyer mechanism definition for the case of agents, is recursive:
- The agents bid to become sellers and buyer.
- Denote the agents according to their bid order, with agent the highest bidder.
- Agent becomes the buyer.
- Each of the agents picks a price (constrained by their bid ).
- The buyer (agent ) chooses which obejcts to buy, and pays each agent whicever price they asked for .
- Agents continue to until either all objects are assigned, or all agents left.
Note that in this mechanism, privacy is protected - the prices in each round are hidden from the other sellers, and are only revealed to the round's buyer.
Guaranteed Safe Bidding in the n-Agents Case[edit]
Similarly to the two-agents case, the definition for the worst utilities in the two cases are: , and . The same lemma can be seen in this case: is concave and strictly increasing from to , and is convex and strictly decreasing from to , and so they intersect uniquely at , and the value at the intersction is the guarantee and the safe bid for the agent.
Example: Dichotomous Utilities[edit]
Consider identical objects and agents with dichotomous utilities, i.e., for some , if , and otherwise.
Note that when , we're in the frugal case, , and when , we're in the greedy case, .
To compute and we need only look at symmetric prices on : and .
By intersecting these we get , and recursively get .
Observe that:
- For (the frugal case), , the agent is guaranteed almost their entire value, and moreso the more objects there are.
- For (the greedy case), , the agent has a very small guarantee.
This example leads to the interesting conclusion that the more subadditive an agent is, the closer their guarantee is to their value.
References[edit]
- ↑ Bogomolnaia, Anna; Moulin, Hervé; Sandomirskiy, Fedor (2021-03-23). "On the Fair Division of a Random Object". Management Science. doi:10.1287/mnsc.2021.3973. ISSN 0025-1909.
This article "Algorithmic Game Theory - Fair division with Money and Prices" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Algorithmic Game Theory - Fair division with Money and Prices. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.