1 Zubei

Prefer Initialization Over Assignment Of Rents

Copy constructors sounds like a topic for an article from 1989. And yet, the changes in the new C++ standard affect the design of a class’ special member functions fundamentally. Find out more about the impact of move semantics on objects’ behavior and learn how to implement the move constructor and the move assignment operator in C++11.

C++11 is the informal name for ISO/IEC 14882:2011, the new C++ standard that was published in September 2011. It includes the TR1 libraries and a large number of new core features (a detailed discussion about these new C++11 features is available here; also see The Biggest Changes in C++11 (and Why You Should Care)):

  • Initializer lists
  • Uniform initialization notation
  • Lambda functions and expressions
  • Strongly-typed enumerations
  • Automatic type deduction in declarations
  • storage class
  • Control and query of object alignment
  • Static assertions
  • Type
  • Variadic templates

Important as these features may be, the defining feature of C++11 is rvalue references.

The Right Time for Rvalue References

Rvalue references are a new category of reference variables that can bind to rvalues.  Rvalues are slippery entities, such as temporaries and literal values; up until now, you haven’t been able to bind these safely to reference variables.

Technically, an rvalue is an unnamed value that exists only during the evaluation of an expression. For example, the following expression produces an rvalue:

x+(y*z); // A C++ expression that produces a temporary 

C++ creates a temporary (an rvalue) that stores the result of , and then adds it to . Conceptually, this rvalue evaporates by the time you reach the semicolon at the end of the full expression.

A declaration of an rvalue reference looks like this:

std::string&& rrstr; //C++11 rvalue reference variable

The traditional reference variables of C++ e.g.,

std::string& ref;

are now called lvalue references.

Rvalue references occur almost anywhere, even if you don’t use them directly in your code. They affect the semantics and lifetime of objects in C++11. To see how exactly, it’s time to talk about move semantics.

Get to Know Move Semantics

Hitherto, copying has been the only means for transferring a state from one object to another (an object’s state is the collective set of its non-static data members’ values). Formally, copying causes a target object to end up with the same state as the source , without modifying . For example, when you copy a string to , the result is two identical strings with the same state as .

And yet, in many real-world scenarios, you don’t copy objects but move them. When my landlord cashes my rent check, he moves money from my account into his. Similarly, removing the SIM card from your mobile phone and installing it in another mobile is a move operation, and so are cutting-and-pasting icons on your desktop, or borrowing a book from a library.

Notwithstanding the conceptual difference between copying and moving, there’s a practical difference too: Move operations tend to be faster than copying because they transfer an existing resource to a new destination, whereas copying requires the creation of a new resource from scratch. The efficiency of moving can be witnessed among the rest in functions that return objects by value. Consider:

string func()
{
string s;
//do something with s
return s;
}
string mystr=func();

When returns, C++ constructs a temporary copy of on the caller’s stack memory. Next, is destroyed and the temporary is used for copy-constructing . After that, the temporary itself is destroyed. Moving achieves the same effect without so many copies and destructor calls along the way.

Moving a string is almost free; it merely assigns the values of the source’s data members to the corresponding data members of the target. In contrast, copying a string requires the allocation of dynamic memory and copying the characters from the source.

Move Special Member Functions

C++11 introduces two new special member functions: the move constructor and the move assignment operator. They are an addition to the fabulous four you know so well:

  • Default constructor
  • Copy constructor
  • Copy assignment operator
  • Destructor

If a class doesn’t have any user-declared special member functions (save a default constructor), C++ declares its remaining five (or six) special member functions implicitly, including a move constructor and a move assignment operator. For example, the following class

class S{};

doesn’t have any user-declared special member functions. Therefore, C++ declares all of its six special member functions implicitly. Under certain conditions, implicitly declared special member functions become implicitly defined as well. The implicitly-defined move special member functions move their sub-objects and data members in a member-wise fashion. Thus, a move constructor invokes its sub-objects’ move constructors, recursively. Similarly, a move assignment operator invokes its sub-objects’ move assignment operators, recursively.

