We study infinitely-repeated two-player zero-sum games with one-sided private information and a persistent state. Here, only one of the two players learns the state of the repeated game. We consider two models: either the state is chosen by nature, or by one of the players. For the former, the equilibrium of the repeated game is known to be equivalent to that of a one-shot public signaling game, and we make this equivalence algorithmic. For the latter, we show equivalence to one-shot team max-min games, and also provide an algorithmic reduction. We apply this framework to repeated zero-sum security games with private information on the side of the defender and provide an almost complete characterization of their computational complexity.

Motivated by demand-responsive parking pricing systems we consider posted-price algorithms for the online metrical matching problem and the online metrical searching problem in a tree metric. Our main result is a poly-log competitive posted-price algorithm for online metrical searching.

Congestion games constitute an important class of games to model resource allocation by different users. As computing an exact [18] or even an approximate [34] pure Nash equilibrium is in general PLScomplete, Caragiannis et al. [9] present a polynomial-time algorithm that computes a (2+ε)-approximate pure Nash equilibria for games with linear cost functions and further results for polynomial cost functions. We show that this factor can be improved to (1.61+ε) and further improved results for polynomial cost functions, by a seemingly simple modification to their algorithm by allowing for the cost functions used during the best response dynamics be different from the overall objective function. Interestingly,

our modification to the algorithm also extends to efficiently computing improved approximate pure Nash equilibria in games with arbitrary non-decreasing resource cost functions. Additionally, our analysis exhibits an interesting method to optimally compute universal load dependent taxes and using linear programming duality prove tight bounds on the PoA under universal taxation, e.g., 2.012 for linear congestion games and further results for polynomial cost functions. Although our approach yield weaker results than that in Bilo and Vinci [6], we remark that our cost functions are locally computable and in contrast to [6] are

independent of the actual instance of the game.

We consider a principal-expert problem in which a principal contracts one or more experts to acquire and report decision-relevant information. The principal never finds out what information is available to which expert, at what costs that information is available, or what costs the experts actually end up paying. This makes it challenging for the principal to compensate the experts in a way that incentivizes acquisition of relevant information without overpaying. We determine the payment scheme that minimizes the principal's worst-case regret relative to the first-best solution. In particular, we show that under two different assumptions about the experts' available information, the optimal payment scheme is a set of linear contracts.

We consider flows over time within the deterministic queueing model and study the solution concept of instantaneous dynamic equilibrium (IDE) in which flow particles select at every decision point a currently shortest path. The length of such a path is measured by the physical travel time plus the time spent in queues. Although IDE have been studied since the eighties, the efficiency of the solution concept is not well understood. We study the price of anarchy for this model and show an upper bound of order O(U·τ) for single-sink instances, where U denotes the total inflow volume and τ the sum of edge travel times. We complement this upper bound with a family of quite complex instances proving a lower bound of order Ω(U·logτ).

We study combinatorial auctions with n agents and m items, where the goal is to allocate the items to the agents such that the social welfare is maximized. We present a universally truthful mechanism with polynomially many queries for combinatorial auctions. Our mechanism and analysis work adaptively for all classes of valuation functions, guaranteeing $\widetilde{O}(\min(d, \sqrt{m}))$-approximation (where $\widetilde{O}$ hides a polylogarithmic factor in m) of the optimal social welfare, where d is the degree of complementarity of the valuation functions. To our knowledge, this is the first mechanism that achieves an approximation guarantee better than $\Omega(\sqrt{m})$ when the valuations exhibit any kind of complementarity.

In the allocation of resources to a set of agents, how do fairness guarantees impact social welfare? A quantitative measure of this impact is the price of fairness, which measures the worst-case loss of social welfare due to fairness constraints. While initially studied for divisible goods, recent work on the price of fairness also studies the setting

of indivisible goods.

In this paper, we resolve the price of two well-studied fairness notions in the context of indivisible goods: envy-freeness up to one good (EF1) and approximate maximin share (MMS). For both EF1 and 1/2-MMS, we show, via different techniques, that the price of fairness is O(\sqrt{n}), where n is the number of agents. From previous work, it follows that these

guarantees are tight. We, in fact, obtain the price-of-fairness results via efficient algorithms. For 1/2-MMS, our bound holds for additive valuations, whereas for EF1, it holds for the more general class of subadditive valuations. This resolves an open problem posed by Bei et al. (2019).