26 Result(s)
within
Felix Brandt
Computer Science
English
-
Chapter and Conference Paper
TetraPackNet: Four-Corner-Based Object Detection in Logistics Use-Cases
While common image object detection tasks focus on bounding boxes or segmentation masks as object representations, we consider the problem of finding objects based on four arbitrary vertices. We propose a nove...
-
Chapter and Conference Paper
On the Convergence of Swap Dynamics to Pareto-Optimal Matchings
We study whether Pareto-optimal stable matchings can be reached via pairwise swaps in one-to-one matching markets with initial assignments. We consider housing markets, marriage markets, and roommate markets ...
-
Chapter
Computational Social Choice: The First Ten Years and Beyond
Computational social choice is a research area at the intersection of computer science, mathematics, and economics that is concerned with aggregation of preferences of multiple agents. Typical applications inc...
-
Article
The Complexity of Computing Minimal Unidirectional Covering Sets
A common thread in the social sciences is to identify sets of alternatives that satisfy certain notions of stability according to some binary dominance relation. Examples can be found in areas as diverse as vo...
-
Article
On the Rate of Convergence of Fictitious Play
Fictitious play is a simple learning algorithm for strategic games that proceeds in rounds. In each round, the players play a best response to a mixed strategy that is given by the empirical frequencies of act...
-
Chapter and Conference Paper
On Popular Random Assignments
One of the most fundamental and ubiquitous problems in microeconomics and operations research is how to assign objects to agents based on their individual preferences. An assignment is called popular if there ...
-
Chapter and Conference Paper
The Computational Complexity of Random Serial Dictatorship
In social choice settings with linear preferences, random dictatorship is known to be the only social decision scheme satisfying strategyproofness and ex post efficiency. When also allowing indifferences, random ...
-
Article
The Computational Complexity of Weak Saddles
We study the computational aspects of weak saddles, an ordinal set-valued solution concept proposed by Shapley. F. Brandt et al. recently gave a polynomial-time algorithm for computing weak saddles in a subcla...
-
Article
On the Complexity of Iterated Weak Dominance in Constant-Sum Games
In game theory, an action is said to be weakly dominated if there exists another action of the same player that, with respect to what the other players do, is never worse and sometimes strictly better. We inve...
-
Chapter and Conference Paper
From Arrow’s Impossibility to Schwartz’s Tournament Equilibrium Set
Perhaps the most influential result in social choice theory is Arrow’s impossibility theorem, which states that a seemingly modest set of desiderata cannot be satisfied when aggregating preferences [1]. While ...
-
Chapter and Conference Paper
Pareto Optimality in Coalition Formation
A minimal requirement on allocative efficiency in the social sciences is Pareto optimality. In this paper, we identify a far-reaching structural connection between Pareto optimal and perfect partitions that ha...
-
Chapter and Conference Paper
The Complexity of Computing Minimal Unidirectional Covering Sets
Given a binary dominance relation on a set of alternatives, a common thread in the social sciences is to identify subsets of alternatives that satisfy certain notions of stability. Examples can be found in are...
-
Chapter and Conference Paper
On the Rate of Convergence of Fictitious Play
Fictitious play is a simple learning algorithm for strategic games that proceeds in rounds. In each round, the players play a best response to a mixed strategy that is given by the empirical frequencies of act...
-
Chapter and Conference Paper
Tournament Solutions and Their Applications to Multiagent Decision Making
Given a finite set of alternatives and choices between all pairs of alternatives, how to choose from the entire set in a way that is faithful to the pairwise comparisons? This simple, yet captivating, problem ...
-
Chapter and Conference Paper
The Computational Complexity of Weak Saddles
We continue the recently initiated study of the computational aspects of weak saddles, an ordinal set-valued solution concept proposed by Shapley. Brandt et al. gave a polynomial-time algorithm for computing w...
-
Chapter and Conference Paper
On the Complexity of Iterated Weak Dominance in Constant-Sum Games
In game theory, a player’s action is said to be weakly dominated if there exists another action that, with respect to what the other players do, is never worse and sometimes strictly better. We investigate the...
-
Chapter and Conference Paper
On the Hardness and Existence of Quasi-Strict Equilibria
This paper investigates the computational properties of quasi-strict equilibrium, an attractive equilibrium refinement proposed by Harsanyi, which was recently shown to always exist in bimatrix games. We prove...
-
Chapter and Conference Paper
Equilibria of Graphical Games with Symmetries
We study graphical games where the payoff function of each player satisfies one of four types of symmetry in the actions of his neighbors. We establish that deciding the existence of a pure Nash equilibrium is...
-
Chapter and Conference Paper
Symmetries and the Complexity of Pure Nash Equilibrium
Strategic games may exhibit symmetries in a variety of ways. A common aspect, enabling the compact representation of games even when the number of players is unbounded, is that players cannot (or need not) dis...
-
Chapter and Conference Paper
PageRank as a Weak Tournament Solution
We observe that ranking systems—a theoretical framework for web page ranking and collaborative filtering introduced by Altman and Tennenholtz—and tournament solutions—a well-studied area of social choice theor...
