Britta Dorn

TCS Journal 2020 Journal Article

Placing quantified variants of 3-SAT and Not-All-Equal 3-SAT in the polynomial hierarchy

• Janosch Döcker
• Britta Dorn
• Simone Linz
• Charles Semple

AAAI Conference 2018 Conference Paper

Tool Auctions

• Janosch Döcker
• Britta Dorn
• Ulle Endriss
• Ronald de Haan
• Sebastian Schneckenburger

We introduce tool auctions, a novel market mechanism for constructing a cost-efficient assembly line for producing a desired set of products from a given set of goods and tools. Such tools can be used to transform one type of good into a different one. We then study the computational complexity of tool auctions in detail, using methods from both classical and parameterized complexity theory. While solving such auctions is intractable in general, just as for the related frameworks of combinatorial and mixed auctions, we are able to identify several special cases of practical interest where designing efficient algorithms is possible.

AAMAS Conference 2017 Conference Paper

The Atkinson Inequality Index in Multiagent Resource Allocation

• Sebastian Schneckenburger
• Britta Dorn
• Ulle Endriss

We analyse the problem of finding an allocation of resources in a multiagent system that is as fair as possible in terms of minimising inequality between the utility levels enjoyed by the individual agents. We use the well-known Atkinson index to measure inequality and we focus on the distributed approach to multiagent resource allocation, where new allocations emerge as the result of a sequence of local deals between groups of agents agreeing on an exchange of some of the items in their possession. Our results show that it is possible to design systems that provide theoretical guarantees for optimal outcomes that minimise inequality, but also that in practice there are significant computational hurdles to be overcome: finding an optimal allocation is computationally intractable—independently of the approach chosen—and large numbers of potentially highly complex deals may be required under the distributed approach. From a methodological point of view, while much work in multiagent resource allocation relies on combinatorial arguments, here we use insights from basic calculus.

ECAI Conference 2016 Conference Paper

Complexity and Tractability Islands for Combinatorial Auctions on Discrete Intervals with Gaps

• Janosch Döcker
• Britta Dorn
• Ulle Endriss
• Dominikus Krüger

Combinatorial auctions are mechanisms for allocating bundles of goods to agents who each have preferences over these goods. Finding an economically efficient allocation, the so-called winner determination problem, is computationally intractable in the general case, which is why it is important to identify special cases that are tractable but also sufficiently expressive for applications. We introduce a family of auction problems in which the goods on auction can be rearranged into a sequence, and each bid submitted concerns a bundle of goods corresponding to an interval on this sequence, possibly with multiple gaps of bounded length. We investigate the computational complexity of the winner determination problem for such auctions and explore the frontier between tractability and intractability in detail, identifying tractable, intractable, and fixed-parameter tractable cases.

MFCS Conference 2009 Conference Paper

Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules

• Nadja Betzler
• Britta Dorn

Abstract To make a joint decision, agents (or voters) are often required to provide their preferences as linear orders. To determine a winner, the given linear orders can be aggregated according to a voting protocol. However, in realistic settings, the voters may often only provide partial orders. This directly leads to the Possible Winner problem that asks, given a set of partial votes, if a distinguished candidate can still become a winner. In this work, we consider the computational complexity of Possible Winner for the broad class of voting protocols defined by scoring rules. A scoring rule provides a score value for every position which a candidate can have in a linear order. Prominent examples include plurality, k -approval, and Borda. Generalizing previous NP-hardness results for some special cases and providing new many-one reductions, we settle the computational complexity for all but one scoring rule. More precisely, for an unbounded number of candidates and unweighted voters, we show that Possible Winner is NP-complete for all pure scoring rules except plurality, veto, and the scoring rule defined by the scoring vector (2, 1, .. ., 1, 0), while it is solvable in polynomial time for plurality and veto.