EconCS Seminar

 

Lecturer: 

Prof. Uriel Feige (Weizmann)

Title: 

A bidding game for allocation of indivisible goods

Abstract: 

We consider allocation of indivisible goods to agents with possibly unequal entitlements, in a setting without payments. We shall briefly survey some fairness notions associated with such settings. There after we shall present an allocation mechanism referred to as the bidding game. The mechanism satisfies natural procedural fairness criteria, and the question that we ask is to what extent the final allocation that it outputs satisfies ex-post fairness criteria. The ex-post fairness notion that we shall consider is that of the anyprice share (APS). For simple classes of valuation functions (unit demand, identical items), we show strategies for the agents that guarantee that in the bidding game they receive at least their APS. For other classes of valuation functions (additive, submodular), we show strategies that guarantee at least a handsome fraction of the APS. These results imply the existence of allocations that give agents a handsome fraction of the APS, and moreover, lead to polynomial time algorithms for finding such allocations.

Location: 

Room 130, Feldman Building, Edmond J. Safra Campus.

 

Click here to add the EconCS Seminar to your Google Calendar