What happens to a moved-from object? The state of a moved-from object is unspecified. Therefore, always assume that a moved-from object no longer owns any resources, and that its state is similar to that of an empty (as if default-constructed) object. For example, if you move a string to , after the move operation the state of is identical to that of before the move, whereas is now an empty (though valid) string object.

Designing a Move Constructor

A move constructor looks like this:

C::C(C&& other); //C++11 move constructor

It doesn’t allocate new resources. Instead, it pilfers‘s resources and then sets to its default-constructed state.

Let’s look at a concrete example. Suppose you’re designing a class that represents a memory buffer:

class MemoryPage
{
size_t size;
char * buf;
public:
explicit MemoryPage(int sz=512):
size(sz), buf(new char [size]) {}
~MemoryPage( delete[] buf;}
//typical C++03 copy ctor and assignment operator
MemoryPage(const MemoryPage&);
MemoryPage& operator=(const MemoryPage&);
};

A typical move constructor definition would look like this:

//C++11
MemoryPage(MemoryPage&& other): size(0), buf(nullptr)
{
// pilfer other’s resource
size=other.size;
buf=other.buf;
// reset other
other.size=0;
other.buf=nullptr;
}

The move constructor is much faster than a copy constructor because it doesn’t allocate memory nor does it copy memory buffers.

Designing a Move Assignment Operator

A move assignment operator has the following signature:

C& C::operator=(C&& other);//C++11 move assignment operator

A move assignment operator is similar to a copy constructor except that before pilfering the source object, it releases any resources that its object may own. The move assignment operator performs four logical steps:

  • Release any resources that currently owns.
  • Pilfer ‘s resource.
  • Set to a default state.
  • Return .

Here’s a definition of ‘s move assignment operator:

//C++11
MemoryPage& MemoryPage::operator=(MemoryPage&& other)
{
if (this!=&other)
{
// release the current object’s resources
delete[] buf;
size=0;
// pilfer other’s resource
size=other.size;
buf=other.buf;
// reset other
other.size=0;
other.buf=nullptr;
}
return *this;
}

Overloading Functions

The overload resolution rules of C++11 were modified to support rvalue references. Standard Library functions such as now define two overloaded versions: one that takes for lvalue arguments as before, and a new one that takes a parameter of type for rvalue arguments. The following program populates a vector with objects using two () calls:

#include <vector>
using namespace std;
int main()
{
vector<MemoryPage> vm;
vm.push_back(MemoryPage(1024));
vm.push_back(MemoryPage(2048));
}

Both calls resolve as because their arguments are rvalues. moves the resources from the argument into ‘s internal objects using ‘s move constructor. In older versions of C++, the same program would generate copies of the argument since the copy constructor of would be called instead.

As I said earlier, is called when the argument is an lvalue:

#include <vector>
using namespace std;
int main()
{
vector<MemoryPage> vm;
MemoryPage mp1(1024);//lvalue
vm.push_back(mp); //push_back(const T&)
}

However, you can enforce the selection of even in this case by casting an lvalue to an rvalue reference using :

//calls push_back(T&&)

vm.push_back(static_cast<MemoryPage&&>(mp));

Alternatively, use the new standard function for the same purpose:

vm.push_back(std::move(mp));//calls push_back(T&&)

It may seem as if is always the best choice because it eliminates unnecessary copies. However, remember that empties its argument. If you want the argument to retain its state after a call, stick to copy semantics. Generally speaking, don’t rush to throw away the copy constructor and the copy assignment operator. In some cases, the same class could be used in a context that requires pure copy semantics, whereas in other contexts move semantics would be preferable.

In Conclusion

C++11 is a different and better C++. Its rvalue references and move-oriented Standard Library eliminate many unnecessary copy operations, thereby improving performance significantly, with minimal, if any, code changes. The move constructor and the move assignment operator are the vehicles of move operations. It takes a while to internalize the principles of move semantics – and to design classes accordingly. However, the benefits are substantial. I would dare predicting that other programming languages will soon find ways to usher-in move semantics too.

