We study the problem of multi-dimensional revenue maximization when selling m items to a buyer that has additive valuations for them, drawn from a (possibly correlated) prior distribution. Unlike traditional Bayesian auction design, we assume that the seller has a very

restricted knowledge of this prior: they only know the mean μ_j and an upper bound σ_j on the standard deviation of each item’s marginal distribution. Our goal is to design mechanisms that achieve good revenue against an ideal optimal auction that has full knowledge of the distribution in advance. Informally, our main contribution is a tight quantification of the interplay between the dispersity of the priors and the aforementioned robust approximation ratio. Furthermore, this can be achieved by very simple selling mechanisms. 

More precisely, we show that selling the items via separate price lotteries achieves an O(log r) approximation ratio where r = max_j(σ_j/μ_j) is the maximum coefficient of variation across the items. If forced to restrict ourselves to deterministic mechanisms, this guarantee degrades to O(r²). Assuming independence of the item valuations, these ratios can be further improved by pricing the full bundle. For the case of identical means and variances, in particular, we get a guarantee of O(log(r/m)) which converges to optimality as the number of items grows large. We demonstrate the optimality of the above mechanisms by providing matching lower bounds. Our tight analysis for the deterministic case resolves an open gap from the work of Azar and Micali [ITCS’13].

Consensus halving refers to the problem of dividing a resource into two parts so that every agent values both parts equally. Prior work has shown that when the resource is represented by an interval, a consensus halving with at most n cuts always exists, but is hard to compute even for agents with simple valuation functions. In this paper, we study consensus halving in a natural setting where the resource consists of a set of items without a linear ordering. When agents have additive utilities, we present a polynomial-time algorithm that computes a consensus halving with at most n cuts, and show that n cuts are almost surely necessary when the agents' utilities are drawn from probabilistic distributions. On the other hand, we show that for a simple class of monotonic utilities, the problem already becomes PPAD-hard. Furthermore, we compare and contrast consensus halving with the more general problem of consensus k-splitting, where we wish to divide the resource into k parts in possibly unequal ratios, and provide some consequences of our results on the problem of computing small agreeable sets.

We study the efficiency of sequential multiunit auctions with two buyers and complete information. For general valuation functions, we show that the price of anarchy is exactly 1/T for auctions with T items for sale. For concave valuation functions, we show that the price of anarchy is bounded below by 1 - 1/e ≈ 0.632. This bound is asymptotically tight as the number of items sold tends to infi nity.

Public goods are often either over-consumed in the absence of regulatory mechanisms, or remain completely unused, as in the Covid-19 pandemic, where social distance constraints are enforced to limit the number of people who can share public spaces. In this work, we plug this gap through market mechanisms designed to efficiently allocate capacity constrained public goods. To design these mechanisms, we leverage the theory of Fisher markets, wherein each agent is endowed with an artificial currency budget that they can spend to avail public goods. While Fisher markets provide a strong methodological backbone to model resource allocation problems, their applicability is limited to settings involving two types of constraints - budgets of individual buyers and capacities of goods. Thus, we introduce a modified Fisher market, where each individual may have additional physical constraints, characterize its solution properties and establish the existence of a market equilibrium. Furthermore, to account for additional constraints we introduce a social convex optimization problem where we perturb the budgets of agents such that the KKT conditions of the perturbed social problem establishes equilibrium prices. Finally, to compute the budget perturbations we present a fixed point scheme and illustrate convergence guarantees through numerical experiments. Thus, our mechanism, both theoretically and computationally, overcomes a fundamental limitation of classical Fisher markets, which only consider capacity and budget constraints.

We consider the classical machine scheduling, where n jobs need to be scheduled on m machines, and where job j scheduled on machine i contributes p_i,j ∈ R to the load of machine i, with the goal of minimizing the makespan, i.e., the maximum load of any machine in the

schedule. We study inefficiency of schedules that are obtained when jobs arrive sequentially one by one, and the jobs choose themselves the machine on which they will be scheduled, aiming at being scheduled on a machine with small load. We measure the inefficiency of a schedule as the ratio of the makespan obtained in the worst-case equilibrium schedule, and of the optimum makespan. This ratio is known as the sequential price of anarchy (SPoA). We also introduce two alternative inefficiency measures, which allow for a favorable choice of the order in which the jobs make their decisions. As our first result, we disprove the conjecture of [22] claiming that the sequential price of anarchy for m = 2 machines is at most 3. We show that the sequential price of anarchy grows at least linearly with the number n of players, assuming arbitrary tie-breaking rules. That is, we show SPoA ∈ Ω(n). Complementing this result, we show that SPoA ∈ O(n), reducing previously known exponential bound for 2 machines. Furthermore, we show that there exists an order of the jobs, resulting in makespan that is at most linearly larger than the optimum makespan. To the end, we show that if an authority can change the order of the jobs adaptively to the decisions made by the jobs so far (but cannot influence the decisions of the jobs), then there exists an adaptive ordering in which the jobs end up in an optimum schedule.

We consider a sequential decision model over multi-tier supply chain networks and show that in particular, for series parallel networks, there is a unique equilibrium. We provide a linear time algorithm to compute the equilibrium and study the impact and invariant of the

network structure to the total trade flow and social welfare. Sequential decision making is a well-observed phenomenon in supply chains. Firms at the top tier typically need to make decisions on the quantity and the price to sell to firms in the next tier, and the buying firms then decide how much to buy from which suppliers, and continue to pass on the goods by determining the quantity and price for firms at the next level. One needs to analyze the subgame perfect equilibria of the market, where each firm internalizes the decisions of all the firms downstream and compete with all the firms of the same tier. The length and the number of trading routes are the two main factors that impact the efficiency of a supply chain network. On one hand, a large variety of options to trade indicates a high degree of competition. On the other hand, a long trading path causes double, triple and higher degree marginalization problems. We study series parallel networks because they are rich enough for investigating the factors described above and simple enough for characterizing the equilibrium outcomes. The unique equilibrium and equilibrium comparative statics are derived from a closed-form expression between the price and quantity, by judiciously using the structure of series parallel networks and the concavity of the firm utilities.

Finding the equilibrium of a routing game requires perfect knowledge of the costs of each edge of the network. If these costs are unknown and the game is repeated day after day, is it possible to learn them? We show that, to achieve this, randomness in the traffic demand is necessary. Different values of this demand will induce exploration of different paths and, as a consequence, learning of their costs. Our main result shows that when demand is sufficiently variable, equilibrium behavior converges to full-information behavior when the routing network belongs to the class of series-parallel networks. When it is not the case, we show that optimal paths may remain unused at every equilibrium, which can imply arbitrarily large losses of efficiency.