This thesis studies four independent resource allocation problems with different assumptions on information available to the central planner, and strategic considerations of the agents present in the system.
We start off with an online, non-strategic agents setting in Chapter 1, where we study the dynamic pricing and learning problem under the Bass demand model. The main objective in the field of dynamic pricing and learning is to study how a seller can maximize revenue by adjusting price over time based on sequentially realized demand. Unlike most existing literature on dynamic pricing and learning, where the price only affects the demand in the current period, under the Bass model, price also influences the future evolution of demand. Finding arevenue-maximizing dynamic pricing policy in this model is non-trivial even in the full information case, where model parameters are known. We consider the more challenging incomplete information problem where dynamic pricing is applied in conjunction with learning the unknown model parameters, with the objective of optimizing the cumulative revenues over a given selling horizon of length 𝑻. Our main contribution is an algorithm that satisfies a high probability regret guarantee of order 𝑚²/³; where the market size 𝑚 is known a priori. Moreover, we show that no algorithm can incur smaller order of loss by deriving a matching lower bound.
We then switch our attention to a single round, strategic agents setting in Chapter 2, where we study a multi-resource allocation problem with heterogeneous demands and Leontief utilities. Leontief utility function captures the idea that for certain resource allocation settings, the utility of marginal increase in one resource depends on the availabilities of other resources. We generalize the existing literature on this model formulation to incorporate more constraints faced in real applications, which in turn requires new algorithm design and analysis techniques. The main contribution of this chapter is an allocation algorithm that satisfies Pareto optimality, envy-freenss, strategy-proofness, and a notion of sharing incentive.
In Chapter 3, we study a single round, non-strategic agent setting, where the central planner tries to allocate a pool of items to a set of agents who each has to receive a prespecified fraction of all items. Additionally, we want to ensure fairness by controlling the amount of envy that agents have with the final allocations. We make the observation that this resource allocation setting can be formulated as an Optimal Transport problem, and that the solution structure displays a surprisingly simple structure. Using this insight, we are able to design an allocation algorithm that achieves the optimal trade-off between efficiency and envy.
Finally, in Chapter 4 we study an online, strategic agent setting, where similar to the previous chapter, the central planner needs to allocate a pool of items to a set of agents who each has to receive a prespecified fraction of all items. Unlike in the previous chapter, the central planner has no a priori information on the distribution of items. Instead, the central planner needs to implicitly learn these distributions from the observed values in order to pick a good allocation policy. Additionally, an added challenge here is that the agents are strategic with incentives to misreport their valuations in order to receive better allocations. This sets our work apart both from the online auction mechanism design settings which typically assume known valuation distributions and/or involve payments, and from the online learning settings that do not consider strategic agents. To that end, our main contribution is an online learning based allocation mechanism that is approximately Bayesian incentive compatible, and when all agents are truthful, guarantees a sublinear regret for individual agents' utility compared to that under the optimal offline allocation policy.
| Identifer | oai:union.ndltd.org:columbia.edu/oai:academiccommons.columbia.edu:10.7916/q7nx-pk03 |
| Date | January 2022 |
| Creators | Yin, Steven |
| Source Sets | Columbia University |
| Language | English |
| Detected Language | English |
| Type | Theses |
Page generated in 0.0033 seconds