Danny Kalev is a certified system analyst by the Israeli Chamber of System Analysts and software engineer specializing in C++. Kalev has written several C++ textbooks and contributes C++ content regularly on various software developers’ sites. He was a member of the C++ standards committee and has a master’s degree in general linguistics.

See also:

 











Rental harmony[1][2] is a kind of a fair division problem in which indivisible items and a fixed monetary cost have to be divided simultaneously. The housemates problem[3][4] and room-assignment-rent-division[5][6] are alternative names to the same problem.[7][8]:305–328

In the typical setting, there are partners who rent together an -room house for cost fixed by the homeowner. Each housemate may have different preferences — one may prefer a large room, another may prefer a room with a view to the main road, etc. The following two problems should be solved simultaneously:

  • (a) Assign a room to each partner,
  • (b) Determine the amount each partner should pay, such that the sum of payments equals the fixed cost.

There are several properties that we would like the assignment to satisfy.

  • Non-negativity (NN): all prices must be 0 or more: no partner should be paid to get a room.
  • Envy-freeness (EF): Given a pricing scheme (an assignment of rent to rooms), we say that a partner prefers a given room if he believes that the parcel of room+rent is weakly better than all other parcels. EF means that every partner prefers his allotted room. I.e, no partner would like to take another room at the rent assigned to that room.
  • Pareto-efficiency (PE): No other assignment of partners to rooms is weakly better for all partners and strictly better for at least one partner (given the price-vector).

Envy-freeness implies Pareto-efficiency. Proof: Suppose by contradiction that there exists an alternative assignment, with the same price-vector, that is strictly better for at least one partner. Then, in the current allocation, that partner is envious.

The rental-harmony problem has been studied under two different assumptions on the partners' preferences:

  • In the ordinal utility version, each partner has a preference relation on bundles [room,price]. Given a price-vector, the partner should only be able to say which room (or rooms) he prefers to rent at that price.
  • In the cardinal utility version, each partner has a vector of monetary valuations. The partner should say, for each room, exactly how much money he is willing to pay for that room. The partner is assumed to have quasilinear utility, i.e., if he values the room as and pays , his net utility is .

The cardinal assumption implies the ordinal assumption, since given a valuation vector it is always possible to construct a preference relation. The ordinal assumption is more general and puts less mental burden on the partners.

Ordinal version[edit]

Su: one person per room[edit]

The protocol by Francis Su makes the following assumptions on the preferences of the partners:

  1. Good house: In any partition of the rent, each person finds at least one room+rent parcel acceptable.
  2. No externalities: The preference relation of each partner depends on the rooms and the rents, but not on choices made by others.
  3. Miserly partners: every partner weakly prefers a free room (a room with a rent of 0) over any other room.
  4. Topologically closed preference sets: A partner who prefers a room for a convergent sequence of prices, prefers that room at the limiting price.

Normalize the total rent to 1. Then each pricing scheme is a point in an -dimensional simplex with vertices in . Su's protocol operates on a dualized version of this simplex in a similar way to the Simmons–Su protocols for cake-cutting: for every vertex of a triangulation of the dual simplex, which corresponds to a certain price scheme, it asks the owning partner "which room do you prefer in that pricing scheme?". This results in a Sperner coloring of the dual simplex, and thus there exists a small sub-simplex which corresponds to an approximate envy-free assignment of rooms and rents.

Su's protocol returns a sequence of allocations which converges to an envy-free allocation. The prices are always non-negative. Hence, the outcome satisfies the NN and EF requirements.

[9] and [10] provide popularized explanations of Su's Rental Harmony protocol.

[11] and [12] provide on-line implementations.

Azriely and Shmaya: room-mates[edit]

Azriely and Shmaya[2] generalize Su's solution to a situation in which the capacity of each room may be larger than one (i.e., several partners can live in the same room).

