Zobrazeno 1 - 10
of 111
pro vyhledávání: '"Kesselheim, Thomas"'
Many classical problems in theoretical computer science involve norm, even if implicitly; for example, both XOS functions and downward-closed sets are equivalent to some norms. The last decade has seen a lot of interest in designing algorithms beyond
Externí odkaz:
http://arxiv.org/abs/2406.15180
We study online capacitated resource allocation, a natural generalization of online stochastic max-weight bipartite matching. This problem is motivated by ride-sharing and Internet advertising applications, where online arrivals may have the capacity
Externí odkaz:
http://arxiv.org/abs/2406.07757
Selling a single item to $n$ self-interested buyers is a fundamental problem in economics, where the two objectives typically considered are welfare maximization and revenue maximization. Since the optimal mechanisms are often impractical and do not
Externí odkaz:
http://arxiv.org/abs/2406.00819
Combinatorial contracts are emerging as a key paradigm in algorithmic contract design, paralleling the role of combinatorial auctions in algorithmic mechanism design. In this paper we study natural combinatorial contract settings involving teams of a
Externí odkaz:
http://arxiv.org/abs/2405.08260
The Prophet Inequality and Pandora's Box problems are fundamental stochastic problem with applications in Mechanism Design, Online Algorithms, Stochastic Optimization, Optimal Stopping, and Operations Research. A usual assumption in these works is th
Externí odkaz:
http://arxiv.org/abs/2211.08586
We study a natural combinatorial single-principal multi-agent contract design problem, in which a principal motivates a team of agents to exert effort toward a given task. At the heart of our model is a reward function, which maps the agent efforts t
Externí odkaz:
http://arxiv.org/abs/2211.05434
Autor:
Braun, Alexander, Kesselheim, Thomas
We consider prophet inequalities for XOS and MPH-$k$ combinatorial auctions and give a simplified proof for the existence of static and anonymous item prices which recover the state-of-the-art competitive ratios. Our proofs make use of a linear progr
Externí odkaz:
http://arxiv.org/abs/2211.00707
Vector norms play a fundamental role in computer science and optimization, so there is an ongoing effort to generalize existing algorithms to settings beyond $\ell_\infty$ and $\ell_p$ norms. We show that many online and bandit applications for gener
Externí odkaz:
http://arxiv.org/abs/2210.13755
We introduce a new model of combinatorial contracts in which a principal delegates the execution of a costly task to an agent. To complete the task, the agent can take any subset of a given set of unobservable actions, each of which has an associated
Externí odkaz:
http://arxiv.org/abs/2109.14260
We consider the problem of posting prices for unit-demand buyers if all $n$ buyers have identically distributed valuations drawn from a distribution with monotone hazard rate. We show that even with multiple items asymptotically optimal welfare can b
Externí odkaz:
http://arxiv.org/abs/2107.00526