BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Ulrich Pferschy

Ulrich Pferschy appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computer Science and Game TheoryDiscrete MathematicsMultiagent Systems

Catalog footprint

What is connected

4works
3topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

4 published item(s)

preprint2022arXiv

Allocation of Indivisible Items with Individual Preference Graphs

This paper studies the allocation of indivisible items to agents, when each agent's preferences are expressed by means of a directed acyclic graph. The vertices of each preference graph represent the subset of items approved of by the respective agent. An arc $(a,b)$ in such a graph means that the respective agent prefers item $a$ over item $b$. We introduce a new measure of dissatisfaction of an agent by counting the number of non-assigned items which are approved of by the agent and for which no more preferred item is allocated to the agent. Considering two problem variants, we seek an allocation of the items to the agents in a way that minimizes (i) the total dissatisfaction over all agents or (ii) the maximum dissatisfaction among the agents. For both optimization problems we study the status of computational complexity and obtain NP-hardness results as well as polynomial algorithms with respect to natural underlying graph structures, such as stars, trees, paths, and matchings. We also analyze the parameterized complexity of the two problems with respect to various parameters related to the number of agents, the dissatisfaction threshold, the vertex degrees of the preference graphs, and the treewidth.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the shortest path game: extended version

In this work we address a game theoretic variant of the shortest path problem, in which two decision makers (players) move together along the edges of a graph from a given starting vertex to a given destination. The two players take turns in deciding in each vertex which edge to traverse next. The decider in each vertex also has to pay the cost of the chosen edge. We want to determine the path where each player minimizes its costs taking into account that also the other player acts in a selfish and rational way. Such a solution is a subgame perfect equilibrium and can be determined by backward induction in the game tree of the associated finite game in extensive form. We show that the decision problem associated with such a path is PSPACE-complete even for bipartite graphs both for the directed and the undirected version. The latter result is a surprising deviation from the complexity status of the closely related game Geography. On the other hand, we can give polynomial time algorithms for directed acyclic graphs and for cactus graphs even in the undirected case. The latter is based on a decomposition of the graph into components and their resolution by a number of fairly involved dynamic programming arrays. Finally, we give some arguments about closing the gap of the complexity status for graphs of bounded treewidth.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Price of Fairness for Allocating a Bounded Resource

In this paper we study the problem of allocating a scarce resource among several players (or agents). A central decision maker wants to maximize the total utility of all agents. However, such a solution may be unfair for one or more agents in the sense that it can be achieved through a very unbalanced allocation of the resource. On the other hand fair/balanced allocations may be far from being optimal from a central point of view. So, in this paper we are interested in assessing the quality of fair solutions, i.e. in measuring the system efficiency loss under a fair allocation compared to the one that maximizes the sum of agents utilities. This indicator is usually called the Price of Fairness and we study it under three different definitions of fairness, namely maximin, Kalai-Smorodinski and proportional fairness. Our results are of two different types. We first formalize a number of properties holding for any general multi-agent problem without any special assumption on the agents utility sets. Then we introduce an allocation problem, where each agent can consume the resource in given discrete quantities (items), such that the maximization of the total utility is given by a Subset Sum Problem. For the resulting Fair Subset Sum Problem, in the case of two agents, we provide upper and lower bounds on the Price of Fairness as functions of an upper bound on the items size.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The Shortest Connection Game

We introduce Shortest Connection Game, a two-player game played on a directed graph with edge costs. Given two designated vertices in which they start, the players take turns in choosing edges emanating from the vertex they are currently located at. In this way, each of the players forms a path that origins from its respective starting vertex. The game ends as soon as the two paths meet, i.e., a connection between the players is established. Each player has to carry the cost of its chosen edges and thus aims at minimizing its own total cost. In this work we analyze the computational complexity of Shortest Connection Game. On the negative side, the game turns out to be computationally hard even on restricted graph classes such as bipartite, acyclic and cactus graphs. On the positive side, we can give a polynomial time algorithm for cactus graphs when the game is restricted to simple paths.

0 citations0 reviewsNo code linkedOpen access