They prove the existence of envy-free allocations in the following conditions:

  1. Good house: Every partner likes at least one of the rooms given each price vector.
  2. No externalities: All partners like free rooms.
  3. Miserly partners: The preferences are continuous in prices.

The main tools used in the proof are:

Their solution is constructive in the same sense as Su's solution - there is a procedure that approximates the solution to any given precision.

General properties of ordinal protocols[edit]

A. In both Su's solution and Azrieli&Shmaya's solution, the preference relation of each partner is allowed (but not obliged) to depend on the entire price-vector. I.e, a partner may say "if room A costs 1000, then I prefer room B to room C, but if room A costs only 700, then I prefer room C to room B".

There are several reasons such generality can be useful.[2]

  1. Future planning. Suppose the partner thinks that room A is best, then B, then C. If A is expensive, the partner settles on B. But if A is cheaper, the partner might buy C (which is the cheapest), and then save some money and switch to A.
  2. Incomplete information. The price-vector may give the partner some indication on the quality of rooms.
  3. Neighbors. The price-vector may allow the partner to predict, to some extent, what kind of people are going to live in the neighboring rooms.
  4. Irrationality effects, e.g. framing effects. If room B and room C are of the same quality and have the same price, then the partner may buy A. But, if room B becomes more expensive, then the partner may switch to C, thinking that "it is the same as B but in bargain price..".

B. Both Su's solution and Azrieli&Shmaya's solution make a "Miserly partners" assumption - they assume that a partner always prefers a free room to a non-free room. This assumption is strong and not always realistic. If one of the rooms is very bad, it is possible that some partners will not want to live in that room even for free. This is easy to see in the cardinal version: if you believe that room A is worth 0 and room B is worth 100, and room A is free and room B costs 50, then you certainly prefer room B.

Su[1] suggests to weaken this assumption in the following way: each partner never chooses the most expensive room if there is a free room available. This does not require the person to choose the free room. In particular, this will hold if a person always prefers a free room to a room costing at least of the total rent. However, even this weakened assumption might be unrealistic, as in the above example.[8]:320–321

Cardinal version[edit]

As explained above, the input to the cardinal version is a matrix of bids: every partner has to submit a bid to each room, saying how much (in dollars) this room is worth for him.

A key notion in the cardinal solutions is a maxsum (aka utilitarian) allocation. This is an allocation of partners to rooms, that maximizes the sum of bids. The problem of finding a maxsum allocation is known as the assignment problem, and it can be solved by the Hungarian algorithm in time (where is the number of partners). Every EF allocation is maxsum and every maxsum allocation is PE.[4]

Incompatibility of EF and NN[edit]

The two requirements of envy-freeness and non-negative payments are not always compatible. For example, suppose the total cost is 100 and the valuations are:

Room 1Room 2
Partner 11500
Partner 214010

Here, the only maxsum allocation is giving room 1 to partner 1 and room 2 to partner 2. In order to make sure partner 2 does not envy, partner 1 must pay 115 and partner 2 must pay -15.

In this example, the sum of valuations is more than the total cost. If the sum of valuations equals the total cost, and there are two or three partners, then there always exists an EF and NN allocation.[4]:110–111 But if there are four or more partners, then again EF and NN might be incompatible, as in the following example (see [8]:318–319 for proof):

Room 1Room 2Room 3Room 4
Partner 13634300
Partner 23136330
Partner 33430360
Partner 43233350

Note that this example does not occur in the ordinal version, since the ordinal protocols make the "Miserly Partners" assumption - partners always prefer free rooms. When this assumption holds, there always exists an EF+NN allocation. But, in the above example, the assumption does not hold and an EF+NN allocation does not exist. Therefore, the protocols in the cardinal version have to compromise between EF and NN. Each protocol makes a different compromise.

Brams and Kilgour: NN but not EF[edit]

