Fair Allocation of resources is a fundamental problem that has been studied by the Economics and Computer Science communities. This problem consists of dividing a set of resources among a set of agents in a fair way. Fairness resists a single definition and various notions of fairness have been defined and investigated in literature. In this talk we consider two fairness notions – AnyPrice Share (APS) and Nash Social Welfare (NSW). We study the algorithmic aspects of these fairness notions when valuation functions of the agents are submodular or fractionally subadditive (XOS).

APS is a share-based notion where each agent determines a value that she thinks is fair and we have to output an allocation where the agents get this value. We will discuss a simple greedy algorithm that ensures 1/3 fraction of APS to every agent when the valuation functions of agents are submodular. This is the current best-known approximation of APS for submodular valuations. Nash social welfare is a single objective where the aim is to maximize the geometric mean of values received by the agents. I will touch upon a sublinear approximation algorithm for maximizing NSW with XOS valuation functions. This algorithm uses Capped Welfare maximization to maximize NSW. This was the first algorithm to use social welfare for maximization of Nash social welfare.

In the setting of budget feasible mechanism design, a buyer wants to purchase items from a set of sellers. Each seller i supplies one item, upon which they incur a cost of ci. The buyer wants to buy a set of items from the sellers so as to maximize a certain valuation function, subject to a knapsack constraint stating that the total cost of the items bought is at most a certain budget. The true cost ci is private information that is only known to seller i and not to the buyer. Thus, the buyer must work with the seller's reported costs. The goal is to design a mechanism that is truthful, in the sense that the sellers do not have an incentive to deviate from reporting their true costs, and budget feasible, in the sense that the total payments made to the sellers is within a given budget B.

Bei et al. considered the setting when the valuation function is XOS and gave the first polynomial time O(1) approximation for the problem. Their mechanism has essentially remained the only mechanism for XOS valuations, and requires both a demand oracle and an XOS oracle. They also showed the existence of a O(1) approximation for when the valuation function is subadditive. However, this result is existential in nature, in the sense that we do not what the mechanism is that obtains this approximation, we just know that one such mechanism exists.

In this talk, I will speak about our recent results in budget feasible mechanism design. When the valuation function is XOS, we design budget feasible mechanisms that are simpler and better, both in terms of the approximation factors they obtain and in terms of requiring weaker oracle access to the valuation function. When the valuation function is subadditive, we give the first polynomial time explicitly constructed constant factor approximation to the problem, whereas previously only an existential result was known. Moreover, we introduce a novel class of mechanism design problems that we dub generalized budget feasible mechanisms, wherein we allow more intricate payment constraints, as opposed to a single constraint on the total payment.

This talk is based on joint work with Chaitanya Swamy and Kanstantsin Pashkovich.

In budget-feasible mechanism design, a buyer wishes to procure a set of items of maximum value from self-interested rational players. We have a ground set $U$ of items, and a nonnegative valuation function v, where $v(S)$ specifies the value obtained from set $S$ of items. The entirety of current work on budget-feasible mechanisms has focussed on the single-dimensional setting, wherein each player holds a single item $e$ and incurs a private cost $c_e$ for supplying item $e$.
We introduce multidimensional budget feasible mechanism design: the universe $U$ is now partitioned into item-sets $\{G_i\}$ held by the different players, and each player $i$ incurs a private cost $c_i(S_i)$ for supplying set $S_i$ of items, which is a subset of $G_i$. A budget-feasible mechanism is a mechanism (i.e., an algorithm and a payment scheme) that is truthful, i.e., where players are incentivized to report their true costs, and where the total payment made to the players is at most some given budget $B$. The goal (as in the single-dimensional setting) is to devise a budget-feasible mechanism that procures a set of items of large value.