Papers

The classic cake cutting problem concerns the fair allocation of a heterogeneous resource among interested agents. In this paper, we study a public goods variant of the problem, where instead of competing with one another for the cake, the agents all share the same subset of the cake which must be chosen subject to a length constraint. We focus on the design of truthful and fair mechanisms in the presence of strategic agents who have piecewise uniform utilities over the cake. On the one hand, we show that the leximin solution is truthful and moreover maximizes an egalitarian welfare measure among all truthful and position oblivious mechanisms. On the other hand, we demonstrate that the maximum Nash welfare solution is truthful for two agents but not in general. Our results assume that mechanisms can block each agent from accessing parts that the agent does not claim to desire; we provide an impossibility result when blocking is not allowed.

poster session 2 @ blue 6, poster session 11 @ blue 6, oral session 2 @ blue 6, poster session 2, poster session 11, oral session 2

We study online task assignment problem with reusable resources, motivated by practical applications such as ridesharing, crowdsourcing and job hiring. In the problem, we are given a set of offline vertices~(agents), and, at each time, an online vertex~(task) arrives randomly according to a known time-dependent distribution. Upon arrival, we assign the task to agents immediately and irrevocably. The goal of the problem is to maximize the expected total profit produced by completed tasks. The key features of our problem are (1) an agent is reusable, i.e., an agent comes back to the market after completing the assigned task, (2) an agent may reject the assigned task to stay the market, and (3) a task may accommodate multiple agents. The setting generalizes that of existing work in which an online task is assigned to one agent under (1). In this paper, we propose an online algorithm that is $1/2$-competitive for the above setting, which is tight. Moreover, when each agent can reject assigned tasks at most $\Delta$ times, the algorithm is shown to have the competitive ratio $\Delta/(3\Delta-1)\geq 1/3$. We also evaluate our proposed algorithm with numerical experiments.

poster session 2 @ blue 6, poster session 11 @ blue 6, oral session 2 @ blue 6, poster session 2, poster session 11, oral session 2

We study multi-unit auctions in social networks, where each buyer has a fixed budget and can spread the sale information to the network neighbors. We design a mechanism encouraging buyers to report their valuations truthfully and spread the sale information. Our design uses the idea of the clinching mechanism to decide the transaction price and can be viewed as a network version of the mechanism. Most of the previous clinching mechanisms search for the transaction prices by increasing the current price. Our mechanism directly computes the transaction prices in polynomial time. Furthermore, the mechanism applies a technique to iteratively activate new buyers in the network. This ensures utility preservations of the buyers and benefits the seller. We prove key properties of our mechanism, such as no-positive-transfers, individual rationality, incentive compatibility, non-wastefulness and social welfare preservation.

poster session 2 @ blue 6, poster session 11 @ blue 6, oral session 2 @ blue 6, poster session 2, poster session 11, oral session 2