Brams and Kilgour[8]:305–328[13] suggest the Gap Procedure:

  1. Calculate a maxsum allocation.
  2. If the max-sum is less than the total cost, then the problem is unsolvable, since the partners do not want to pay the total amount required by the houseowner.
  3. If the max-sum exactly equals the total cost, then the rooms are allocated and the partners pay their valuations.
  4. If the max-sum is more than the total cost, then the prices are lowered based on the gap between these prices and the next-lowest valuations (see the book for more details).

The idea behind the last step is that the next-lowest valuations represent the "competition" on the rooms. If there a room is more wanted by the next-highest bidder, then it should cost more. This is similar in spirit to the Vickrey auction. However, while in the Vickrey auction the payment is entirely independent of the partner's bid, in the Gap procedure the payment is only partially independent. Therefore, the Gap procedure is not strategyproof.

The Gap Procedure always assignes non-negative prices. Because the assignment is maxsum, it is obviouly also Pareto-efficient. However, some partners may be envious. I.e, the Gap procedure satisfies NN and PE but not EF.

Moreover, the Gap Procedure may return non-envy-free allocations, even when EF allocations exist. Brams relates to this problem saying that: "Gap prices do take into account the competitiveness of bidding for goods, which makes the pricing mechanism market-oriented. Although envy-freeness is a desirable property, I prefer a marketlike mechanism when there is a conflict between these two properties; partners should pay more when bids are competitive, even at the sacrifice of causing envy".[8]:321

Haake and Raith and Su: EF but not NN[edit]

Haake et al.[7] present the Compensation Procedure. The problem it solves is more general than the rental-harmony problem in certain aspects:

  • The number of indivisible items to divide (m) may differ than the number of partners (n).
  • There can be arbitrary constraints on bundles of items, as long as they are anonymous (do not differentiate between partners based on their identity). For example, there can be no constraint at all, or a constraint such as "each partner must receive at least a certain number of items", or "some items must be bundled together" (e.g. because they are land-plots that must remain connected), etc.
  • The total "cost" can also be positive, which means that there is also some money to share. This is characteristic of inheritance division scenarios. Similarly, the "items" can have negative utility (e.g., they can represent indivisible chores).

There is a "qualification requirement" for a partner: the sum of his bids must be at least the total cost.

The procedure works in the following steps.

  1. Find a maxsum (utilitarian) allocation - an allocation with a highest sum-of-utilities that satisfies the constraints on bundles of items. If there are no constraints, then an allocation that gives each item to the partner with the highest valuation is maxsum. If there are constraints (such as "at least one item per partner"), then a maxsum allocation might be more difficult to find.
  2. Charge from each partner the value of the bundle allocated to him. This creates the initial pool of money.
  3. Pay the cost from the initial pool. If all partners satisfy the qualification requirement, then the money in the pool is sufficient, and there may be some remaining surplus.
  4. Eliminate envy by compensating envious partners. There are at most rounds of compensation. The procedure is fully descriptive and says explicitly which compensations should be made, and in what order. Moreover, it is simple enough to be carried out without computer support.
  5. The sum of compensations made in all rounds is the smallest sum that is required to eliminate envy, and it never exceeds the surplus. If some surplus remains, it can be divided in any way that does not create envy, e.g., by giving an equal amount to each partner (the paper discusses other options that may be considered "fairer").

When there are many item and complex constraints, the initial step - finding a maxsum allocation - may be difficult to calculate without a computer. In this case, the Compensation Procedure may start with an arbitrary allocation. In this case, the procedure might conclude with an allocation that contains envy-cycles. These cycles can be removed by moving bundles along the cycle. This strictly increases the total sum of utilities. Hence, after a bounded number of iterations, a maxsum allocation will be found, and the procedure can continue as above to create an envy-free allocation.

The Compensation Procedure might charge some partners a negative payment (i.e., give the partners a positive amount of money). This means that the Compensation Procedure is EF (hence also PE) but not NN. The authors say:

