We study cake cutting on a graph, where agents can only evaluate their shares relative to their neighbors. This is an extension of the classical problem of fair division to incorporate the notion of social comparison from the social sciences. We say an allocation is locally envy-free if no agent envies a neighbor’s allocation, and locally proportional if each agent values its own allocation as much as the average value of its neighbors’ allocations. We generalize the classical “Cut and Choose” protocol for two agents to this setting, by fully characterizing the set of graphs for which an oblivious single-cutter protocol can give locally envy-free (thus also locally-proportional) allocations. We study the price of envy-freeness, which compares the total value of an optimal allocation with that of an optimal, locally envy-free allocation. Surprisingly, a lower bound of Ω(√n) on the price of envy-freeness for global allocations also holds for local envy-freeness in any connected graph, so sparse graphs do not provide more ﬂexibility asymptotically with respect to the quality of envy-free allocations.
This talk is about the problem of a budget limited buyer who wants to buy a set of items, each from a different seller, to maximize her value. The budget feasible mechanism design problem aims to design a mechanism which incentivizes the sellers to truthfully report their cost, and maximizes the buyer's value while guaranteeing that the total payment does not exceed her budget. Such budget feasible mechanisms can model a buyer in a crowdsourcing market interested in recruiting a set of workers (sellers) to accomplish a task for her.
This budget feasible mechanism design problem was introduced by Singer in 2010. There have been a number of improvements on the approximation guarantee of such mechanisms since then. We consider the general case where the buyer's valuation is a monotone submodular function.
We offer two general frameworks for simple mechanisms, and by combining these frameworks, we significantly improve on the best known results for this problem, while also simplifying the analysis. For example, we improve the approximation guarantee for the general monotone submodular case from 7.91 to 5; and for the case of large markets (where each individual item has negligible value) from 3 to 2.58. More generally, given an $r$ approximation algorithm for the optimization problem (ignoring incentives), our mechanism is a $r+1$ approximation mechanism for large markets, an improvement from $2r^2$. We also provide a similar parameterized mechanism without the large market assumption, where we achieve a $4r+1$ approximation guarantee.