"we do not preclude the possibility that an individual may end up being paid by the others to take a bundle of goods. In the context of fair division, we do not find this problematic at all. Indeed, if a group does not wish to exclude any of its members, then there is no reason why the group should not subsidize a member for receiving an undesired bundle. Moreover, the qualification requirement guarantees that subsidization is never a consequence of a player's insufficient valuation of the complete set of objects to be distributed".[7]:746

However, other authors claim that, in the usual housemates scenario:

"a housemate who is assigned a room with a negative room rent is subsidized by some of other housemates. In such a situation, some housemates may prefer to leave the room with negative room rent unused and to exclude the housemate who is assigned that room, because they may receive larger discount. In order to avoid such a situation, negative room rents must be avoided".[4]

Abdulkadiroglu and Sonmez and Unver: EF and NN if possible[edit]

Abdulkadiroğlu et al.[5] suggest a market-based approach. It is a combination of an ascending auction and a descending auction. It is simplest to describe as a continuous-price auction:

  1. Initialize the price of each room to of the total house cost.
  2. Calculate the demand-set of each partner: the room or set of rooms he likes most at the current prices.
  3. Calculate the set of over-demanded rooms (rooms that are demanded by more partners than the number of rooms; see the paper for exact definition).
  4. Increase the price of all over-demanded rooms in the same rate;
  5. Simultaneously, decrease the price of all other rooms in the same rate, such that the sum of prices of all rooms always equals the total cost.
  6. At each instant, update the demand of each partner and the set of over-demanded rooms.
  7. When the set of over-demanded rooms is empty, stop and apply Hall's marriage theorem to allocate to each partner a room in their demand-set.

In practice, it is not necessary to change the price continuously, since the only interesting prices are prices in which the demand-sets of one or more partners change. It is possible to calculate the set of interesting prices in advance, and convert the continuous-price auction to a discrete-price auction. This discrete-price auction stops after a finite number of steps.[5]:525–528

The returned allocation is always envy-free. The prices may be negative, like in the procedure of Haake et al. However, in contrast to that procedure, the prices are non-negative if there exists an EF allocation with non-negative prices.

Sung and Vlach: EF and NN if possible[edit]

Sung and Vlach[4] prove that every envy-free allocation is maxsum, and every maxsum allocation is envy-free for some selection of the price-vector. Based on this proof, they propose the following algorithm:

  1. Find a maxsum allocation.
  2. Find a minsum price-vector (a vector in which the sum of prices is minimized), subject to the envy-freeness constraint. Such price-vector is a solution of a linear programming problem, and it can be found by the Bellman–Ford algorithm.
  3. If the min-sum equals the total cost, implement the maxsum allocation with the minsum prices and finish.
  4. If the min-sum is less than the total cost, then increase all prices in a constant rate until the sum equals the total cost (i.e., add to each price: ). Changing all prices by the same amount ensures that the assignment is still envy-free.
  5. If the min-sum is more than the total cost, then there is no solution satisfying both NN and EF. There are several possible ways to proceed:
    • Decrease all prices in a constant rate until the sum equals the total cost (i.e., subtract from each price: ). Some prices will necessarily be negative, as in the solution of Haake et al.
    • Decrease only the positive prices in a constant rate, until the sum equals the total cost. Here, the prices do not change by the same amount, so some partners will necessarily envious, as in the solution of Brams and Kilgour. However, in this solution, the envious partners get their room for free.

The runtime complexity of both finding maxsum allocation and finding minsum prices is .

The solution of Sung and Vlach seems to have all the desirable properties of the previous protocols, i.e.: PE and EF and NN (if possible) and polynomial run-time, and in addition, it guarantees that every envious partner gets a free room.[14] provides an implementation of a similar solution, also based on solving a linear-programming problem but citing a different paper.

[edit]

All protocols surveyed so far assume that the partners reveal their true valuations. They are not strategyproof - a partner can gain by reporting false valuations. Indeed, strategyproofness is incompatible with envy-freeness: there is no deterministic strategyproof protocol that always returns an envy-free alloction. This is true even when there are only two partners and when the prices are allowed to be negative. Proof: Assume that the total cost is 100 and the partners' valuations are as below (where are parameters and ):

Room 1Room 2
Partner 1100x
Partner 2100y

The only maxsum allocation is giving room 1 to partner 1 and room 2 to partner 2. Let be the price of room 2 (so that the price of room 1 is ). To ensure partner 1 does not envy, we must have . To ensure partner 2 does not envy, we must have .

Suppose a deterministic protocol sets the price to some value in . If the price is more than , then partner 2 has an incentive to report a lower value of , which is still above , in order to push his payment down towards . Similarly, if the price is less than , then partner 1 has an incentive to report a higher value of , which is still below , in order to push the payment of partner 2 up towards (and thus push his own payment down). Hence, the mechanism cannot be strategyproof.

Researchers have coped with this impossibility in two ways.

Sun and Yang: Changing the problem[edit]

There is a variant of the problem in which, instead of assuming that the total house cost is fixed, we assume that there is a maximum cost for each room. In this variant, a strategyproof mechanism exists: the deterministic allocation-rule selecting the min-sum cost is strategyproof.[15]

This result can be generalized for greater flexibility on the indivisible objects, and a proof of coalitional strategy-proofness.[16][17]

Dufton and Larson: Using randomization[edit]

Going back to the original rental-harmony problem, it is possible to consider randomized mechanisms. A randomized mechanism returns a probability distribution over room-assignments and rent-divisions. A randomized mechanism is truthful in expectation if no partner can increase the expected value of his utility by mis-reporting his valuations to the rooms. The fairness of a randomized mechanism can be measured in several ways:[6]

1. Ex-ante Envy-Freeness means that no partner envies the lottery of any other partner. This condition is trivial to achieve in a truthful mechanism: randomise over all possible allocations with equal probability and charge each partner of the total cost. But this condition is not appealing, since there is a large chance that in the final outcome, many partners will be envious. They may not be comforted by the fact that the lottery has been fair.

2. Guaranteed Probability of Envy-Freeness (GPEF) means that there is a certain probability such that, regardless of the partners' valuations, with probability at least , the final outcome will be envy-free. It is possible to achieve a GPEF of in the following way: find an envy-free assignment; choose an integer at random; and move each partner cyclically rooms to the right. This randomized mechanism is truthful-in-expectation, since every partner has an equal probability to land in each room and the expected payment is of the total cost, regardless of the partner's bid. The probability of having an EF allocation is the probability that , which is exactly . This is not encouraging, since the probability of envy-freeness converges to 0 when the number of partners grows. But it is impossible to do better: in every truthful-in-expectation mechanism, the GPEF is at most .

3. Expected Number of Envy-Free partners (ENEF) means that there is a certain integer such that, if we average the number of partners who do not envy in all possible outcomes of the mechanism, then regardless of the partners' valuations, the expectation is at least . The ENEF criterion seems more appropriate than the GPEF criterion, because it measures not only the probability of entire envy-freeness, but also the quality of the cases in which the allocation is not entirely envy-free. The maximum ENEF of a truthful-in-expectation mechanism is at most . It is possible to attain this bound for . For , there is a truthful-in-expectation mechanism that almost attains this bound: the ENEF is . The general idea is as follows. Use the VCG mechanism to calculate a maxsum assignment and payments. Select one partner at random. Ignore that partner and use VCG again. Combine the outcomes in a way which guarantees that the total payment equals the total cost (see the paper for details). It is possible to show that: (a) the mechanism is truthful-in-expectation; (b) all partners except the ignored partner do not envy. Hence, the ENEF is . Simulations show that in about 80% of the cases, the GPEF of this mechanism is also at its maximum of .

Andersson and Ehlers and Svensson: Attaining partial-strategyproofness[edit]

A possible relaxation of the strategyproofness requirement is to try to minimize the "degree of manipulability".[18] This is defined by counting, for each profile, the number of agents who can manipulate the rule. Maximally-preferred fair allocation rules are the minimally (individually and coalitionally) manipulable fair and budget-balanced allocation rules according to this new concept. Such rules choose allocations with the maximal number of agents for whom the utility is maximized among all fair and budget-balanced allocations.

See also[edit]

  • Fair item assignment - a fair division problem where there are only indivisible items to share, with no monetary transfers.

References[edit]

  1. ^ abSu, F. E. (1999). "Rental Harmony: Sperner's Lemma in Fair Division". The American Mathematical Monthly. 106 (10): 930. doi:10.2307/2589747. JSTOR 2589747. 
  2. ^ abcAzrieli, Yaron; Shmaya, Eran (2014). "Rental harmony with roommates". Journal of Economic Theory. 153: 128. doi:10.1016/j.jet.2014.06.006. 
  3. ^Potthoff, Richard F. (2002). "Use of Linear Programming to Find an Envy-Free Solution Closest to the Brams–Kilgour Gap Solution for the Housemates Problem". Group Decision and Negotiation. 11 (5): 405. doi:10.1023/A:1020485018300. 
  4. ^ abcdeSung, Shao Chin; Vlach, Milan (2004). "Competitive envy-free division". Social Choice and Welfare. 23. doi:10.1007/s00355-003-0240-z. 
  5. ^ abcAbdulkadiroğlu, Atila; Sönmez, Tayfun; Utku Ünver, M. (2004). "Room assignment-rent division: A market approach". Social Choice and Welfare. 22 (3): 515. doi:10.1007/s00355-003-0231-0. 
  6. ^ abLachlan Dufton and Kate Larson (2011). "Randomised Room Assignment-Rent Division"(PDF). Proceedings of the IJCAI-2011 Workshop on Social Choice and Artificial Intelligence. IJCAI. pp. 34–39. Retrieved 5 March 2016. 
  7. ^ abcHaake, Claus-Jochen; Raith, Matthias G.; Su, Francis Edward (2002). "Bidding for envy-freeness: A procedural approach to n-player fair-division problems". Social Choice and Welfare. 19 (4): 723. doi:10.1007/s003550100149. 
  8. ^ abcdeSteven J. Brams (2008). Mathematics and Democracy: Designing Better Voting and Fair-Division Procedures. Princeton, NJ: Princeton University Press. ISBN 9780691133218. 
  9. ^Sun, Albert. "To Divide the Rent, Start With a Triangle". The New York Times. Retrieved 26 August 2014. 
  10. ^Procaccia, Ariel. "Fair division and the whining philosophers problem". Turing's Invisible Hand. Retrieved 26 August 2014. 
  11. ^"Francis Su's Fair Division Page". Math.hmc.edu. Retrieved 2017-01-05. 
  12. ^"Divide Your Rent Fairly". The New York Times. Retrieved 2017-01-05. 
  13. ^Brams, Steven J.; Kilgour, D. Marc (2001). "Competitive Fair Division". Journal of Political Economy. 109 (2): 418. doi:10.1086/319550. 
  14. ^[1][dead link]
  15. ^Sun, Ning; Yang, Zaifu (2003). "A general strategy proof fair allocation mechanism". Economics Letters. 81: 73. doi:10.1016/s0165-1765(03)00151-4. 
  16. ^Andersson, Tommy; Svensson, Lars-Gunnar (2008). "Non-manipulable assignment of individuals to positions revisited". Mathematical Social Sciences. 56 (3): 350. doi:10.1016/j.mathsocsci.2008.05.004. 
  17. ^Andersson, Tommy (2009). "A general strategy-proof fair allocation mechanism revisited". Economics Bulletin: 1719–1724. 
  18. ^Andersson, Tommy; Ehlers, Lars; Svensson, Lars-Gunnar (2014). "Budget balance, fairness, and minimal manipulability". Theoretical Economics. 9 (3): 753. doi:10.3982/te1346. 

Leave a Comment

(0 Comments)

Your email address will not be published. Required fields are marked *