# Publications

**2017** (5)

Peter Kling, Alexander Mäcker, Sören Riechers, Alexander Skopalik:

In Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). ACM

[Show Abstract]

**Sharing is Caring: Multiprocessor Scheduling with a Sharable Resource**In Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). ACM

**(2017)**(to appear)[Show Abstract]

We consider a scheduling problem on $m$ identical processors sharing an arbitrarily divisible resource. In addition to assigning jobs to processors, the scheduler must distribute the resource among the processors (e.g., for three processors in shares of 20\%, 15\%, and 65\%) and adjust this distribution over time. Each job $j$ comes with a size $p_j \in \mathbbR$ and a resource requirement $r_j > 0$. Jobs do not benefit when receiving a share larger than $r_j$ of the resource. But providing them with a fraction of the resource requirement causes a linear decrease in the processing efficiency. We seek a (non-preemptive) job and resource assignment minimizing the makespan.

Our main result is an efficient approximation algorithm which achieves an approximation ratio of $2 + 1/(m-2)$. It can be improved to an (asymptotic) ratio of $1 + 1/(m-1)$ if all jobs have unit size. Our algorithms also imply new results for a well-known bin packing problem with splittable items and a restricted number of allowed item parts per bin.

Based upon the above solution, we also derive an approximation algorithm with similar guarantees for a setting in which we introduce so-called tasks each containing several jobs and where we are interested in the average completion time of tasks (a task is completed when all its jobs are completed).

[Show BibTeX] Our main result is an efficient approximation algorithm which achieves an approximation ratio of $2 + 1/(m-2)$. It can be improved to an (asymptotic) ratio of $1 + 1/(m-1)$ if all jobs have unit size. Our algorithms also imply new results for a well-known bin packing problem with splittable items and a restricted number of allowed item parts per bin.

Based upon the above solution, we also derive an approximation algorithm with similar guarantees for a setting in which we introduce so-called tasks each containing several jobs and where we are interested in the average completion time of tasks (a task is completed when all its jobs are completed).

@inproceedings{KMRS17,

author = {Peter Kling AND Alexander M{\"a}cker AND S{\"o}ren Riechers AND Alexander Skopalik},

title = {Sharing is Caring: Multiprocessor Scheduling with a Sharable Resource},

booktitle = {Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},

year = {2017},

publisher = {ACM},

month = {July},

note = {to appear},

abstract = {We consider a scheduling problem on $m$ identical processors sharing an arbitrarily divisible resource. In addition to assigning jobs to processors, the scheduler must distribute the resource among the processors (e.g., for three processors in shares of 20\%, 15\%, and 65\%) and adjust this distribution over time. Each job $j$ comes with a size $p_j \in \mathbb{R}$ and a resource requirement $r_j > 0$. Jobs do not benefit when receiving a share larger than $r_j$ of the resource. But providing them with a fraction of the resource requirement causes a linear decrease in the processing efficiency. We seek a (non-preemptive) job and resource assignment minimizing the makespan.Our main result is an efficient approximation algorithm which achieves an approximation ratio of $2 + 1/(m-2)$. It can be improved to an (asymptotic) ratio of $1 + 1/(m-1)$ if all jobs have unit size. Our algorithms also imply new results for a well-known bin packing problem with splittable items and a restricted number of allowed item parts per bin.Based upon the above solution, we also derive an approximation algorithm with similar guarantees for a setting in which we introduce so-called tasks each containing several jobs and where we are interested in the average completion time of tasks (a task is completed when all its jobs are completed).}

}

author = {Peter Kling AND Alexander M{\"a}cker AND S{\"o}ren Riechers AND Alexander Skopalik},

title = {Sharing is Caring: Multiprocessor Scheduling with a Sharable Resource},

booktitle = {Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},

year = {2017},

publisher = {ACM},

month = {July},

note = {to appear},

abstract = {We consider a scheduling problem on $m$ identical processors sharing an arbitrarily divisible resource. In addition to assigning jobs to processors, the scheduler must distribute the resource among the processors (e.g., for three processors in shares of 20\%, 15\%, and 65\%) and adjust this distribution over time. Each job $j$ comes with a size $p_j \in \mathbb{R}$ and a resource requirement $r_j > 0$. Jobs do not benefit when receiving a share larger than $r_j$ of the resource. But providing them with a fraction of the resource requirement causes a linear decrease in the processing efficiency. We seek a (non-preemptive) job and resource assignment minimizing the makespan.Our main result is an efficient approximation algorithm which achieves an approximation ratio of $2 + 1/(m-2)$. It can be improved to an (asymptotic) ratio of $1 + 1/(m-1)$ if all jobs have unit size. Our algorithms also imply new results for a well-known bin packing problem with splittable items and a restricted number of allowed item parts per bin.Based upon the above solution, we also derive an approximation algorithm with similar guarantees for a setting in which we introduce so-called tasks each containing several jobs and where we are interested in the average completion time of tasks (a task is completed when all its jobs are completed).}

}

Matthias Feldotto, Maximilian Drees, Sören Riechers, Alexander Skopalik:

In Proceedings of the 23rd International Computing and Combinatorics Conference (COCOON). Springer, LNCS

[Show Abstract]

**Pure Nash Equilibria in Restricted Budget Games**In Proceedings of the 23rd International Computing and Combinatorics Conference (COCOON). Springer, LNCS

**(2017)**(to appear)[Show Abstract]

In budget games, players compete over resources with finite budgets. For every resource, a player has a specific demand and as a strategy, he chooses a subset of resources. If the total demand on a resource does not exceed its budget, the utility of each player who chose that resource equals his demand. Otherwise, the budget is shared proportionally. In the general case, pure Nash equilibria (NE) do not exist for such games. In this paper, we consider the natural classes of singleton and matroid budget games with additional constraints and show that for each, pure NE can be guaranteed. In addition, we introduce a lexicographical potential function to prove that every matroid budget game has an approximate pure NE which depends on the largest ratio between the different demands of each individual player.

[Show BibTeX] @inproceedings{DFRS17,

author = {Matthias Feldotto AND Maximilian Drees AND S{\"o}ren Riechers AND Alexander Skopalik},

title = {Pure Nash Equilibria in Restricted Budget Games},

booktitle = {Proceedings of the 23rd International Computing and Combinatorics Conference (COCOON)},

year = {2017},

publisher = {Springer},

note = {to appear},

abstract = {In budget games, players compete over resources with finite budgets. For every resource, a player has a specific demand and as a strategy, he chooses a subset of resources. If the total demand on a resource does not exceed its budget, the utility of each player who chose that resource equals his demand. Otherwise, the budget is shared proportionally. In the general case, pure Nash equilibria (NE) do not exist for such games. In this paper, we consider the natural classes of singleton and matroid budget games with additional constraints and show that for each, pure NE can be guaranteed. In addition, we introduce a lexicographical potential function to prove that every matroid budget game has an approximate pure NE which depends on the largest ratio between the different demands of each individual player.},

series = {LNCS}

}

author = {Matthias Feldotto AND Maximilian Drees AND S{\"o}ren Riechers AND Alexander Skopalik},

title = {Pure Nash Equilibria in Restricted Budget Games},

booktitle = {Proceedings of the 23rd International Computing and Combinatorics Conference (COCOON)},

year = {2017},

publisher = {Springer},

note = {to appear},

abstract = {In budget games, players compete over resources with finite budgets. For every resource, a player has a specific demand and as a strategy, he chooses a subset of resources. If the total demand on a resource does not exceed its budget, the utility of each player who chose that resource equals his demand. Otherwise, the budget is shared proportionally. In the general case, pure Nash equilibria (NE) do not exist for such games. In this paper, we consider the natural classes of singleton and matroid budget games with additional constraints and show that for each, pure NE can be guaranteed. In addition, we introduce a lexicographical potential function to prove that every matroid budget game has an approximate pure NE which depends on the largest ratio between the different demands of each individual player.},

series = {LNCS}

}

Angelika Endres, Sonja Brangewitz, Behnud Djawadi, Britta Hoyer:

Techreport UPB.

[Show Abstract]

**Network Formation and Disruption - An Experiment: Are efficient networks too complex?**Techreport UPB.

**(2017)**[Show Abstract]

We experimentally study the emergence of networks under a known external threat. To be more specific, we deal with the question if subjects in the role of a strategic Designer are able to form safe and efficient networks while facing a strategic Adversary who is going to attack their networks. This investigation relates theoretical predictions by Dziubinski and Goyal (2013) to actual observed behaviour. Varying the costs for protecting nodes, we designed and tested two treatments with different predictions for the equilibrium network. Furthermore, the influence of the subjects' farsightedness on their decision-making process was elicited and analysed. We find that while subjects are able to build safe networks in both treatments, equilibrium networks are only built in one of the two treatments. In the other treatment, predominantly safe networks are built but they are not efficient. Additionally, we find that farsightedness -as measured in our experiment - has no influence on whether subjects are able to build safe or efficient networks.

[Show BibTeX] @techreport{BDEH2017,

author = {Angelika Endres AND Sonja Brangewitz AND Behnud Djawadi AND Britta Hoyer},

title = {Network Formation and Disruption - An Experiment: Are efficient networks too complex?},

year = {2017},

type = {Techreport UPB},

abstract = {We experimentally study the emergence of networks under a known external threat. To be more specific, we deal with the question if subjects in the role of a strategic Designer are able to form safe and efficient networks while facing a strategic Adversary who is going to attack their networks. This investigation relates theoretical predictions by Dziubinski and Goyal (2013) to actual observed behaviour. Varying the costs for protecting nodes, we designed and tested two treatments with different predictions for the equilibrium network. Furthermore, the influence of the subjects' farsightedness on their decision-making process was elicited and analysed. We find that while subjects are able to build safe networks in both treatments, equilibrium networks are only built in one of the two treatments. In the other treatment, predominantly safe networks are built but they are not efficient. Additionally, we find that farsightedness --as measured in our experiment - has no influence on whether subjects are able to build safe or efficient networks.}

}

author = {Angelika Endres AND Sonja Brangewitz AND Behnud Djawadi AND Britta Hoyer},

title = {Network Formation and Disruption - An Experiment: Are efficient networks too complex?},

year = {2017},

type = {Techreport UPB},

abstract = {We experimentally study the emergence of networks under a known external threat. To be more specific, we deal with the question if subjects in the role of a strategic Designer are able to form safe and efficient networks while facing a strategic Adversary who is going to attack their networks. This investigation relates theoretical predictions by Dziubinski and Goyal (2013) to actual observed behaviour. Varying the costs for protecting nodes, we designed and tested two treatments with different predictions for the equilibrium network. Furthermore, the influence of the subjects' farsightedness on their decision-making process was elicited and analysed. We find that while subjects are able to build safe networks in both treatments, equilibrium networks are only built in one of the two treatments. In the other treatment, predominantly safe networks are built but they are not efficient. Additionally, we find that farsightedness --as measured in our experiment - has no influence on whether subjects are able to build safe or efficient networks.}

}

Laura Niggmeyer:

Bachelor thesis, University of Paderborn

[Show BibTeX]

**Kartellabsprachen und vertikale Preisbindungen - Eine wettbewerbspolitische Analyse am Bespiel der Lebensmittelindustrie in Deutschland**Bachelor thesis, University of Paderborn

**(2017)**[Show BibTeX]

@misc{LN2017,

author = {Laura Niggmeyer},

title = {Kartellabsprachen und vertikale Preisbindungen - Eine wettbewerbspolitische Analyse am Bespiel der Lebensmittelindustrie in Deutschland},

year = {2017}

}

author = {Laura Niggmeyer},

title = {Kartellabsprachen und vertikale Preisbindungen - Eine wettbewerbspolitische Analyse am Bespiel der Lebensmittelindustrie in Deutschland},

year = {2017}

}

Matthias Feldotto, Lennart Leder, Alexander Skopalik:

In Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC). Springer, LNCS, vol. 10236, pp. 222-233

[Show Abstract]

**Congestion Games with Complementarities**In Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC). Springer, LNCS, vol. 10236, pp. 222-233

**(2017)**[Show Abstract]

We study a model of selfish resource allocation that seeks to incorporate dependencies among resources as they exist in in modern networked environments. Our model is inspired by utility functions with constant elasticity of substitution (CES) which is a well-studied model in economics. We consider congestion games with different aggregation functions. In particular, we study $L_p$ norms and analyze the existence and complexity of (approximate) pure Nash equilibria. Additionally, we give an almost tight characterization based on monotonicity properties to describe the set of aggregation functions that guarantee the existence of pure Nash equilibria.

[Show BibTeX] @inproceedings{FLS17,

author = {Matthias Feldotto AND Lennart Leder AND Alexander Skopalik},

title = {Congestion Games with Complementarities},

booktitle = {Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC)},

year = {2017},

pages = {222--233},

publisher = {Springer},

abstract = {We study a model of selfish resource allocation that seeks to incorporate dependencies among resources as they exist in in modern networked environments. Our model is inspired by utility functions with constant elasticity of substitution (CES) which is a well-studied model in economics. We consider congestion games with different aggregation functions. In particular, we study $L_p$ norms and analyze the existence and complexity of (approximate) pure Nash equilibria. Additionally, we give an almost tight characterization based on monotonicity properties to describe the set of aggregation functions that guarantee the existence of pure Nash equilibria.},

series = {LNCS}

}

[DOI]
author = {Matthias Feldotto AND Lennart Leder AND Alexander Skopalik},

title = {Congestion Games with Complementarities},

booktitle = {Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC)},

year = {2017},

pages = {222--233},

publisher = {Springer},

abstract = {We study a model of selfish resource allocation that seeks to incorporate dependencies among resources as they exist in in modern networked environments. Our model is inspired by utility functions with constant elasticity of substitution (CES) which is a well-studied model in economics. We consider congestion games with different aggregation functions. In particular, we study $L_p$ norms and analyze the existence and complexity of (approximate) pure Nash equilibria. Additionally, we give an almost tight characterization based on monotonicity properties to describe the set of aggregation functions that guarantee the existence of pure Nash equilibria.},

series = {LNCS}

}

**2016** (6)

Burkhard Monien, Marios Mavronicolas:

In

[Show Abstract]

**The complexity of equilibria for risk-modeling valuations**In

*Theoretical Computer Science*, vol. 634, pp. 67-96. Elsevier**(2016)**[Show Abstract]

Following the direction pioneered by Fiat and Papadimitriou in their 2010 paper [12], we study the complexity of deciding the existence of mixed equilibria for minimization games where players use valuations other than expectation to evaluate their costs. We consider risk-averse players seeking to minimize the sum V=E+R of expectationE and a risk valuationR of their costs; R is non-negative and vanishes exactly when the cost incurred to a player is constant over all choices of strategies by the other players. In a V-equilibrium, no player could unilaterally reduce her cost.

Say that V has the Weak-Equilibrium-for-Expectation property if all strategies supported in a player's best-response mixed strategy incur the same conditional expectation of her cost. We introduce E-strict concavity and observe that every E-strictly concave valuation has the Weak-Equilibrium-for-Expectation property. We focus on a broad class of valuations shown to have the Weak-Equilibrium-for-Expectation property, which we exploit to prove two main complexity results, the first of their kind, for the two simplest cases of the problem:

• Two strategies: Deciding the existence of a V-equilibrium is strongly NP-hard for the restricted class of player-specific scheduling games on two ordered links [22], when choosing R as (1)Var (variance), or (2)SD (standard deviation), or (3) a concave linear sum of even moments of small order.

• Two players: Deciding the existence of a V-equilibrium is strongly NP-hard when choosing R as (1)γ⋅Var, or (2)γ⋅SD, where γ>0 is the risk-coefficient, or choosing V as (3) a convex combination of E+γ⋅Var and the concave ν-valuationν−1(E(ν(⋅))), where ν(x)=xr, with r≥2. This is a concrete consequence of a general strong NP-hardness result that only needs the Weak-Equilibrium-for-Expectation property and a few additional properties for V; its proof involves a reduction with a single parameter, which can be chosen efficiently so that each valuation satisfies the additional properties.

[Show BibTeX] Say that V has the Weak-Equilibrium-for-Expectation property if all strategies supported in a player's best-response mixed strategy incur the same conditional expectation of her cost. We introduce E-strict concavity and observe that every E-strictly concave valuation has the Weak-Equilibrium-for-Expectation property. We focus on a broad class of valuations shown to have the Weak-Equilibrium-for-Expectation property, which we exploit to prove two main complexity results, the first of their kind, for the two simplest cases of the problem:

• Two strategies: Deciding the existence of a V-equilibrium is strongly NP-hard for the restricted class of player-specific scheduling games on two ordered links [22], when choosing R as (1)Var (variance), or (2)SD (standard deviation), or (3) a concave linear sum of even moments of small order.

• Two players: Deciding the existence of a V-equilibrium is strongly NP-hard when choosing R as (1)γ⋅Var, or (2)γ⋅SD, where γ>0 is the risk-coefficient, or choosing V as (3) a convex combination of E+γ⋅Var and the concave ν-valuationν−1(E(ν(⋅))), where ν(x)=xr, with r≥2. This is a concrete consequence of a general strong NP-hardness result that only needs the Weak-Equilibrium-for-Expectation property and a few additional properties for V; its proof involves a reduction with a single parameter, which can be chosen efficiently so that each valuation satisfies the additional properties.

@article{MM2016,

author = {Burkhard Monien AND Marios Mavronicolas},

title = {The complexity of equilibria for risk-modeling valuations},

journal = {Theoretical Computer Science},

year = {2016},

volume = {634},

pages = {67-96},

abstract = {Following the direction pioneered by Fiat and Papadimitriou in their 2010 paper [12], we study the complexity of deciding the existence of mixed equilibria for minimization games where players use valuations other than expectation to evaluate their costs. We consider risk-averse players seeking to minimize the sum V=E+R of expectationE and a risk valuationR of their costs; R is non-negative and vanishes exactly when the cost incurred to a player is constant over all choices of strategies by the other players. In a V-equilibrium, no player could unilaterally reduce her cost.Say that V has the Weak-Equilibrium-for-Expectation property if all strategies supported in a player's best-response mixed strategy incur the same conditional expectation of her cost. We introduce E-strict concavity and observe that every E-strictly concave valuation has the Weak-Equilibrium-for-Expectation property. We focus on a broad class of valuations shown to have the Weak-Equilibrium-for-Expectation property, which we exploit to prove two main complexity results, the first of their kind, for the two simplest cases of the problem:• Two strategies: Deciding the existence of a V-equilibrium is strongly NP-hard for the restricted class of player-specific scheduling games on two ordered links [22], when choosing R as (1)Var (variance), or (2)SD (standard deviation), or (3) a concave linear sum of even moments of small order.• Two players: Deciding the existence of a V-equilibrium is strongly NP-hard when choosing R as (1)γ⋅Var, or (2)γ⋅SD, where γ>0 is the risk-coefficient, or choosing V as (3) a convex combination of E+γ⋅Var and the concave ν-valuationν−1(E(ν(⋅))), where ν(x)=xr, with r≥2. This is a concrete consequence of a general strong NP-hardness result that only needs the Weak-Equilibrium-for-Expectation property and a few additional properties for V; its proof involves a reduction with a single parameter, which can be chosen efficiently so that each valuation satisfies the additional properties.}

}

[DOI]
author = {Burkhard Monien AND Marios Mavronicolas},

title = {The complexity of equilibria for risk-modeling valuations},

journal = {Theoretical Computer Science},

year = {2016},

volume = {634},

pages = {67-96},

abstract = {Following the direction pioneered by Fiat and Papadimitriou in their 2010 paper [12], we study the complexity of deciding the existence of mixed equilibria for minimization games where players use valuations other than expectation to evaluate their costs. We consider risk-averse players seeking to minimize the sum V=E+R of expectationE and a risk valuationR of their costs; R is non-negative and vanishes exactly when the cost incurred to a player is constant over all choices of strategies by the other players. In a V-equilibrium, no player could unilaterally reduce her cost.Say that V has the Weak-Equilibrium-for-Expectation property if all strategies supported in a player's best-response mixed strategy incur the same conditional expectation of her cost. We introduce E-strict concavity and observe that every E-strictly concave valuation has the Weak-Equilibrium-for-Expectation property. We focus on a broad class of valuations shown to have the Weak-Equilibrium-for-Expectation property, which we exploit to prove two main complexity results, the first of their kind, for the two simplest cases of the problem:• Two strategies: Deciding the existence of a V-equilibrium is strongly NP-hard for the restricted class of player-specific scheduling games on two ordered links [22], when choosing R as (1)Var (variance), or (2)SD (standard deviation), or (3) a concave linear sum of even moments of small order.• Two players: Deciding the existence of a V-equilibrium is strongly NP-hard when choosing R as (1)γ⋅Var, or (2)γ⋅SD, where γ>0 is the risk-coefficient, or choosing V as (3) a convex combination of E+γ⋅Var and the concave ν-valuationν−1(E(ν(⋅))), where ν(x)=xr, with r≥2. This is a concrete consequence of a general strong NP-hardness result that only needs the Weak-Equilibrium-for-Expectation property and a few additional properties for V; its proof involves a reduction with a single parameter, which can be chosen efficiently so that each valuation satisfies the additional properties.}

}

Sonja Brangewitz, Sarah Brockhoff:

In

[Show Abstract]

**Sustainability of Coalitional Equilibria within Repeated Tax Competition**In

*European Journal of Political Economy*. Elsevier**(2016)**(in press)[Show Abstract]

This paper analyzes the sustainability of capital tax harmonization agreements in a stylized model where countries have formed coalitions to agree on a common tax rate in order to avoid the inefficient, fully non-cooperative Nash equilibrium. In particular, for a given coalition structure we study to what extent the sustainability of tax agreements is affected by the coalitions that have formed. In our setup, countries are symmetric, but coalitions can be of arbitrary size. We analyze sustainability by means of a repeated game setting employing simple trigger strategies and we allow a sub-coalition to deviate from the coalitional equilibrium. For a given form of punishment we rank the sustainability of different coalition structures. We show that sub-coalitions consisting of singleton regions have the largest incentives to deviate and that the sustainability of cooperation depends on the degree of cooperative behavior ex-ante. Bilateral agreements between pairs of regions turn out to be the form of cooperation that is the easiest to sustain.

[Show BibTeX] @article{SBSB2016,

author = {Sonja Brangewitz AND Sarah Brockhoff},

title = {Sustainability of Coalitional Equilibria within Repeated Tax Competition},

journal = {European Journal of Political Economy},

year = {2016},

note = {in press},

abstract = {This paper analyzes the sustainability of capital tax harmonization agreements in a stylized model where countries have formed coalitions to agree on a common tax rate in order to avoid the inefficient, fully non-cooperative Nash equilibrium. In particular, for a given coalition structure we study to what extent the sustainability of tax agreements is affected by the coalitions that have formed. In our setup, countries are symmetric, but coalitions can be of arbitrary size. We analyze sustainability by means of a repeated game setting employing simple trigger strategies and we allow a sub-coalition to deviate from the coalitional equilibrium. For a given form of punishment we rank the sustainability of different coalition structures. We show that sub-coalitions consisting of singleton regions have the largest incentives to deviate and that the sustainability of cooperation depends on the degree of cooperative behavior ex-ante. Bilateral agreements between pairs of regions turn out to be the form of cooperation that is the easiest to sustain.}

}

[DOI]
author = {Sonja Brangewitz AND Sarah Brockhoff},

title = {Sustainability of Coalitional Equilibria within Repeated Tax Competition},

journal = {European Journal of Political Economy},

year = {2016},

note = {in press},

abstract = {This paper analyzes the sustainability of capital tax harmonization agreements in a stylized model where countries have formed coalitions to agree on a common tax rate in order to avoid the inefficient, fully non-cooperative Nash equilibrium. In particular, for a given coalition structure we study to what extent the sustainability of tax agreements is affected by the coalitions that have formed. In our setup, countries are symmetric, but coalitions can be of arbitrary size. We analyze sustainability by means of a repeated game setting employing simple trigger strategies and we allow a sub-coalition to deviate from the coalitional equilibrium. For a given form of punishment we rank the sustainability of different coalition structures. We show that sub-coalitions consisting of singleton regions have the largest incentives to deviate and that the sustainability of cooperation depends on the degree of cooperative behavior ex-ante. Bilateral agreements between pairs of regions turn out to be the form of cooperation that is the easiest to sustain.}

}

Tobias Harks, Martin Höfer, Kevin Schewior, Alexander Skopalik:

In

[Show Abstract]

**Routing Games With Progressive Filling**In

*IEEE/ACM Transactions on Networking*, vol. 24, no. 4, pp. 2553 - 2562.**(2016)**[Show Abstract]

Abstract—Max-min fairness (MMF) is a widely known approach

to a fair allocation of bandwidth to each of the users

in a network. This allocation can be computed by uniformly

raising the bandwidths of all users without violating capacity

constraints. We consider an extension of these allocations by

raising the bandwidth with arbitrary and not necessarily uniform

time-depending velocities (allocation rates). These allocations

are used in a game-theoretic context for routing choices, which

we formalize in progressive filling games (PFGs). We present a

variety of results for equilibria in PFGs. We show that these games

possess pure Nash and strong equilibria. While computation in

general is NP-hard, there are polynomial-time algorithms for

prominent classes of Max-Min-Fair Games (MMFG), including

the case when all users have the same source-destination pair.

We characterize prices of anarchy and stability for pure Nash

and strong equilibria in PFGs and MMFGs when players have

different or the same source-destination pairs. In addition, we

show that when a designer can adjust allocation rates, it is possible

to design games with optimal strong equilibria. Some initial results

on polynomial-time algorithms in this direction are also derived.

[Show BibTeX] to a fair allocation of bandwidth to each of the users

in a network. This allocation can be computed by uniformly

raising the bandwidths of all users without violating capacity

constraints. We consider an extension of these allocations by

raising the bandwidth with arbitrary and not necessarily uniform

time-depending velocities (allocation rates). These allocations

are used in a game-theoretic context for routing choices, which

we formalize in progressive filling games (PFGs). We present a

variety of results for equilibria in PFGs. We show that these games

possess pure Nash and strong equilibria. While computation in

general is NP-hard, there are polynomial-time algorithms for

prominent classes of Max-Min-Fair Games (MMFG), including

the case when all users have the same source-destination pair.

We characterize prices of anarchy and stability for pure Nash

and strong equilibria in PFGs and MMFGs when players have

different or the same source-destination pairs. In addition, we

show that when a designer can adjust allocation rates, it is possible

to design games with optimal strong equilibria. Some initial results

on polynomial-time algorithms in this direction are also derived.

@article{HHSS16,

author = {Tobias Harks AND Martin H{\"o}fer AND Kevin Schewior AND Alexander Skopalik},

title = {Routing Games With Progressive Filling},

journal = {IEEE/ACM Transactions on Networking},

year = {2016},

volume = {24},

number = {4},

pages = {2553 - 2562},

abstract = {Abstract—Max-min fairness (MMF) is a widely known approachto a fair allocation of bandwidth to each of the usersin a network. This allocation can be computed by uniformlyraising the bandwidths of all users without violating capacityconstraints. We consider an extension of these allocations byraising the bandwidth with arbitrary and not necessarily uniformtime-depending velocities (allocation rates). These allocationsare used in a game-theoretic context for routing choices, whichwe formalize in progressive filling games (PFGs). We present avariety of results for equilibria in PFGs. We show that these gamespossess pure Nash and strong equilibria. While computation ingeneral is NP-hard, there are polynomial-time algorithms forprominent classes of Max-Min-Fair Games (MMFG), includingthe case when all users have the same source-destination pair.We characterize prices of anarchy and stability for pure Nashand strong equilibria in PFGs and MMFGs when players havedifferent or the same source-destination pairs. In addition, weshow that when a designer can adjust allocation rates, it is possibleto design games with optimal strong equilibria. Some initial resultson polynomial-time algorithms in this direction are also derived.}

}

[DOI]
author = {Tobias Harks AND Martin H{\"o}fer AND Kevin Schewior AND Alexander Skopalik},

title = {Routing Games With Progressive Filling},

journal = {IEEE/ACM Transactions on Networking},

year = {2016},

volume = {24},

number = {4},

pages = {2553 - 2562},

abstract = {Abstract—Max-min fairness (MMF) is a widely known approachto a fair allocation of bandwidth to each of the usersin a network. This allocation can be computed by uniformlyraising the bandwidths of all users without violating capacityconstraints. We consider an extension of these allocations byraising the bandwidth with arbitrary and not necessarily uniformtime-depending velocities (allocation rates). These allocationsare used in a game-theoretic context for routing choices, whichwe formalize in progressive filling games (PFGs). We present avariety of results for equilibria in PFGs. We show that these gamespossess pure Nash and strong equilibria. While computation ingeneral is NP-hard, there are polynomial-time algorithms forprominent classes of Max-Min-Fair Games (MMFG), includingthe case when all users have the same source-destination pair.We characterize prices of anarchy and stability for pure Nashand strong equilibria in PFGs and MMFGs when players havedifferent or the same source-destination pairs. In addition, weshow that when a designer can adjust allocation rates, it is possibleto design games with optimal strong equilibria. Some initial resultson polynomial-time algorithms in this direction are also derived.}

}

Sonja Brangewitz, Simon Hoof:

In Marco Aiello, Einar Broch Johnsen, Schahram Dustdar, and Ilche Georgievski (eds.): Service-Oriented and Cloud Computing: 5th IFIP WG 2.14 European Conference, ESOCC 2016, Vienna, Austria, September 5-7, 2016, Proceedings. Springer International Publishing (Cham), pp. 201-215

[Show Abstract]

**Economic Aspects of Service Composition: Price Negotiations and Quality Investments**In Marco Aiello, Einar Broch Johnsen, Schahram Dustdar, and Ilche Georgievski (eds.): Service-Oriented and Cloud Computing: 5th IFIP WG 2.14 European Conference, ESOCC 2016, Vienna, Austria, September 5-7, 2016, Proceedings. Springer International Publishing (Cham), pp. 201-215

**(2016)**[Show Abstract]

We analyse the economic interaction on the market for composed services. Typically, as providers of composed services, intermediaries interact on the sales side with users and on the procurement side with providers of single services. Thus, in how far a user request can be met often crucially depends on the prices and qualities of the different single services used in the composition. We study an intermediary who purchases two complementary single services and combines them. The prices paid to the service providers are determined by simultaneous multilateral Nash bargaining between the intermediary and the respective service provider. By using a function with constant elasticity of substitution (CES) to determine the quality of the composed service, we allow for complementary as well as substitutable degrees of the providers' service qualities. We investigate quality investments of service providers and the corresponding evolution of the single service quality within a differential game framework.

[Show BibTeX] @inproceedings{SBSH16,

author = {Sonja Brangewitz AND Simon Hoof},

title = {Economic Aspects of Service Composition: Price Negotiations and Quality Investments},

booktitle = {Service-Oriented and Cloud Computing: 5th IFIP WG 2.14 European Conference, ESOCC 2016, Vienna, Austria, September 5-7, 2016, Proceedings},

year = {2016},

editor = {Marco Aiello, Einar Broch Johnsen, Schahram Dustdar, and Ilche Georgievski},

pages = {201-215},

publisher = {Springer International Publishing},

address = {Cham},

abstract = {We analyse the economic interaction on the market for composed services. Typically, as providers of composed services, intermediaries interact on the sales side with users and on the procurement side with providers of single services. Thus, in how far a user request can be met often crucially depends on the prices and qualities of the different single services used in the composition. We study an intermediary who purchases two complementary single services and combines them. The prices paid to the service providers are determined by simultaneous multilateral Nash bargaining between the intermediary and the respective service provider. By using a function with constant elasticity of substitution (CES) to determine the quality of the composed service, we allow for complementary as well as substitutable degrees of the providers' service qualities. We investigate quality investments of service providers and the corresponding evolution of the single service quality within a differential game framework. }

}

[DOI]
author = {Sonja Brangewitz AND Simon Hoof},

title = {Economic Aspects of Service Composition: Price Negotiations and Quality Investments},

booktitle = {Service-Oriented and Cloud Computing: 5th IFIP WG 2.14 European Conference, ESOCC 2016, Vienna, Austria, September 5-7, 2016, Proceedings},

year = {2016},

editor = {Marco Aiello, Einar Broch Johnsen, Schahram Dustdar, and Ilche Georgievski},

pages = {201-215},

publisher = {Springer International Publishing},

address = {Cham},

abstract = {We analyse the economic interaction on the market for composed services. Typically, as providers of composed services, intermediaries interact on the sales side with users and on the procurement side with providers of single services. Thus, in how far a user request can be met often crucially depends on the prices and qualities of the different single services used in the composition. We study an intermediary who purchases two complementary single services and combines them. The prices paid to the service providers are determined by simultaneous multilateral Nash bargaining between the intermediary and the respective service provider. By using a function with constant elasticity of substitution (CES) to determine the quality of the composed service, we allow for complementary as well as substitutable degrees of the providers' service qualities. We investigate quality investments of service providers and the corresponding evolution of the single service quality within a differential game framework. }

}

Matthias Feldotto, Lennart Leder, Alexander Skopalik:

In Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA). Springer, LNCS, vol. 10043, pp. 655-669

[Show Abstract]

**Congestion Games with Mixed Objectives**In Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA). Springer, LNCS, vol. 10043, pp. 655-669

**(2016)**[Show Abstract]

We study a new class of games which generalizes congestion games and its bottleneck variant. We introduce congestion games with mixed objectives to model network scenarios in which players seek to optimize for latency and bandwidths alike. We characterize the existence of pure Nash equilibria (PNE) and the convergence of improvement dynamics. For games that do not possess PNE we give bounds on the approximation ratio of approximate pure Nash equilibria.

[Show BibTeX] @inproceedings{FLS16,

author = {Matthias Feldotto AND Lennart Leder AND Alexander Skopalik},

title = {Congestion Games with Mixed Objectives},

booktitle = {Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)},

year = {2016},

pages = {655--669},

publisher = {Springer},

abstract = {We study a new class of games which generalizes congestion games and its bottleneck variant. We introduce congestion games with mixed objectives to model network scenarios in which players seek to optimize for latency and bandwidths alike. We characterize the existence of pure Nash equilibria (PNE) and the convergence of improvement dynamics. For games that do not possess PNE we give bounds on the approximation ratio of approximate pure Nash equilibria.},

series = {LNCS}

}

[DOI]
author = {Matthias Feldotto AND Lennart Leder AND Alexander Skopalik},

title = {Congestion Games with Mixed Objectives},

booktitle = {Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)},

year = {2016},

pages = {655--669},

publisher = {Springer},

abstract = {We study a new class of games which generalizes congestion games and its bottleneck variant. We introduce congestion games with mixed objectives to model network scenarios in which players seek to optimize for latency and bandwidths alike. We characterize the existence of pure Nash equilibria (PNE) and the convergence of improvement dynamics. For games that do not possess PNE we give bounds on the approximation ratio of approximate pure Nash equilibria.},

series = {LNCS}

}

Sonja Brangewitz, Jochen Manegold:

In

[Show Abstract]

**Competition of Intermediaries in a Differentiated Duopoly**In

*Theoretical Economics Letters*, vol. 6, pp. 1341-1362.**(2016)**[Show Abstract]

On an intermediate goods market with asymmetric production technologies as well as vertical and horizontal product differentiation we analyze the influence of simultaneous competition for resources and customers. The intermediaries face either price or quantity competition on the output market and a monopolistic, strategically acting supplier on the input market. We find that there exist quality and productivity differences such that for quantity competition only one intermediary is willing to procure inputs from the input supplier, while for price competition both intermediaries are willing to purchase inputs. Moreover, the well-known welfare advantage of price competition can in general be no longer confirmed in our model with an endogenous input market and asymmetric intermediaries.

[Show BibTeX] @article{SBJM2016,

author = {Sonja Brangewitz AND Jochen Manegold},

title = {Competition of Intermediaries in a Differentiated Duopoly},

journal = {Theoretical Economics Letters},

year = {2016},

volume = {6},

pages = {1341-1362},

abstract = {On an intermediate goods market with asymmetric production technologies as well as vertical and horizontal product differentiation we analyze the influence of simultaneous competition for resources and customers. The intermediaries face either price or quantity competition on the output market and a monopolistic, strategically acting supplier on the input market. We find that there exist quality and productivity differences such that for quantity competition only one intermediary is willing to procure inputs from the input supplier, while for price competition both intermediaries are willing to purchase inputs. Moreover, the well-known welfare advantage of price competition can in general be no longer confirmed in our model with an endogenous input market and asymmetric intermediaries.}

}

[DOI]
author = {Sonja Brangewitz AND Jochen Manegold},

title = {Competition of Intermediaries in a Differentiated Duopoly},

journal = {Theoretical Economics Letters},

year = {2016},

volume = {6},

pages = {1341-1362},

abstract = {On an intermediate goods market with asymmetric production technologies as well as vertical and horizontal product differentiation we analyze the influence of simultaneous competition for resources and customers. The intermediaries face either price or quantity competition on the output market and a monopolistic, strategically acting supplier on the input market. We find that there exist quality and productivity differences such that for quantity competition only one intermediary is willing to procure inputs from the input supplier, while for price competition both intermediaries are willing to purchase inputs. Moreover, the well-known welfare advantage of price competition can in general be no longer confirmed in our model with an endogenous input market and asymmetric intermediaries.}

}

**2015** (8)

Burkhard Monien, Marios Mavronicolas, Klaus Wagner:

In the ´Festschrift´ Algorithms, Probability, Networks, and Games: Scientific Papers and Essays Dedicated to Paul G. Spirakis on the Occasion of His 60th Birthday. Springer, LNCS, vol. 9295, pp. 49-86

[Show Abstract]

**Weighted Boolean Formula Games**In the ´Festschrift´ Algorithms, Probability, Networks, and Games: Scientific Papers and Essays Dedicated to Paul G. Spirakis on the Occasion of His 60th Birthday. Springer, LNCS, vol. 9295, pp. 49-86

**(2015)**[Show Abstract]

We introduce weighted boolean formula games (WBFG) as a new class of succinct games. Each player has a set of boolean formulas she wants to get satisfied; the formulas involve a ground set of boolean variables each of which is controlled by some player. The payoff of a player is a weighted sum of the values of her formulas. We consider both pure equilibria and their refinement of payoff-dominant equilibria [34], where every player is no worse-off than in any other pure equilibrium. We present both structural and complexity results:

We consider mutual weighted boolean formula games (MWBFG), a subclass of WBFG making a natural mutuality assumption on the formulas of players. We present a very simple exact potential for MWBFG. We establish a polynomial monomorphism from certain classes of weighted congestion games to subclasses of WBFG and MWBFG, respectively, indicating their rich structure.

We present a collection of complexity results about decision (and search) problems for both pure and payoff-dominant equilibria in WBFG. The precise complexities depend crucially on five parameters: (i) the number of players; (ii) the number of variables per player; (iii) the number of formulas per player; (iv) the weights in the payoff functions (whether identical or not), and (v) the syntax of the formulas. These results imply that, unless the polynomial hierarchy collapses, decision (and search) problems for payoff-dominant equilibria are harde than for pure equilibria.

[Show BibTeX] We consider mutual weighted boolean formula games (MWBFG), a subclass of WBFG making a natural mutuality assumption on the formulas of players. We present a very simple exact potential for MWBFG. We establish a polynomial monomorphism from certain classes of weighted congestion games to subclasses of WBFG and MWBFG, respectively, indicating their rich structure.

We present a collection of complexity results about decision (and search) problems for both pure and payoff-dominant equilibria in WBFG. The precise complexities depend crucially on five parameters: (i) the number of players; (ii) the number of variables per player; (iii) the number of formulas per player; (iv) the weights in the payoff functions (whether identical or not), and (v) the syntax of the formulas. These results imply that, unless the polynomial hierarchy collapses, decision (and search) problems for payoff-dominant equilibria are harde than for pure equilibria.

@inproceedings{MM2014,

author = {Burkhard Monien AND Marios Mavronicolas AND Klaus Wagner},

title = {Weighted Boolean Formula Games},

booktitle = {the ´Festschrift´ Algorithms, Probability, Networks, and Games: Scientific Papers and Essays Dedicated to Paul G. Spirakis on the Occasion of His 60th Birthday},

year = {2015},

pages = {49-86},

publisher = {Springer},

abstract = {We introduce weighted boolean formula games (WBFG) as a new class of succinct games. Each player has a set of boolean formulas she wants to get satisfied; the formulas involve a ground set of boolean variables each of which is controlled by some player. The payoff of a player is a weighted sum of the values of her formulas. We consider both pure equilibria and their refinement of payoff-dominant equilibria [34], where every player is no worse-off than in any other pure equilibrium. We present both structural and complexity results:We consider mutual weighted boolean formula games (MWBFG), a subclass of WBFG making a natural mutuality assumption on the formulas of players. We present a very simple exact potential for MWBFG. We establish a polynomial monomorphism from certain classes of weighted congestion games to subclasses of WBFG and MWBFG, respectively, indicating their rich structure.We present a collection of complexity results about decision (and search) problems for both pure and payoff-dominant equilibria in WBFG. The precise complexities depend crucially on five parameters: (i) the number of players; (ii) the number of variables per player; (iii) the number of formulas per player; (iv) the weights in the payoff functions (whether identical or not), and (v) the syntax of the formulas. These results imply that, unless the polynomial hierarchy collapses, decision (and search) problems for payoff-dominant equilibria are harde than for pure equilibria.},

series = {LNCS}

}

[DOI]
author = {Burkhard Monien AND Marios Mavronicolas AND Klaus Wagner},

title = {Weighted Boolean Formula Games},

booktitle = {the ´Festschrift´ Algorithms, Probability, Networks, and Games: Scientific Papers and Essays Dedicated to Paul G. Spirakis on the Occasion of His 60th Birthday},

year = {2015},

pages = {49-86},

publisher = {Springer},

abstract = {We introduce weighted boolean formula games (WBFG) as a new class of succinct games. Each player has a set of boolean formulas she wants to get satisfied; the formulas involve a ground set of boolean variables each of which is controlled by some player. The payoff of a player is a weighted sum of the values of her formulas. We consider both pure equilibria and their refinement of payoff-dominant equilibria [34], where every player is no worse-off than in any other pure equilibrium. We present both structural and complexity results:We consider mutual weighted boolean formula games (MWBFG), a subclass of WBFG making a natural mutuality assumption on the formulas of players. We present a very simple exact potential for MWBFG. We establish a polynomial monomorphism from certain classes of weighted congestion games to subclasses of WBFG and MWBFG, respectively, indicating their rich structure.We present a collection of complexity results about decision (and search) problems for both pure and payoff-dominant equilibria in WBFG. The precise complexities depend crucially on five parameters: (i) the number of players; (ii) the number of variables per player; (iii) the number of formulas per player; (iv) the weights in the payoff functions (whether identical or not), and (v) the syntax of the formulas. These results imply that, unless the polynomial hierarchy collapses, decision (and search) problems for payoff-dominant equilibria are harde than for pure equilibria.},

series = {LNCS}

}

Burkhard Monien, Marios Mavronicolas:

In

[Show Abstract]

**The complexity of pure equilibria in mix-weighted congestion games on parallel links**In

*Information Processing Letters*, pp. 927-931. Elsevier**(2015)**[Show Abstract]

We revisit the simple class of weighted congestion games on parallel links [10], where each player has a non-negative weight and her cost on the link she chooses is the sum of the weights of all players choosing the link. We extend this class to mix-weighted congestion games on parallel links, where weights may as well be negative. For the resulting simple class, we study the complexity of deciding the existence of a pure equilibrium, where no player could unilaterally improve her cost by switching to another link.

We show that even for a singlenegative weight, this decision problem is strongly NP-complete when the number of links is part of the input; the problem is NP-complete already for two links. When the number of links is a fixed constant, we show, through a pseudopolynomial, dynamic programming algorithm, that the problem is not strongly NP-complete unless P = NP; the algorithm works for any number of negative weights.

[Show BibTeX] We show that even for a singlenegative weight, this decision problem is strongly NP-complete when the number of links is part of the input; the problem is NP-complete already for two links. When the number of links is a fixed constant, we show, through a pseudopolynomial, dynamic programming algorithm, that the problem is not strongly NP-complete unless P = NP; the algorithm works for any number of negative weights.

@article{MM2015,

author = {Burkhard Monien AND Marios Mavronicolas},

title = {The complexity of pure equilibria in mix-weighted congestion games on parallel links},

journal = {Information Processing Letters},

year = {2015},

pages = {927-931},

abstract = {We revisit the simple class of weighted congestion games on parallel links [10], where each player has a non-negative weight and her cost on the link she chooses is the sum of the weights of all players choosing the link. We extend this class to mix-weighted congestion games on parallel links, where weights may as well be negative. For the resulting simple class, we study the complexity of deciding the existence of a pure equilibrium, where no player could unilaterally improve her cost by switching to another link.We show that even for a singlenegative weight, this decision problem is strongly NP-complete when the number of links is part of the input; the problem is NP-complete already for two links. When the number of links is a fixed constant, we show, through a pseudopolynomial, dynamic programming algorithm, that the problem is not strongly NP-complete unless P = NP; the algorithm works for any number of negative weights.}

}

[DOI]
author = {Burkhard Monien AND Marios Mavronicolas},

title = {The complexity of pure equilibria in mix-weighted congestion games on parallel links},

journal = {Information Processing Letters},

year = {2015},

pages = {927-931},

abstract = {We revisit the simple class of weighted congestion games on parallel links [10], where each player has a non-negative weight and her cost on the link she chooses is the sum of the weights of all players choosing the link. We extend this class to mix-weighted congestion games on parallel links, where weights may as well be negative. For the resulting simple class, we study the complexity of deciding the existence of a pure equilibrium, where no player could unilaterally improve her cost by switching to another link.We show that even for a singlenegative weight, this decision problem is strongly NP-complete when the number of links is part of the input; the problem is NP-complete already for two links. When the number of links is a fixed constant, we show, through a pseudopolynomial, dynamic programming algorithm, that the problem is not strongly NP-complete unless P = NP; the algorithm works for any number of negative weights.}

}

Sonja Brangewitz, Claus-Jochen Haake, Philipp Möhlmeier:

Techreport UPB.

[Show Abstract]

**Strategic Formation of Customer Relationship Networks**Techreport UPB.

**(2015)**[Show Abstract]

We analyze the stability of networks when two intermediaries strategically form costly links to customers. We interpret these links as customer relationships that enable trade to sell a product. Equilibrium prices and equilibrium quantities on the output as well as on the input market are determined endogenously for a given network of customer relationships. We investigate in how far the substitutability of the intermediaries' products and the costs of link formation influence the intermediaries' equilibrium profits and thus have an impact on the incentives to strategically form relationships to customers. For networks with three customers we characterize locally stable networks, in particular existence is guaranteed for any degree of substitutability. Moreover for the special cases of perfect complements, independent products and perfect substitutes, local stability coincides with the stronger concept of Nash stability. Additionally, for networks with n customers we analyze stability regions for selected networks and determine their limits when n goes to infinity. It turns out that the shape of the stability regions for those networks does not significantly change compared to a setting with a small number of customers.

[Show BibTeX] @techreport{SBPHCJH2015a,

author = {Sonja Brangewitz AND Claus-Jochen Haake AND Philipp M{\"o}hlmeier},

title = {Strategic Formation of Customer Relationship Networks},

year = {2015},

type = {Techreport UPB},

abstract = {We analyze the stability of networks when two intermediaries strategically form costly links to customers. We interpret these links as customer relationships that enable trade to sell a product. Equilibrium prices and equilibrium quantities on the output as well as on the input market are determined endogenously for a given network of customer relationships. We investigate in how far the substitutability of the intermediaries' products and the costs of link formation influence the intermediaries' equilibrium profits and thus have an impact on the incentives to strategically form relationships to customers. For networks with three customers we characterize locally stable networks, in particular existence is guaranteed for any degree of substitutability. Moreover for the special cases of perfect complements, independent products and perfect substitutes, local stability coincides with the stronger concept of Nash stability. Additionally, for networks with n customers we analyze stability regions for selected networks and determine their limits when n goes to infinity. It turns out that the shape of the stability regions for those networks does not significantly change compared to a setting with a small number of customers. }

}

author = {Sonja Brangewitz AND Claus-Jochen Haake AND Philipp M{\"o}hlmeier},

title = {Strategic Formation of Customer Relationship Networks},

year = {2015},

type = {Techreport UPB},

abstract = {We analyze the stability of networks when two intermediaries strategically form costly links to customers. We interpret these links as customer relationships that enable trade to sell a product. Equilibrium prices and equilibrium quantities on the output as well as on the input market are determined endogenously for a given network of customer relationships. We investigate in how far the substitutability of the intermediaries' products and the costs of link formation influence the intermediaries' equilibrium profits and thus have an impact on the incentives to strategically form relationships to customers. For networks with three customers we characterize locally stable networks, in particular existence is guaranteed for any degree of substitutability. Moreover for the special cases of perfect complements, independent products and perfect substitutes, local stability coincides with the stronger concept of Nash stability. Additionally, for networks with n customers we analyze stability regions for selected networks and determine their limits when n goes to infinity. It turns out that the shape of the stability regions for those networks does not significantly change compared to a setting with a small number of customers. }

}

Berno Buechel, Nils Roehl:

In

[Show Abstract]

**Robust equilibria in location games**In

*European Journal of Operational Research*, vol. 240, no. 2, pp. 505-517. Elsevier**(2015)**[Show Abstract]

In the framework of spatial competition, two or more players strategically choose a location in order to attract consumers. It is assumed standardly that consumers with the same favorite location fully agree on the ranking of all possible locations. To investigate the necessity of this questionable and restrictive assumption, we model heterogeneity in consumers’ distance perceptions by individual edge lengths of a given graph. A profile of location choices is called a “robust equilibrium” if it is a Nash equilibrium in several games which differ only by the consumers’ perceptions of distances. For a finite number of players and any distribution of consumers, we provide a complete characterization of robust equilibria and derive structural conditions for their existence. Furthermore, we discuss whether the classical observations of minimal differentiation and inefficiency are robust phenomena. Thereby, we find strong support for an old conjecture that in equilibrium firms form local clusters.

[Show BibTeX] @article{BBRN2015,

author = {Berno Buechel AND Nils Roehl},

title = {Robust equilibria in location games},

journal = {European Journal of Operational Research},

year = {2015},

volume = {240},

number = {2},

pages = {505-517},

abstract = {In the framework of spatial competition, two or more players strategically choose a location in order to attract consumers. It is assumed standardly that consumers with the same favorite location fully agree on the ranking of all possible locations. To investigate the necessity of this questionable and restrictive assumption, we model heterogeneity in consumers’ distance perceptions by individual edge lengths of a given graph. A profile of location choices is called a “robust equilibrium” if it is a Nash equilibrium in several games which differ only by the consumers’ perceptions of distances. For a finite number of players and any distribution of consumers, we provide a complete characterization of robust equilibria and derive structural conditions for their existence. Furthermore, we discuss whether the classical observations of minimal differentiation and inefficiency are robust phenomena. Thereby, we find strong support for an old conjecture that in equilibrium firms form local clusters.}

}

[DOI]
author = {Berno Buechel AND Nils Roehl},

title = {Robust equilibria in location games},

journal = {European Journal of Operational Research},

year = {2015},

volume = {240},

number = {2},

pages = {505-517},

abstract = {In the framework of spatial competition, two or more players strategically choose a location in order to attract consumers. It is assumed standardly that consumers with the same favorite location fully agree on the ranking of all possible locations. To investigate the necessity of this questionable and restrictive assumption, we model heterogeneity in consumers’ distance perceptions by individual edge lengths of a given graph. A profile of location choices is called a “robust equilibrium” if it is a Nash equilibrium in several games which differ only by the consumers’ perceptions of distances. For a finite number of players and any distribution of consumers, we provide a complete characterization of robust equilibria and derive structural conditions for their existence. Furthermore, we discuss whether the classical observations of minimal differentiation and inefficiency are robust phenomena. Thereby, we find strong support for an old conjecture that in equilibrium firms form local clusters.}

}

Maximilian Drees, Matthias Feldotto, Sören Riechers, Alexander Skopalik:

In Proceedings of the 8th International Symposium on Algorithmic Game Theory (SAGT). Springer Berlin Heidelberg, Lecture Notes in Computer Science, vol. 9347, pp. 178-189

[Show Abstract]

**On Existence and Properties of Approximate Pure Nash Equilibria in Bandwidth Allocation Games**In Proceedings of the 8th International Symposium on Algorithmic Game Theory (SAGT). Springer Berlin Heidelberg, Lecture Notes in Computer Science, vol. 9347, pp. 178-189

**(2015)**[Show Abstract]

In \emphbandwidth allocation games (BAGs), the strategy of a player consists of various demands on different resources. The player's utility is at most the sum of these demands, provided they are fully satisfied. Every resource has a limited capacity and if it is exceeded by the total demand, it has to be split between the players. Since these games generally do not have pure Nash equilibria, we consider approximate pure Nash equilibria, in which no player can improve her utility by more than some fixed factor $\alpha$ through unilateral strategy changes. There is a threshold $\alpha_\delta$ (where $\delta$ is a parameter that limits the demand of each player on a specific resource) such that $\alpha$-approximate pure Nash equilibria always exist for $\alpha \geq \alpha_\delta$, but not for $\alpha < \alpha_\delta$. We give both upper and lower bounds on this threshold $\alpha_\delta$ and show that the corresponding decision problem is $\sf NP$-hard. We also show that the $\alpha$-approximate price of anarchy for BAGs is $\alpha+1$. For a restricted version of the game, where demands of players only differ slightly from each other (e.g. symmetric games), we show that approximate Nash equilibria can be reached (and thus also be computed) in polynomial time using the best-response dynamic. Finally, we show that a broader class of utility-maximization games (which includes BAGs) converges quickly towards states whose social welfare is close to the optimum.

[Show BibTeX] @inproceedings{DFRS15,

author = {Maximilian Drees AND Matthias Feldotto AND S{\"o}ren Riechers AND Alexander Skopalik},

title = {On Existence and Properties of Approximate Pure Nash Equilibria in Bandwidth Allocation Games},

booktitle = {Proceedings of the 8th International Symposium on Algorithmic Game Theory (SAGT)},

year = {2015},

pages = {178-189},

publisher = {Springer Berlin Heidelberg},

abstract = {In \emph{bandwidth allocation games} (BAGs), the strategy of a player consists of various demands on different resources. The player's utility is at most the sum of these demands, provided they are fully satisfied. Every resource has a limited capacity and if it is exceeded by the total demand, it has to be split between the players. Since these games generally do not have pure Nash equilibria, we consider approximate pure Nash equilibria, in which no player can improve her utility by more than some fixed factor $\alpha$ through unilateral strategy changes. There is a threshold $\alpha_\delta$ (where $\delta$ is a parameter that limits the demand of each player on a specific resource) such that $\alpha$-approximate pure Nash equilibria always exist for $\alpha \geq \alpha_\delta$, but not for $\alpha < \alpha_\delta$. We give both upper and lower bounds on this threshold $\alpha_\delta$ and show that the corresponding decision problem is ${\sf NP}$-hard. We also show that the $\alpha$-approximate price of anarchy for BAGs is $\alpha+1$. For a restricted version of the game, where demands of players only differ slightly from each other (e.g. symmetric games), we show that approximate Nash equilibria can be reached (and thus also be computed) in polynomial time using the best-response dynamic. Finally, we show that a broader class of utility-maximization games (which includes BAGs) converges quickly towards states whose social welfare is close to the optimum.},

series = {Lecture Notes in Computer Science}

}

[DOI]
author = {Maximilian Drees AND Matthias Feldotto AND S{\"o}ren Riechers AND Alexander Skopalik},

title = {On Existence and Properties of Approximate Pure Nash Equilibria in Bandwidth Allocation Games},

booktitle = {Proceedings of the 8th International Symposium on Algorithmic Game Theory (SAGT)},

year = {2015},

pages = {178-189},

publisher = {Springer Berlin Heidelberg},

abstract = {In \emph{bandwidth allocation games} (BAGs), the strategy of a player consists of various demands on different resources. The player's utility is at most the sum of these demands, provided they are fully satisfied. Every resource has a limited capacity and if it is exceeded by the total demand, it has to be split between the players. Since these games generally do not have pure Nash equilibria, we consider approximate pure Nash equilibria, in which no player can improve her utility by more than some fixed factor $\alpha$ through unilateral strategy changes. There is a threshold $\alpha_\delta$ (where $\delta$ is a parameter that limits the demand of each player on a specific resource) such that $\alpha$-approximate pure Nash equilibria always exist for $\alpha \geq \alpha_\delta$, but not for $\alpha < \alpha_\delta$. We give both upper and lower bounds on this threshold $\alpha_\delta$ and show that the corresponding decision problem is ${\sf NP}$-hard. We also show that the $\alpha$-approximate price of anarchy for BAGs is $\alpha+1$. For a restricted version of the game, where demands of players only differ slightly from each other (e.g. symmetric games), we show that approximate Nash equilibria can be reached (and thus also be computed) in polynomial time using the best-response dynamic. Finally, we show that a broader class of utility-maximization games (which includes BAGs) converges quickly towards states whose social welfare is close to the optimum.},

series = {Lecture Notes in Computer Science}

}

Sonja Brangewitz, Claus-Jochen Haake, Jochen Manegold:

In Ortiz, Guadalupe and Tran, Cuong (eds.): Advances in Service-Oriented and Cloud Computing. Springer International Publishing, Communications in Computer and Information Science, vol. 508, pp. 160-174

[Show Abstract]

**Contract Design for Composed Services in a Cloud Computing Environment**In Ortiz, Guadalupe and Tran, Cuong (eds.): Advances in Service-Oriented and Cloud Computing. Springer International Publishing, Communications in Computer and Information Science, vol. 508, pp. 160-174

**(2015)**(Proceedings of the 2nd International Workshop on Cloud Service Brokerage, CSB 2014)[Show Abstract]

In this paper, we study markets in which sellers and buyers

interact with each other via an intermediary. Our motivating example

is a market with a cloud infrastructure where single services are

exibly combined to composed services. We address the contract design problem

of an intermediary to purchase complementary single services. By using

a non-cooperative game-theoretic model, we analyze the incentives for

high- and low-quality composed services to be an equilibrium outcome of

the market. It turns out that equilibria with low quality can be obtained

in the short run and in the long run, whereas those with high quality can

only be achieved in the long run. In our analysis we explicitly determine

the according discount factors needed in an infinitely repeated game.

Furthermore, we derive optimal contracts for the supply of high- and

low-quality composed services.

[Show BibTeX] interact with each other via an intermediary. Our motivating example

is a market with a cloud infrastructure where single services are

exibly combined to composed services. We address the contract design problem

of an intermediary to purchase complementary single services. By using

a non-cooperative game-theoretic model, we analyze the incentives for

high- and low-quality composed services to be an equilibrium outcome of

the market. It turns out that equilibria with low quality can be obtained

in the short run and in the long run, whereas those with high quality can

only be achieved in the long run. In our analysis we explicitly determine

the according discount factors needed in an infinitely repeated game.

Furthermore, we derive optimal contracts for the supply of high- and

low-quality composed services.

@inproceedings{BHM14,

author = {Sonja Brangewitz AND Claus-Jochen Haake AND Jochen Manegold},

title = {Contract Design for Composed Services in a Cloud Computing Environment},

booktitle = {Advances in Service-Oriented and Cloud Computing},

year = {2015},

editor = {Ortiz, Guadalupe and Tran, Cuong},

pages = {160-174},

publisher = {Springer International Publishing},

note = {Proceedings of the 2nd International Workshop on Cloud Service Brokerage, CSB 2014},

abstract = {In this paper, we study markets in which sellers and buyersinteract with each other via an intermediary. Our motivating exampleis a market with a cloud infrastructure where single services are exibly combined to composed services. We address the contract design problemof an intermediary to purchase complementary single services. By usinga non-cooperative game-theoretic model, we analyze the incentives forhigh- and low-quality composed services to be an equilibrium outcome ofthe market. It turns out that equilibria with low quality can be obtainedin the short run and in the long run, whereas those with high quality canonly be achieved in the long run. In our analysis we explicitly determinethe according discount factors needed in an infinitely repeated game.Furthermore, we derive optimal contracts for the supply of high- andlow-quality composed services.},

series = {Communications in Computer and Information Science}

}

[DOI]
author = {Sonja Brangewitz AND Claus-Jochen Haake AND Jochen Manegold},

title = {Contract Design for Composed Services in a Cloud Computing Environment},

booktitle = {Advances in Service-Oriented and Cloud Computing},

year = {2015},

editor = {Ortiz, Guadalupe and Tran, Cuong},

pages = {160-174},

publisher = {Springer International Publishing},

note = {Proceedings of the 2nd International Workshop on Cloud Service Brokerage, CSB 2014},

abstract = {In this paper, we study markets in which sellers and buyersinteract with each other via an intermediary. Our motivating exampleis a market with a cloud infrastructure where single services are exibly combined to composed services. We address the contract design problemof an intermediary to purchase complementary single services. By usinga non-cooperative game-theoretic model, we analyze the incentives forhigh- and low-quality composed services to be an equilibrium outcome ofthe market. It turns out that equilibria with low quality can be obtainedin the short run and in the long run, whereas those with high quality canonly be achieved in the long run. In our analysis we explicitly determinethe according discount factors needed in an infinitely repeated game.Furthermore, we derive optimal contracts for the supply of high- andlow-quality composed services.},

series = {Communications in Computer and Information Science}

}

Sonja Brangewitz, Jochen Manegold:

Techreport UPB.

[Show Abstract]

**Competition and Product Innovation of Intermediaries in a Differentiated Duopoly**Techreport UPB.

**(2015)**[Show Abstract]

On an intermediate goods market we allow for vertical and horizontal product differentiation and analyze the influence of simultaneous competition for resources and customers on the market outcome. Asymmetries between intermediaries cannot arise just from distinct product qualities, but also from different production technologies. The intermediaries face either price or quantity competition on the output market and a monopolistic input supplier on the input market. We find that there exist quality and productivity differences such that for quantity competition only one intermediary is willing to procure inputs from the input supplier, while for price competition both intermediaries are willing to purchase inputs. Considering product innovation for symmetric productivities we derive equilibrium conditions on the investment costs and compare price and quantity competition. It turns out that on the one hand there exist product qualities and degrees of horizontal product differentiation for complements such that asymmetric investment equilibria fail to exist. On the other hand we find that there also exist product qualities and degrees of horizontal product differentiation for substitutes such that existence can be guaranteed if the investment costs are chosen accordingly.

[Show BibTeX] @techreport{SBJM2015a,

author = {Sonja Brangewitz AND Jochen Manegold},

title = {Competition and Product Innovation of Intermediaries in a Differentiated Duopoly},

year = {2015},

type = {Techreport UPB},

abstract = {On an intermediate goods market we allow for vertical and horizontal product differentiation and analyze the influence of simultaneous competition for resources and customers on the market outcome. Asymmetries between intermediaries cannot arise just from distinct product qualities, but also from different production technologies. The intermediaries face either price or quantity competition on the output market and a monopolistic input supplier on the input market. We find that there exist quality and productivity differences such that for quantity competition only one intermediary is willing to procure inputs from the input supplier, while for price competition both intermediaries are willing to purchase inputs. Considering product innovation for symmetric productivities we derive equilibrium conditions on the investment costs and compare price and quantity competition. It turns out that on the one hand there exist product qualities and degrees of horizontal product differentiation for complements such that asymmetric investment equilibria fail to exist. On the other hand we find that there also exist product qualities and degrees of horizontal product differentiation for substitutes such that existence can be guaranteed if the investment costs are chosen accordingly.}

}

author = {Sonja Brangewitz AND Jochen Manegold},

title = {Competition and Product Innovation of Intermediaries in a Differentiated Duopoly},

year = {2015},

type = {Techreport UPB},

abstract = {On an intermediate goods market we allow for vertical and horizontal product differentiation and analyze the influence of simultaneous competition for resources and customers on the market outcome. Asymmetries between intermediaries cannot arise just from distinct product qualities, but also from different production technologies. The intermediaries face either price or quantity competition on the output market and a monopolistic input supplier on the input market. We find that there exist quality and productivity differences such that for quantity competition only one intermediary is willing to procure inputs from the input supplier, while for price competition both intermediaries are willing to purchase inputs. Considering product innovation for symmetric productivities we derive equilibrium conditions on the investment costs and compare price and quantity competition. It turns out that on the one hand there exist product qualities and degrees of horizontal product differentiation for complements such that asymmetric investment equilibria fail to exist. On the other hand we find that there also exist product qualities and degrees of horizontal product differentiation for substitutes such that existence can be guaranteed if the investment costs are chosen accordingly.}

}

Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, Alexander Skopalik:

In

[Show Abstract]

**Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure**In

*Transactions on Economics and Computation*, vol. 3, no. 1, pp. 2. ACM**(2015)**[Show Abstract]

We consider structural and algorithmic questions related to the Nash dynamics of weighted congestion games. In weighted congestion games with linear latency functions, the existence of pure Nash equilibria is guaranteed by a potential function argument. Unfortunately, this proof of existence is inefficient and computing pure Nash equilibria in such games is a PLS-hard problem even when all players have unit weights. The situation gets worse when superlinear (e.g., quadratic) latency functions come into play; in this case, the Nash dynamics of the game may contain cycles and pure Nash equilibria may not even exist. Given these obstacles, we consider approximate pure Nash equilibria as alternative solution concepts. A ρ-approximate pure Nash equilibrium is a state of a (weighted congestion) game from which no player has any incentive to deviate in order to improve her cost by a multiplicative factor higher than ρ. Do such equilibria exist for small values of ρ? And if so, can we compute them efficiently?

We provide positive answers to both questions for weighted congestion games with polynomial latency functions by exploiting an “approximation” of such games by a new class of potential games that we call Ψ-games. This allows us to show that these games have d!-approximate pure Nash equilibria, where d is the maximum degree of the latency functions. Our main technical contribution is an efficient algorithm for computing O(1)-approximate pure Nash equilibria when d is a constant. For games with linear latency functions, the approximation guarantee is 3+√5/2 + Oγ for arbitrarily small γ > 0; for latency functions with maximum degree d≥ 2, it is d2d+o(d). The running time is polynomial in the number of bits in the representation of the game and 1/γ. As a byproduct of our techniques, we also show the following interesting structural statement for weighted congestion games with polynomial latency functions of maximum degree d ≥ 2: polynomially-long sequences of best-response moves from any initial state to a dO(d2)-approximate pure Nash equilibrium exist and can be efficiently identified in such games as long as d is a constant.

To the best of our knowledge, these are the first positive algorithmic results for approximate pure Nash equilibria in weighted congestion games. Our techniques significantly extend our recent work on unweighted congestion games through the use of Ψ-games. The concept of approximating nonpotential games by potential ones is interesting in itself and might have further applications.

[Show BibTeX] We provide positive answers to both questions for weighted congestion games with polynomial latency functions by exploiting an “approximation” of such games by a new class of potential games that we call Ψ-games. This allows us to show that these games have d!-approximate pure Nash equilibria, where d is the maximum degree of the latency functions. Our main technical contribution is an efficient algorithm for computing O(1)-approximate pure Nash equilibria when d is a constant. For games with linear latency functions, the approximation guarantee is 3+√5/2 + Oγ for arbitrarily small γ > 0; for latency functions with maximum degree d≥ 2, it is d2d+o(d). The running time is polynomial in the number of bits in the representation of the game and 1/γ. As a byproduct of our techniques, we also show the following interesting structural statement for weighted congestion games with polynomial latency functions of maximum degree d ≥ 2: polynomially-long sequences of best-response moves from any initial state to a dO(d2)-approximate pure Nash equilibrium exist and can be efficiently identified in such games as long as d is a constant.

To the best of our knowledge, these are the first positive algorithmic results for approximate pure Nash equilibria in weighted congestion games. Our techniques significantly extend our recent work on unweighted congestion games through the use of Ψ-games. The concept of approximating nonpotential games by potential ones is interesting in itself and might have further applications.

@article{DBLP:journals/teco/CaragiannisFGS15,

author = {Ioannis Caragiannis AND Angelo Fanelli AND Nick Gravin AND Alexander Skopalik},

title = {Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure},

journal = {Transactions on Economics and Computation},

year = {2015},

volume = {3},

number = {1},

pages = {2},

abstract = {We consider structural and algorithmic questions related to the Nash dynamics of weighted congestion games. In weighted congestion games with linear latency functions, the existence of pure Nash equilibria is guaranteed by a potential function argument. Unfortunately, this proof of existence is inefficient and computing pure Nash equilibria in such games is a PLS-hard problem even when all players have unit weights. The situation gets worse when superlinear (e.g., quadratic) latency functions come into play; in this case, the Nash dynamics of the game may contain cycles and pure Nash equilibria may not even exist. Given these obstacles, we consider approximate pure Nash equilibria as alternative solution concepts. A ρ--approximate pure Nash equilibrium is a state of a (weighted congestion) game from which no player has any incentive to deviate in order to improve her cost by a multiplicative factor higher than ρ. Do such equilibria exist for small values of ρ? And if so, can we compute them efficiently?We provide positive answers to both questions for weighted congestion games with polynomial latency functions by exploiting an “approximation” of such games by a new class of potential games that we call Ψ-games. This allows us to show that these games have d!-approximate pure Nash equilibria, where d is the maximum degree of the latency functions. Our main technical contribution is an efficient algorithm for computing O(1)-approximate pure Nash equilibria when d is a constant. For games with linear latency functions, the approximation guarantee is 3+√5/2 + Oγ for arbitrarily small γ > 0; for latency functions with maximum degree d≥ 2, it is d2d+o(d). The running time is polynomial in the number of bits in the representation of the game and 1/γ. As a byproduct of our techniques, we also show the following interesting structural statement for weighted congestion games with polynomial latency functions of maximum degree d ≥ 2: polynomially-long sequences of best-response moves from any initial state to a dO(d2)-approximate pure Nash equilibrium exist and can be efficiently identified in such games as long as d is a constant.To the best of our knowledge, these are the first positive algorithmic results for approximate pure Nash equilibria in weighted congestion games. Our techniques significantly extend our recent work on unweighted congestion games through the use of Ψ-games. The concept of approximating nonpotential games by potential ones is interesting in itself and might have further applications.}

}

[DOI]
author = {Ioannis Caragiannis AND Angelo Fanelli AND Nick Gravin AND Alexander Skopalik},

title = {Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure},

journal = {Transactions on Economics and Computation},

year = {2015},

volume = {3},

number = {1},

pages = {2},

abstract = {We consider structural and algorithmic questions related to the Nash dynamics of weighted congestion games. In weighted congestion games with linear latency functions, the existence of pure Nash equilibria is guaranteed by a potential function argument. Unfortunately, this proof of existence is inefficient and computing pure Nash equilibria in such games is a PLS-hard problem even when all players have unit weights. The situation gets worse when superlinear (e.g., quadratic) latency functions come into play; in this case, the Nash dynamics of the game may contain cycles and pure Nash equilibria may not even exist. Given these obstacles, we consider approximate pure Nash equilibria as alternative solution concepts. A ρ--approximate pure Nash equilibrium is a state of a (weighted congestion) game from which no player has any incentive to deviate in order to improve her cost by a multiplicative factor higher than ρ. Do such equilibria exist for small values of ρ? And if so, can we compute them efficiently?We provide positive answers to both questions for weighted congestion games with polynomial latency functions by exploiting an “approximation” of such games by a new class of potential games that we call Ψ-games. This allows us to show that these games have d!-approximate pure Nash equilibria, where d is the maximum degree of the latency functions. Our main technical contribution is an efficient algorithm for computing O(1)-approximate pure Nash equilibria when d is a constant. For games with linear latency functions, the approximation guarantee is 3+√5/2 + Oγ for arbitrarily small γ > 0; for latency functions with maximum degree d≥ 2, it is d2d+o(d). The running time is polynomial in the number of bits in the representation of the game and 1/γ. As a byproduct of our techniques, we also show the following interesting structural statement for weighted congestion games with polynomial latency functions of maximum degree d ≥ 2: polynomially-long sequences of best-response moves from any initial state to a dO(d2)-approximate pure Nash equilibrium exist and can be efficiently identified in such games as long as d is a constant.To the best of our knowledge, these are the first positive algorithmic results for approximate pure Nash equilibria in weighted congestion games. Our techniques significantly extend our recent work on unweighted congestion games through the use of Ψ-games. The concept of approximating nonpotential games by potential ones is interesting in itself and might have further applications.}

}

**2014** (16)

Sonja Brangewitz, Alexander Jungmann, Ronald Petrlic, Marie Christin Platenius:

In Proceedings of the 6th International Conferences on Advanced Service Computing (SERVICE COMPUTATION). IARIA XPS Press, pp. 49-57

[Show Abstract]

**Towards a Flexible and Privacy-Preserving Reputation System for Markets of Composed Services**In Proceedings of the 6th International Conferences on Advanced Service Computing (SERVICE COMPUTATION). IARIA XPS Press, pp. 49-57

**(2014)**[Show Abstract]

One future goal of service-oriented computing is to realize global markets of composed services. On such markets, service providers offer services that can be flexibly combined with each other. However, most often, market participants are not able to individually estimate the quality of traded services in advance. As a consequence, even potentially profitable transactions between customers and providers might not take place. In the worst case, this can induce a market failure. To overcome this problem, we propose the incorporation of reputation information as an indicator for expected service quality. We address On-The-Fly Computing as a representative environment of markets of composed services. In this environment, customers provide feedback on transactions. We present a conceptual design of a reputation system which collects and processes user feedback, and provides it to participants in the market. Our contribution includes the identification of requirements for such a reputation system from a technical and an economic perspective. Based on these requirements, we propose a flexible solution that facilitates the incorporation of reputation information into markets of composed services while simultaneously preserving privacy of customers who provide feedback. The requirements we formulate in this paper have just been partially met in literature. An integrated approach, however, has not been addressed yet.

[Show BibTeX] @inproceedings{BJPP2014,

author = {Sonja Brangewitz AND Alexander Jungmann AND Ronald Petrlic AND Marie Christin Platenius},

title = {Towards a Flexible and Privacy-Preserving Reputation System for Markets of Composed Services},

booktitle = {Proceedings of the 6th International Conferences on Advanced Service Computing (SERVICE COMPUTATION)},

year = {2014},

pages = {49-57},

publisher = {IARIA XPS Press},

abstract = {One future goal of service-oriented computing is to realize global markets of composed services. On such markets, service providers offer services that can be flexibly combined with each other. However, most often, market participants are not able to individually estimate the quality of traded services in advance. As a consequence, even potentially profitable transactions between customers and providers might not take place. In the worst case, this can induce a market failure. To overcome this problem, we propose the incorporation of reputation information as an indicator for expected service quality. We address On-The-Fly Computing as a representative environment of markets of composed services. In this environment, customers provide feedback on transactions. We present a conceptual design of a reputation system which collects and processes user feedback, and provides it to participants in the market. Our contribution includes the identification of requirements for such a reputation system from a technical and an economic perspective. Based on these requirements, we propose a flexible solution that facilitates the incorporation of reputation information into markets of composed services while simultaneously preserving privacy of customers who provide feedback. The requirements we formulate in this paper have just been partially met in literature. An integrated approach, however, has not been addressed yet.}

}

[DOI]
author = {Sonja Brangewitz AND Alexander Jungmann AND Ronald Petrlic AND Marie Christin Platenius},

title = {Towards a Flexible and Privacy-Preserving Reputation System for Markets of Composed Services},

booktitle = {Proceedings of the 6th International Conferences on Advanced Service Computing (SERVICE COMPUTATION)},

year = {2014},

pages = {49-57},

publisher = {IARIA XPS Press},

abstract = {One future goal of service-oriented computing is to realize global markets of composed services. On such markets, service providers offer services that can be flexibly combined with each other. However, most often, market participants are not able to individually estimate the quality of traded services in advance. As a consequence, even potentially profitable transactions between customers and providers might not take place. In the worst case, this can induce a market failure. To overcome this problem, we propose the incorporation of reputation information as an indicator for expected service quality. We address On-The-Fly Computing as a representative environment of markets of composed services. In this environment, customers provide feedback on transactions. We present a conceptual design of a reputation system which collects and processes user feedback, and provides it to participants in the market. Our contribution includes the identification of requirements for such a reputation system from a technical and an economic perspective. Based on these requirements, we propose a flexible solution that facilitates the incorporation of reputation information into markets of composed services while simultaneously preserving privacy of customers who provide feedback. The requirements we formulate in this paper have just been partially met in literature. An integrated approach, however, has not been addressed yet.}

}

Daniel Kaimann, Joe Cox:

Techreport UPB.

[Show Abstract]

**The Interaction of Signals: A Fuzzy set Analysis of the Video Game Industry**Techreport UPB.

**(2014)**[Show Abstract]

Customers continuously evaluate the credibility and reliability of a range of signals both separately and jointly. However, existing econometric studies pay insufficient attention to the interactions and complex combinations of these signals, and are typically limited as a result of difficulties controlling for multicollinearity and endogeneity in their data. We develop a novel theoretical approach to address these issues and study different signaling effects (i.e., word-of-mouth, brand reputation, and distribution strategy) on customer perceptions. Using data on the US video games market, we apply a fuzzy set qualitative comparative analysis (fsQCA) to account for cause-effect relationships. The results of our study address a number of key issues in the economics and management literature. First, our results support the contention that reviews from professional critics act as a signal of product quality and therefore positively influence unit sales, as do the discriminatory effects of prices and restricted age ratings. Second, we find evidence to support the use of brand extension strategies as marketing tools that create spillover effects and support the launch of new products.

[Show BibTeX] @techreport{ck14,

author = {Daniel Kaimann AND Joe Cox},

title = {The Interaction of Signals: A Fuzzy set Analysis of the Video Game Industry},

year = {2014},

type = {Techreport UPB},

abstract = {Customers continuously evaluate the credibility and reliability of a range of signals both separately and jointly. However, existing econometric studies pay insufficient attention to the interactions and complex combinations of these signals, and are typically limited as a result of difficulties controlling for multicollinearity and endogeneity in their data. We develop a novel theoretical approach to address these issues and study different signaling effects (i.e., word-of-mouth, brand reputation, and distribution strategy) on customer perceptions. Using data on the US video games market, we apply a fuzzy set qualitative comparative analysis (fsQCA) to account for cause-effect relationships. The results of our study address a number of key issues in the economics and management literature. First, our results support the contention that reviews from professional critics act as a signal of product quality and therefore positively influence unit sales, as do the discriminatory effects of prices and restricted age ratings. Second, we find evidence to support the use of brand extension strategies as marketing tools that create spillover effects and support the launch of new products.}

}

author = {Daniel Kaimann AND Joe Cox},

title = {The Interaction of Signals: A Fuzzy set Analysis of the Video Game Industry},

year = {2014},

type = {Techreport UPB},

abstract = {Customers continuously evaluate the credibility and reliability of a range of signals both separately and jointly. However, existing econometric studies pay insufficient attention to the interactions and complex combinations of these signals, and are typically limited as a result of difficulties controlling for multicollinearity and endogeneity in their data. We develop a novel theoretical approach to address these issues and study different signaling effects (i.e., word-of-mouth, brand reputation, and distribution strategy) on customer perceptions. Using data on the US video games market, we apply a fuzzy set qualitative comparative analysis (fsQCA) to account for cause-effect relationships. The results of our study address a number of key issues in the economics and management literature. First, our results support the contention that reviews from professional critics act as a signal of product quality and therefore positively influence unit sales, as do the discriminatory effects of prices and restricted age ratings. Second, we find evidence to support the use of brand extension strategies as marketing tools that create spillover effects and support the launch of new products.}

}

Tobias Harks, Martin Höfer, Kevin Schewior, Alexander Skopalik:

In Proceedings of the 33rd Annual IEEE International Conference on Computer Communications (INFOCOM'14). IEEE, pp. 352-360

[Show Abstract]

**Routing Games with Progressive Filling**In Proceedings of the 33rd Annual IEEE International Conference on Computer Communications (INFOCOM'14). IEEE, pp. 352-360

**(2014)**[Show Abstract]

Max-min fairness (MMF) is a widely known approach to a fair allocation of bandwidth to each of the users in a network. This allocation can be computed by uniformly raising the bandwidths of all users without violating capacity constraints. We consider an extension of these allocations by raising the bandwidth with arbitrary and not necessarily uniform time-depending velocities (allocation rates). These allocations are used in a game-theoretic context for routing choices, which we formalize in progressive filling games (PFGs).

We present a variety of results for equilibria in PFGs. We show that these games possess pure Nash and strong equilibria. While computation in general is NP-hard, there are polynomial-time algorithms for prominent classes of Max-Min-Fair Games (MMFG), including the case when all users have the same source-destination pair. We characterize prices of anarchy and stability for pure Nash and strong equilibria in PFGs and MMFGs when players have different or the same source-destination pairs. In addition, we show that when a designer can adjust allocation rates, it is possible to design games with optimal strong equilibria. Some initial results on polynomial-time algorithms in this direction are also derived.

[Show BibTeX] We present a variety of results for equilibria in PFGs. We show that these games possess pure Nash and strong equilibria. While computation in general is NP-hard, there are polynomial-time algorithms for prominent classes of Max-Min-Fair Games (MMFG), including the case when all users have the same source-destination pair. We characterize prices of anarchy and stability for pure Nash and strong equilibria in PFGs and MMFGs when players have different or the same source-destination pairs. In addition, we show that when a designer can adjust allocation rates, it is possible to design games with optimal strong equilibria. Some initial results on polynomial-time algorithms in this direction are also derived.

@inproceedings{HHSS14,

author = {Tobias Harks AND Martin H{\"o}fer AND Kevin Schewior AND Alexander Skopalik},

title = {Routing Games with Progressive Filling},

booktitle = {Proceedings of the 33rd Annual IEEE International Conference on Computer Communications (INFOCOM'14)},

year = {2014},

pages = {352-360},

publisher = {IEEE},

abstract = {Max-min fairness (MMF) is a widely known approach to a fair allocation of bandwidth to each of the users in a network. This allocation can be computed by uniformly raising the bandwidths of all users without violating capacity constraints. We consider an extension of these allocations by raising the bandwidth with arbitrary and not necessarily uniform time-depending velocities (allocation rates). These allocations are used in a game-theoretic context for routing choices, which we formalize in progressive filling games (PFGs).We present a variety of results for equilibria in PFGs. We show that these games possess pure Nash and strong equilibria. While computation in general is NP-hard, there are polynomial-time algorithms for prominent classes of Max-Min-Fair Games (MMFG), including the case when all users have the same source-destination pair. We characterize prices of anarchy and stability for pure Nash and strong equilibria in PFGs and MMFGs when players have different or the same source-destination pairs. In addition, we show that when a designer can adjust allocation rates, it is possible to design games with optimal strong equilibria. Some initial results on polynomial-time algorithms in this direction are also derived. }

}

[DOI]
author = {Tobias Harks AND Martin H{\"o}fer AND Kevin Schewior AND Alexander Skopalik},

title = {Routing Games with Progressive Filling},

booktitle = {Proceedings of the 33rd Annual IEEE International Conference on Computer Communications (INFOCOM'14)},

year = {2014},

pages = {352-360},

publisher = {IEEE},

abstract = {Max-min fairness (MMF) is a widely known approach to a fair allocation of bandwidth to each of the users in a network. This allocation can be computed by uniformly raising the bandwidths of all users without violating capacity constraints. We consider an extension of these allocations by raising the bandwidth with arbitrary and not necessarily uniform time-depending velocities (allocation rates). These allocations are used in a game-theoretic context for routing choices, which we formalize in progressive filling games (PFGs).We present a variety of results for equilibria in PFGs. We show that these games possess pure Nash and strong equilibria. While computation in general is NP-hard, there are polynomial-time algorithms for prominent classes of Max-Min-Fair Games (MMFG), including the case when all users have the same source-destination pair. We characterize prices of anarchy and stability for pure Nash and strong equilibria in PFGs and MMFGs when players have different or the same source-destination pairs. In addition, we show that when a designer can adjust allocation rates, it is possible to design games with optimal strong equilibria. Some initial results on polynomial-time algorithms in this direction are also derived. }

}

Sonja Brangewitz, Behnud Djawadi, Rene Fahr, Claus-Jochen Haake:

Techreport UPB.

[Show Abstract]

**Quality Choices and Reputation Systems in Online Markets - An Experimental Study**Techreport UPB.

**(2014)**[Show Abstract]

In internet transactions where customers and service providers often interact once and anonymously, a reputation system is particularly important to reduce information asymmetries about product quality. In this study we experimentally examine the impact of the customers' evaluation abilities on strategic quality choices of a service provider. Our study is motivated by a simple theoretical model where short-lived customers are asked to evaluate the observed quality of the service provider's product by providing ratings to a reputation system. A reputation profile informs about the ratings of the last three sales. This profile gives new customers an indicator for the quality they have to expect and determines the sales price of the product. From the theoretical model we derive that the service provider's dichotomous quality decisions are independent of the reputation profile and depend only on the probabilities of receiving positive and negative ratings when providing low or high quality. However, when mapping our theoretical model to an experimental design we find that subjects in the role of the service provider deviate from optimal behavior and choose actions which are conditional on the current reputation profile. In addition, increasing the probability of a negative rating and decreasing the probability of a positive rating both do not affect strategic quality choices.

[Show BibTeX] @techreport{BSDBFRHCJ2014,

author = {Sonja Brangewitz AND Behnud Djawadi AND Rene Fahr AND Claus-Jochen Haake},

title = {Quality Choices and Reputation Systems in Online Markets - An Experimental Study},

year = {2014},

type = {Techreport UPB},

abstract = {In internet transactions where customers and service providers often interact once and anonymously, a reputation system is particularly important to reduce information asymmetries about product quality. In this study we experimentally examine the impact of the customers' evaluation abilities on strategic quality choices of a service provider. Our study is motivated by a simple theoretical model where short-lived customers are asked to evaluate the observed quality of the service provider's product by providing ratings to a reputation system. A reputation profile informs about the ratings of the last three sales. This profile gives new customers an indicator for the quality they have to expect and determines the sales price of the product. From the theoretical model we derive that the service provider's dichotomous quality decisions are independent of the reputation profile and depend only on the probabilities of receiving positive and negative ratings when providing low or high quality. However, when mapping our theoretical model to an experimental design we find that subjects in the role of the service provider deviate from optimal behavior and choose actions which are conditional on the current reputation profile. In addition, increasing the probability of a negative rating and decreasing the probability of a positive rating both do not affect strategic quality choices.}

}

author = {Sonja Brangewitz AND Behnud Djawadi AND Rene Fahr AND Claus-Jochen Haake},

title = {Quality Choices and Reputation Systems in Online Markets - An Experimental Study},

year = {2014},

type = {Techreport UPB},

abstract = {In internet transactions where customers and service providers often interact once and anonymously, a reputation system is particularly important to reduce information asymmetries about product quality. In this study we experimentally examine the impact of the customers' evaluation abilities on strategic quality choices of a service provider. Our study is motivated by a simple theoretical model where short-lived customers are asked to evaluate the observed quality of the service provider's product by providing ratings to a reputation system. A reputation profile informs about the ratings of the last three sales. This profile gives new customers an indicator for the quality they have to expect and determines the sales price of the product. From the theoretical model we derive that the service provider's dichotomous quality decisions are independent of the reputation profile and depend only on the probabilities of receiving positive and negative ratings when providing low or high quality. However, when mapping our theoretical model to an experimental design we find that subjects in the role of the service provider deviate from optimal behavior and choose actions which are conditional on the current reputation profile. In addition, increasing the probability of a negative rating and decreasing the probability of a positive rating both do not affect strategic quality choices.}

}

Jörn Künsemöller, Sonja Brangewitz, Holger Karl, Claus-Jochen Haake:

In Proceedings of the 2014 IEEE International Conference on Services Computing (SCC). IEEE Computer Society, pp. 203-210

[Show Abstract]

**Provider Competition in Infrastructure-as-a-Service**In Proceedings of the 2014 IEEE International Conference on Services Computing (SCC). IEEE Computer Society, pp. 203-210

**(2014)**[Show Abstract]

This paper explores how cloud provider competition inﬂuences instance pricing in an IaaS (Infrastructure-as-a-Service) market. When reserved instance pricing includes an on-demand price component in addition to a reservation fee (two-part tariffs), different providers might offer different price combinations, where the client’s choice depends on its load proﬁle. We investigate a duopoly of providers and analyze stable market prices in two-part tariffs. Further, we study offers that allow a speciﬁed amount of included usage (three-part tariffs). Neither two-part nor three-part tariffs produce an equilibrium market outcome other than a service pricing that equals production cost, i.e., complex price structures do not signiﬁcantly affect the results from ordinary Bertrand competition.

[Show BibTeX] @inproceedings{KKBH-2014,

author = {J{\"o}rn K{\"u}nsem{\"o}ller AND Sonja Brangewitz AND Holger Karl AND Claus-Jochen Haake},

title = {Provider Competition in Infrastructure-as-a-Service},

booktitle = {Proceedings of the 2014 IEEE International Conference onServices Computing (SCC)},

year = {2014},

pages = {203-210},

publisher = {IEEE Computer Society},

month = {June},

abstract = {This paper explores how cloud provider competition inﬂuences instance pricing in an IaaS (Infrastructure-as-a-Service) market. When reserved instance pricing includes an on-demand price component in addition to a reservation fee (two-part tariffs), different providers might offer different price combinations, where the client’s choice depends on its load proﬁle. We investigate a duopoly of providers and analyze stable market prices in two-part tariffs. Further, we study offers that allow a speciﬁed amount of included usage (three-part tariffs). Neither two-part nor three-part tariffs produce an equilibrium market outcome other than a service pricing that equals production cost, i.e., complex price structures do not signiﬁcantly affect the results from ordinary Bertrand competition.}

}

[DOI]
author = {J{\"o}rn K{\"u}nsem{\"o}ller AND Sonja Brangewitz AND Holger Karl AND Claus-Jochen Haake},

title = {Provider Competition in Infrastructure-as-a-Service},

booktitle = {Proceedings of the 2014 IEEE International Conference onServices Computing (SCC)},

year = {2014},

pages = {203-210},

publisher = {IEEE Computer Society},

month = {June},

abstract = {This paper explores how cloud provider competition inﬂuences instance pricing in an IaaS (Infrastructure-as-a-Service) market. When reserved instance pricing includes an on-demand price component in addition to a reservation fee (two-part tariffs), different providers might offer different price combinations, where the client’s choice depends on its load proﬁle. We investigate a duopoly of providers and analyze stable market prices in two-part tariffs. Further, we study offers that allow a speciﬁed amount of included usage (three-part tariffs). Neither two-part nor three-part tariffs produce an equilibrium market outcome other than a service pricing that equals production cost, i.e., complex price structures do not signiﬁcantly affect the results from ordinary Bertrand competition.}

}

Sebastian Abshoff, Andreas Cord Landwehr, Daniel Jung, Alexander Skopalik:

In Proceedings of the 10th International Conference on Web and Internet Economics (WINE). Springer International Publishing Switzerland, LNCS, vol. 8877, pp. 435-440

[Show Abstract]

**Multilevel Network Games**In Proceedings of the 10th International Conference on Web and Internet Economics (WINE). Springer International Publishing Switzerland, LNCS, vol. 8877, pp. 435-440

**(2014)**[Show Abstract]

We consider a multilevel network game, where nodes can improve

their communication costs by connecting to a high-speed network.

The n nodes are connected by a static network and each node can decide

individually to become a gateway to the high-speed network. The goal

of a node v is to minimize its private costs, i.e., the sum (SUM-game) or

maximum (MAX-game) of communication distances from v to all other

nodes plus a fixed price α > 0 if it decides to be a gateway. Between gateways

the communication distance is 0, and gateways also improve other

nodes’ distances by behaving as shortcuts. For the SUM-game, we show

that for α ≤ n − 1, the price of anarchy is Θ (n/

√

α) and in this range

equilibria always exist. In range α ∈ (n−1, n(n−1)) the price of anarchy

is Θ(

√

α), and for α ≥ n(n − 1) it is constant. For the MAX-game, we

show that the price of anarchy is either Θ (1 + n/

√

α), for α ≥ 1, or

else 1. Given a graph with girth of at least 4α, equilibria always exist.

Concerning the dynamics, both games are not potential games. For the

SUM-game, we even show that it is not weakly acyclic.

[Show BibTeX] their communication costs by connecting to a high-speed network.

The n nodes are connected by a static network and each node can decide

individually to become a gateway to the high-speed network. The goal

of a node v is to minimize its private costs, i.e., the sum (SUM-game) or

maximum (MAX-game) of communication distances from v to all other

nodes plus a fixed price α > 0 if it decides to be a gateway. Between gateways

the communication distance is 0, and gateways also improve other

nodes’ distances by behaving as shortcuts. For the SUM-game, we show

that for α ≤ n − 1, the price of anarchy is Θ (n/

√

α) and in this range

equilibria always exist. In range α ∈ (n−1, n(n−1)) the price of anarchy

is Θ(

√

α), and for α ≥ n(n − 1) it is constant. For the MAX-game, we

show that the price of anarchy is either Θ (1 + n/

√

α), for α ≥ 1, or

else 1. Given a graph with girth of at least 4α, equilibria always exist.

Concerning the dynamics, both games are not potential games. For the

SUM-game, we even show that it is not weakly acyclic.

@inproceedings{ACJS14,

author = {Sebastian Abshoff AND Andreas Cord Landwehr AND Daniel Jung AND Alexander Skopalik},

title = {Multilevel Network Games},

booktitle = {Proceedings of the 10th International Conference on Web and Internet Economics (WINE)},

year = {2014},

pages = {435-440},

publisher = {Springer International Publishing Switzerland},

abstract = {We consider a multilevel network game, where nodes can improvetheir communication costs by connecting to a high-speed network.The n nodes are connected by a static network and each node can decideindividually to become a gateway to the high-speed network. The goalof a node v is to minimize its private costs, i.e., the sum (SUM-game) ormaximum (MAX-game) of communication distances from v to all othernodes plus a fixed price α > 0 if it decides to be a gateway. Between gatewaysthe communication distance is 0, and gateways also improve othernodes’ distances by behaving as shortcuts. For the SUM-game, we showthat for α ≤ n − 1, the price of anarchy is Θ (n/√α) and in this rangeequilibria always exist. In range α ∈ (n−1, n(n−1)) the price of anarchyis Θ(√α), and for α ≥ n(n − 1) it is constant. For the MAX-game, weshow that the price of anarchy is either Θ (1 + n/√α), for α ≥ 1, orelse 1. Given a graph with girth of at least 4α, equilibria always exist.Concerning the dynamics, both games are not potential games. For theSUM-game, we even show that it is not weakly acyclic.},

series = {LNCS}

}

[DOI]
author = {Sebastian Abshoff AND Andreas Cord Landwehr AND Daniel Jung AND Alexander Skopalik},

title = {Multilevel Network Games},

booktitle = {Proceedings of the 10th International Conference on Web and Internet Economics (WINE)},

year = {2014},

pages = {435-440},

publisher = {Springer International Publishing Switzerland},

abstract = {We consider a multilevel network game, where nodes can improvetheir communication costs by connecting to a high-speed network.The n nodes are connected by a static network and each node can decideindividually to become a gateway to the high-speed network. The goalof a node v is to minimize its private costs, i.e., the sum (SUM-game) ormaximum (MAX-game) of communication distances from v to all othernodes plus a fixed price α > 0 if it decides to be a gateway. Between gatewaysthe communication distance is 0, and gateways also improve othernodes’ distances by behaving as shortcuts. For the SUM-game, we showthat for α ≤ n − 1, the price of anarchy is Θ (n/√α) and in this rangeequilibria always exist. In range α ∈ (n−1, n(n−1)) the price of anarchyis Θ(√α), and for α ≥ n(n − 1) it is constant. For the MAX-game, weshow that the price of anarchy is either Θ (1 + n/√α), for α ≥ 1, orelse 1. Given a graph with girth of at least 4α, equilibria always exist.Concerning the dynamics, both games are not potential games. For theSUM-game, we even show that it is not weakly acyclic.},

series = {LNCS}

}

Burkhard Monien, Marios Mavronicolas:

In

[Show Abstract]

**Minimizing Expectation Plus Variance**In

*Theory of Computing Systems*. Springer**(2014)**[Show Abstract]

We consider strategic games in which each player seeks a mixed strategy to minimize her cost evaluated by a concave valuation V (mapping probability distributions to reals); such valuations are used to model risk. In contrast to games with expectation-optimizer players where mixed equilibria always exist (Nash 1950; Nash Ann. Math. 54, 286–295, 1951), a mixed equilibrium for such games, called a V-equilibrium, may fail to exist, even though pure equilibria (if any) transfer over. What is the exact impact of such valuations on the existence, structure and complexity of mixed equilibria? We address this fundamental question in the context of expectation plus variance, a particular concave valuation denoted as RA, which stands for risk-averse; so, variance enters as a measure of risk and it is used as an additive adjustment to expectation. We obtain the following results about RA-equilibria:

A collection of general structural properties of RA-equilibria connecting to (i) E-equilibria and Var-equilibria, which correspond to the expectation and variance valuations E and Var, respectively, and to (ii) other weaker or incomparable properties such as Weak Equilibrium and Strong Equilibrium. Some of these structural properties imply quantitative constraints on the existence of mixed RA-equilibria.

A second collection of (i) existence, (ii) equivalence and separation (with respect to E-equilibria), and (iii) characterization results for RA-equilibria in the new class of player-specific scheduling games. We provide suitable examples with a mixed RA-equilibrium that is not an E-equilibrium and vice versa.

A purification technique to transform a player-specific scheduling game on two identical links into a player-specific scheduling game on two links so that all non-pure RA-equilibria are eliminated while no new pure equilibria are created; so, a particular player-specific scheduling game on two identical links with no pure equilibrium yields a player-specific scheduling game with no RA-equilibrium (whether mixed or pure). As a by-product, the first PLS-completeness result for the computation of RA-equilibria follows.

[Show BibTeX] A collection of general structural properties of RA-equilibria connecting to (i) E-equilibria and Var-equilibria, which correspond to the expectation and variance valuations E and Var, respectively, and to (ii) other weaker or incomparable properties such as Weak Equilibrium and Strong Equilibrium. Some of these structural properties imply quantitative constraints on the existence of mixed RA-equilibria.

A second collection of (i) existence, (ii) equivalence and separation (with respect to E-equilibria), and (iii) characterization results for RA-equilibria in the new class of player-specific scheduling games. We provide suitable examples with a mixed RA-equilibrium that is not an E-equilibrium and vice versa.

A purification technique to transform a player-specific scheduling game on two identical links into a player-specific scheduling game on two links so that all non-pure RA-equilibria are eliminated while no new pure equilibria are created; so, a particular player-specific scheduling game on two identical links with no pure equilibrium yields a player-specific scheduling game with no RA-equilibrium (whether mixed or pure). As a by-product, the first PLS-completeness result for the computation of RA-equilibria follows.

@article{MM2014,

author = {Burkhard Monien AND Marios Mavronicolas},

title = {Minimizing Expectation Plus Variance},

journal = {Theory of Computing Systems},

year = {2014},

abstract = {We consider strategic games in which each player seeks a mixed strategy to minimize her cost evaluated by a concave valuation V (mapping probability distributions to reals); such valuations are used to model risk. In contrast to games with expectation-optimizer players where mixed equilibria always exist (Nash 1950; Nash Ann. Math. 54, 286–295, 1951), a mixed equilibrium for such games, called a V-equilibrium, may fail to exist, even though pure equilibria (if any) transfer over. What is the exact impact of such valuations on the existence, structure and complexity of mixed equilibria? We address this fundamental question in the context of expectation plus variance, a particular concave valuation denoted as RA, which stands for risk-averse; so, variance enters as a measure of risk and it is used as an additive adjustment to expectation. We obtain the following results about RA-equilibria:A collection of general structural properties of RA-equilibria connecting to (i) E-equilibria and Var-equilibria, which correspond to the expectation and variance valuations E and Var, respectively, and to (ii) other weaker or incomparable properties such as Weak Equilibrium and Strong Equilibrium. Some of these structural properties imply quantitative constraints on the existence of mixed RA-equilibria.A second collection of (i) existence, (ii) equivalence and separation (with respect to E-equilibria), and (iii) characterization results for RA-equilibria in the new class of player-specific scheduling games. We provide suitable examples with a mixed RA-equilibrium that is not an E-equilibrium and vice versa.A purification technique to transform a player-specific scheduling game on two identical links into a player-specific scheduling game on two links so that all non-pure RA-equilibria are eliminated while no new pure equilibria are created; so, a particular player-specific scheduling game on two identical links with no pure equilibrium yields a player-specific scheduling game with no RA-equilibrium (whether mixed or pure). As a by-product, the first PLS-completeness result for the computation of RA-equilibria follows.}

}

[DOI]
author = {Burkhard Monien AND Marios Mavronicolas},

title = {Minimizing Expectation Plus Variance},

journal = {Theory of Computing Systems},

year = {2014},

abstract = {We consider strategic games in which each player seeks a mixed strategy to minimize her cost evaluated by a concave valuation V (mapping probability distributions to reals); such valuations are used to model risk. In contrast to games with expectation-optimizer players where mixed equilibria always exist (Nash 1950; Nash Ann. Math. 54, 286–295, 1951), a mixed equilibrium for such games, called a V-equilibrium, may fail to exist, even though pure equilibria (if any) transfer over. What is the exact impact of such valuations on the existence, structure and complexity of mixed equilibria? We address this fundamental question in the context of expectation plus variance, a particular concave valuation denoted as RA, which stands for risk-averse; so, variance enters as a measure of risk and it is used as an additive adjustment to expectation. We obtain the following results about RA-equilibria:A collection of general structural properties of RA-equilibria connecting to (i) E-equilibria and Var-equilibria, which correspond to the expectation and variance valuations E and Var, respectively, and to (ii) other weaker or incomparable properties such as Weak Equilibrium and Strong Equilibrium. Some of these structural properties imply quantitative constraints on the existence of mixed RA-equilibria.A second collection of (i) existence, (ii) equivalence and separation (with respect to E-equilibria), and (iii) characterization results for RA-equilibria in the new class of player-specific scheduling games. We provide suitable examples with a mixed RA-equilibrium that is not an E-equilibrium and vice versa.A purification technique to transform a player-specific scheduling game on two identical links into a player-specific scheduling game on two links so that all non-pure RA-equilibria are eliminated while no new pure equilibria are created; so, a particular player-specific scheduling game on two identical links with no pure equilibrium yields a player-specific scheduling game with no RA-equilibrium (whether mixed or pure). As a by-product, the first PLS-completeness result for the computation of RA-equilibria follows.}

}

Alexander Jungmann, Sonja Brangewitz, Ronald Petrlic, Marie Christin Platenius:

In

[Show Abstract]

**Incorporating Reputation Information into Decision-Making Processes in Markets of Composed Services**In

*International Journal On Advances in Intelligent Systems (IntSys)*, vol. 7, no. 3&4, pp. 572-594. ThinkMind**(2014)**[Show Abstract]

One goal of service-oriented computing is to realize future markets of composed services. In such markets, service providers offer services that can be ﬂexibly combined with each other. However, although crucial for decision-making, market participants are usually not able to individually estimate the quality of traded services in advance. To overcome this problem, we present a conceptual design for a reputation system that collects and processes user feedback on transactions, and provides this information as a signal for quality to participants in the market. Based on our proposed concept, we describe the incorporation of reputation information into distinct decision-making processes that are crucial in such service markets. In this context, we present a fuzzy service matching approach that takes reputation information into account. Furthermore, we introduce an adaptive service composition approach, and investigate the impact of exchanging immediate user feedback by reputation information. Last but not least, we describe the importance of reputation information for economic decisions of different market participants. The overall output of this paper is a comprehensive view on managing and exploiting reputation information in markets of composed services using the example of On-The-Fly Computing.

[Show BibTeX] @article{JBPP2014,

author = {Alexander Jungmann AND Sonja Brangewitz AND Ronald Petrlic AND Marie Christin Platenius},

title = {Incorporating Reputation Information into Decision-Making Processes in Markets of Composed Services},

journal = {International Journal On Advances in Intelligent Systems (IntSys)},

year = {2014},

volume = {7},

number = {3&4},

pages = {572--594},

abstract = {One goal of service-oriented computing is to realize future markets of composed services. In such markets, service providers offer services that can be ﬂexibly combined with each other. However, although crucial for decision-making, market participants are usually not able to individually estimate the quality of traded services in advance. To overcome this problem, we present a conceptual design for a reputation system that collects and processes user feedback on transactions, and provides this information as a signal for quality to participants in the market. Based on our proposed concept, we describe the incorporation of reputation information into distinct decision-making processes that are crucial in such service markets. In this context, we present a fuzzy service matching approach that takes reputation information into account. Furthermore, we introduce an adaptive service composition approach, and investigate the impact of exchanging immediate user feedback by reputation information. Last but not least, we describe the importance of reputation information for economic decisions of different market participants. The overall output of this paper is a comprehensive view on managing and exploiting reputation information in markets of composed services using the example of On-The-Fly Computing.}

}

[DOI]
author = {Alexander Jungmann AND Sonja Brangewitz AND Ronald Petrlic AND Marie Christin Platenius},

title = {Incorporating Reputation Information into Decision-Making Processes in Markets of Composed Services},

journal = {International Journal On Advances in Intelligent Systems (IntSys)},

year = {2014},

volume = {7},

number = {3&4},

pages = {572--594},

abstract = {One goal of service-oriented computing is to realize future markets of composed services. In such markets, service providers offer services that can be ﬂexibly combined with each other. However, although crucial for decision-making, market participants are usually not able to individually estimate the quality of traded services in advance. To overcome this problem, we present a conceptual design for a reputation system that collects and processes user feedback on transactions, and provides this information as a signal for quality to participants in the market. Based on our proposed concept, we describe the incorporation of reputation information into distinct decision-making processes that are crucial in such service markets. In this context, we present a fuzzy service matching approach that takes reputation information into account. Furthermore, we introduce an adaptive service composition approach, and investigate the impact of exchanging immediate user feedback by reputation information. Last but not least, we describe the importance of reputation information for economic decisions of different market participants. The overall output of this paper is a comprehensive view on managing and exploiting reputation information in markets of composed services using the example of On-The-Fly Computing.}

}

Ana Mauleon, Nils Roehl, Vincent Vannetelbosch:

Techreport UPB.

[Show Abstract]

**Constitutions and Social Networks**Techreport UPB.

**(2014)**[Show Abstract]

The objective of this paper is to analyze the formation of group structures where individuals are allowed to engage in several groups at the same time. These structures are interpreted here as social networks. Each of the groups is supposed to have specific rules or constitutions governing which members may join or leave it. A social network is then considered to be stable if none of the groups is altered any more. Given this framework, we not only analyze which influence the constitutions have on network formation but we also provide requirements under which stable networks are induced for sure. Furthermore, by embedding many-to-many matchings into our setting, we apply our model to job markets with labor unions. To some extent the unions may provide job guarantees and, therefore, have influence on the stability of the job market.

[Show BibTeX] @techreport{MRV2014,

author = {Ana Mauleon AND Nils Roehl AND Vincent Vannetelbosch},

title = {Constitutions and Social Networks},

year = {2014},

type = {Techreport UPB},

abstract = {The objective of this paper is to analyze the formation of group structures where individuals are allowed to engage in several groups at the same time. These structures are interpreted here as social networks. Each of the groups is supposed to have specific rules or constitutions governing which members may join or leave it. A social network is then considered to be stable if none of the groups is altered any more. Given this framework, we not only analyze which influence the constitutions have on network formation but we also provide requirements under which stable networks are induced for sure. Furthermore, by embedding many-to-many matchings into our setting, we apply our model to job markets with labor unions. To some extent the unions may provide job guarantees and, therefore, have influence on the stability of the job market.}

}

author = {Ana Mauleon AND Nils Roehl AND Vincent Vannetelbosch},

title = {Constitutions and Social Networks},

year = {2014},

type = {Techreport UPB},

abstract = {The objective of this paper is to analyze the formation of group structures where individuals are allowed to engage in several groups at the same time. These structures are interpreted here as social networks. Each of the groups is supposed to have specific rules or constitutions governing which members may join or leave it. A social network is then considered to be stable if none of the groups is altered any more. Given this framework, we not only analyze which influence the constitutions have on network formation but we also provide requirements under which stable networks are induced for sure. Furthermore, by embedding many-to-many matchings into our setting, we apply our model to job markets with labor unions. To some extent the unions may provide job guarantees and, therefore, have influence on the stability of the job market.}

}

Sonja Brangewitz, Jan-Philip Gamp:

In

[Show Abstract]

**Competitive outcomes and the inner core of NTU market games**In

*Economic Theory*, vol. 57, no. 3, pp. 529-554. Springer Berlin Heidelberg**(2014)**[Show Abstract]

We consider the inner core as a solution concept for cooperative games with non-transferable utility (NTU) and its relationship to payoffs of competitive equilibria of markets that are induced by NTU games. An NTU game is an NTU market game if there exists a market such that the set of utility allocations a coalition can achieve in the market coincides with the set of utility allocations the coalition can achieve in the game. In this paper, we introduce a new construction of a market based on a closed subset of the inner core which satisfies a strict positive separability. We show that the constructed market represents the NTU game and, further, has the given closed set as the set of payoff vectors of competitive equilibria. It turns out that this market is not uniquely determined, and thus, we obtain a class of markets. Our results generalize those relating to competitive outcomes of NTU market games in the literature.

[Show BibTeX] @article{SBJG14,

author = {Sonja Brangewitz AND Jan-Philip Gamp},

title = {Competitive outcomes and the inner core of NTU market games},

journal = {Economic Theory},

year = {2014},

volume = {57},

number = {3},

pages = {529-554},

abstract = {We consider the inner core as a solution concept for cooperative games with non-transferable utility (NTU) and its relationship to payoffs of competitive equilibria of markets that are induced by NTU games. An NTU game is an NTU market game if there exists a market such that the set of utility allocations a coalition can achieve in the market coincides with the set of utility allocations the coalition can achieve in the game. In this paper, we introduce a new construction of a market based on a closed subset of the inner core which satisfies a strict positive separability. We show that the constructed market represents the NTU game and, further, has the given closed set as the set of payoff vectors of competitive equilibria. It turns out that this market is not uniquely determined, and thus, we obtain a class of markets. Our results generalize those relating to competitive outcomes of NTU market games in the literature.}

}

[DOI]
author = {Sonja Brangewitz AND Jan-Philip Gamp},

title = {Competitive outcomes and the inner core of NTU market games},

journal = {Economic Theory},

year = {2014},

volume = {57},

number = {3},

pages = {529-554},

abstract = {We consider the inner core as a solution concept for cooperative games with non-transferable utility (NTU) and its relationship to payoffs of competitive equilibria of markets that are induced by NTU games. An NTU game is an NTU market game if there exists a market such that the set of utility allocations a coalition can achieve in the market coincides with the set of utility allocations the coalition can achieve in the game. In this paper, we introduce a new construction of a market based on a closed subset of the inner core which satisfies a strict positive separability. We show that the constructed market represents the NTU game and, further, has the given closed set as the set of payoff vectors of competitive equilibria. It turns out that this market is not uniquely determined, and thus, we obtain a class of markets. Our results generalize those relating to competitive outcomes of NTU market games in the literature.}

}

Maximilian Drees, Sören Riechers, Alexander Skopalik:

In Ron Lavi (eds.): Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT). Springer Berlin Heidelberg, Lecture Notes in Computer Science, vol. 8768, pp. 110-121

[Show Abstract]

**Budget-restricted utility games with ordered strategic decisions**In Ron Lavi (eds.): Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT). Springer Berlin Heidelberg, Lecture Notes in Computer Science, vol. 8768, pp. 110-121

**(2014)**[Show Abstract]

We introduce the concept of budget games. Players choose a set of tasks and each task has a certain demand on every resource in the game. Each resource has a budget. If the budget is not enough to satisfy the sum of all demands, it has to be shared between the tasks. We study strategic budget games, where the budget is shared proportionally. We also consider a variant in which the order of the strategic decisions influences the distribution of the budgets. The complexity of the optimal solution as well as existence, complexity and quality of equilibria are analysed. Finally, we show that the time an ordered budget game needs to convergence towards an equilibrium may be exponential.

[Show BibTeX] @inproceedings{DRS14,

author = {Maximilian Drees AND S{\"o}ren Riechers AND Alexander Skopalik},

title = {Budget-restricted utility games with ordered strategic decisions},

booktitle = {Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT)},

year = {2014},

editor = {Ron Lavi},

pages = {110-121},

publisher = {Springer Berlin Heidelberg},

abstract = {We introduce the concept of budget games. Players choose a set of tasks and each task has a certain demand on every resource in the game. Each resource has a budget. If the budget is not enough to satisfy the sum of all demands, it has to be shared between the tasks. We study strategic budget games, where the budget is shared proportionally. We also consider a variant in which the order of the strategic decisions influences the distribution of the budgets. The complexity of the optimal solution as well as existence, complexity and quality of equilibria are analysed. Finally, we show that the time an ordered budget game needs to convergence towards an equilibrium may be exponential.},

series = {Lecture Notes in Computer Science}

}

[DOI]
author = {Maximilian Drees AND S{\"o}ren Riechers AND Alexander Skopalik},

title = {Budget-restricted utility games with ordered strategic decisions},

booktitle = {Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT)},

year = {2014},

editor = {Ron Lavi},

pages = {110-121},

publisher = {Springer Berlin Heidelberg},

abstract = {We introduce the concept of budget games. Players choose a set of tasks and each task has a certain demand on every resource in the game. Each resource has a budget. If the budget is not enough to satisfy the sum of all demands, it has to be shared between the tasks. We study strategic budget games, where the budget is shared proportionally. We also consider a variant in which the order of the strategic decisions influences the distribution of the budgets. The complexity of the optimal solution as well as existence, complexity and quality of equilibria are analysed. Finally, we show that the time an ordered budget game needs to convergence towards an equilibrium may be exponential.},

series = {Lecture Notes in Computer Science}

}

Sebastian Abshoff, Andreas Cord Landwehr, Daniel Jung, Alexander Skopalik:

In Ron Lavi (eds.): Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT). Springer, LNCS, vol. 8768, pp. 294

[Show Abstract]

**Brief Announcement: A Model for Multilevel Network Games**In Ron Lavi (eds.): Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT). Springer, LNCS, vol. 8768, pp. 294

**(2014)**[Show Abstract]

Today's networks, like the Internet, do not consist of one but a mixture of several interconnected networks. Each has individual qualities and hence the performance of a network node results from the networks' interplay.

We introduce a new game theoretic model capturing the interplay between a high-speed backbone network and a low-speed general purpose network. In our model, n nodes are connected by a static network and each node can decide individually to become a gateway node. A gateway node pays a fixed price for its connection to the high-speed network, but can utilize the high-speed network to gain communication distance 0 to all other gateways. Communication distances in the low-speed network are given by the hop distances. The effective communication distance between any two nodes then is given by the shortest path, which is possibly improved by using gateways as shortcuts.

Every node v has the objective to minimize its communication costs, given by the sum (SUM-game) or maximum (MAX-game) of the effective communication distances from v to all other nodes plus a fixed price \alpha > 0, if it decides to be a gateway. For both games and different ranges of \alpha, we study the existence of equilibria, the price of anarchy, and convergence properties of best-response dynamics.

[Show BibTeX] We introduce a new game theoretic model capturing the interplay between a high-speed backbone network and a low-speed general purpose network. In our model, n nodes are connected by a static network and each node can decide individually to become a gateway node. A gateway node pays a fixed price for its connection to the high-speed network, but can utilize the high-speed network to gain communication distance 0 to all other gateways. Communication distances in the low-speed network are given by the hop distances. The effective communication distance between any two nodes then is given by the shortest path, which is possibly improved by using gateways as shortcuts.

Every node v has the objective to minimize its communication costs, given by the sum (SUM-game) or maximum (MAX-game) of the effective communication distances from v to all other nodes plus a fixed price \alpha > 0, if it decides to be a gateway. For both games and different ranges of \alpha, we study the existence of equilibria, the price of anarchy, and convergence properties of best-response dynamics.

@inproceedings{2014sagtmultilevel,

author = {Sebastian Abshoff AND Andreas Cord Landwehr AND Daniel Jung AND Alexander Skopalik},

title = {Brief Announcement: A Model for Multilevel Network Games},

booktitle = {Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT)},

year = {2014},

editor = {Ron Lavi},

pages = {294},

publisher = {Springer},

abstract = {Today's networks, like the Internet, do not consist of one but a mixture of several interconnected networks. Each has individual qualities and hence the performance of a network node results from the networks' interplay.We introduce a new game theoretic model capturing the interplay between a high-speed backbone network and a low-speed general purpose network. In our model, n nodes are connected by a static network and each node can decide individually to become a gateway node. A gateway node pays a fixed price for its connection to the high-speed network, but can utilize the high-speed network to gain communication distance 0 to all other gateways. Communication distances in the low-speed network are given by the hop distances. The effective communication distance between any two nodes then is given by the shortest path, which is possibly improved by using gateways as shortcuts.Every node v has the objective to minimize its communication costs, given by the sum (SUM-game) or maximum (MAX-game) of the effective communication distances from v to all other nodes plus a fixed price \alpha > 0, if it decides to be a gateway. For both games and different ranges of \alpha, we study the existence of equilibria, the price of anarchy, and convergence properties of best-response dynamics.},

series = {LNCS}

}

author = {Sebastian Abshoff AND Andreas Cord Landwehr AND Daniel Jung AND Alexander Skopalik},

title = {Brief Announcement: A Model for Multilevel Network Games},

booktitle = {Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT)},

year = {2014},

editor = {Ron Lavi},

pages = {294},

publisher = {Springer},

abstract = {Today's networks, like the Internet, do not consist of one but a mixture of several interconnected networks. Each has individual qualities and hence the performance of a network node results from the networks' interplay.We introduce a new game theoretic model capturing the interplay between a high-speed backbone network and a low-speed general purpose network. In our model, n nodes are connected by a static network and each node can decide individually to become a gateway node. A gateway node pays a fixed price for its connection to the high-speed network, but can utilize the high-speed network to gain communication distance 0 to all other gateways. Communication distances in the low-speed network are given by the hop distances. The effective communication distance between any two nodes then is given by the shortest path, which is possibly improved by using gateways as shortcuts.Every node v has the objective to minimize its communication costs, given by the sum (SUM-game) or maximum (MAX-game) of the effective communication distances from v to all other nodes plus a fixed price \alpha > 0, if it decides to be a gateway. For both games and different ranges of \alpha, we study the existence of equilibria, the price of anarchy, and convergence properties of best-response dynamics.},

series = {LNCS}

}

Matthias Feldotto, Martin Gairing, Alexander Skopalik:

In Proceedings of the 10th International Conference on Web and Internet Economics (WINE). Springer International Publishing Switzerland, LNCS, vol. 8877, pp. 30-43

[Show Abstract]

**Bounding the Potential Function in Congestion Games and Approximate Pure Nash Equilibria**In Proceedings of the 10th International Conference on Web and Internet Economics (WINE). Springer International Publishing Switzerland, LNCS, vol. 8877, pp. 30-43

**(2014)**[Show Abstract]

In this paper we study the potential function in congestion games. We consider both games with non-decreasing cost functions as well as games with non-increasing utility functions. We show that the value of the potential function $\Phi(\sf s)$ of any outcome $\sf s$ of a congestion game approximates the optimum potential value $\Phi(\sf s^*)$ by a factor $\Psi_\mathcalF$ which only depends on the set of cost/utility functions $\mathcalF$, and an additive term which is bounded by the sum of the total possible improvements of the players in the outcome $\sf s$. The significance of this result is twofold. On the one hand it provides \emphPrice-of-Anarchy-like results with respect to the potential function. On the other hand, we show that these approximations can be used to compute $(1+\varepsilon)\cdot\Psi_\mathcalF$-approximate pure Nash equilibria for congestion games with non-decreasing cost functions. For the special case of polynomial cost functions, this significantly improves the guarantees from Caragiannis et al. [FOCS 2011]. Moreover, our machinery provides the first guarantees for general latency functions.

[Show BibTeX] @inproceedings{FGS14,

author = {Matthias Feldotto AND Martin Gairing AND Alexander Skopalik},

title = {Bounding the Potential Function in Congestion Games and Approximate Pure Nash Equilibria},

booktitle = {Proceedings of the 10th International Conference on Web and Internet Economics (WINE)},

year = {2014},

pages = {30-43},

publisher = {Springer International Publishing Switzerland},

abstract = {In this paper we study the potential function in congestion games. We consider both games with non-decreasing cost functions as well as games with non-increasing utility functions. We show that the value of the potential function $\Phi(\sf s)$ of any outcome $\sf s$ of a congestion game approximates the optimum potential value $\Phi(\sf s^*)$ by a factor $\Psi_{\mathcal{F}}$ which only depends on the set of cost/utility functions $\mathcal{F}$, and an additive term which is bounded by the sum of the total possible improvements of the players in the outcome $\sf s$. The significance of this result is twofold. On the one hand it provides \emph{Price-of-Anarchy}-like results with respect to the potential function. On the other hand, we show that these approximations can be used to compute $(1+\varepsilon)\cdot\Psi_{\mathcal{F}}$-approximate pure Nash equilibria for congestion games with non-decreasing cost functions. For the special case of polynomial cost functions, this significantly improves the guarantees from Caragiannis et al. [FOCS 2011]. Moreover, our machinery provides the first guarantees for general latency functions.},

series = {LNCS}

}

[DOI]
author = {Matthias Feldotto AND Martin Gairing AND Alexander Skopalik},

title = {Bounding the Potential Function in Congestion Games and Approximate Pure Nash Equilibria},

booktitle = {Proceedings of the 10th International Conference on Web and Internet Economics (WINE)},

year = {2014},

pages = {30-43},

publisher = {Springer International Publishing Switzerland},

abstract = {In this paper we study the potential function in congestion games. We consider both games with non-decreasing cost functions as well as games with non-increasing utility functions. We show that the value of the potential function $\Phi(\sf s)$ of any outcome $\sf s$ of a congestion game approximates the optimum potential value $\Phi(\sf s^*)$ by a factor $\Psi_{\mathcal{F}}$ which only depends on the set of cost/utility functions $\mathcal{F}$, and an additive term which is bounded by the sum of the total possible improvements of the players in the outcome $\sf s$. The significance of this result is twofold. On the one hand it provides \emph{Price-of-Anarchy}-like results with respect to the potential function. On the other hand, we show that these approximations can be used to compute $(1+\varepsilon)\cdot\Psi_{\mathcal{F}}$-approximate pure Nash equilibria for congestion games with non-decreasing cost functions. For the special case of polynomial cost functions, this significantly improves the guarantees from Caragiannis et al. [FOCS 2011]. Moreover, our machinery provides the first guarantees for general latency functions.},

series = {LNCS}

}

Christoph Hansknecht, Max Klimm, Alexander Skopalik:

In Proceedings of the 17th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, LIPIcs, vol. 28, pp. 242 - 257

[Show Abstract]

**Approximate pure Nash equilibria in weighted congestion games**In Proceedings of the 17th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, LIPIcs, vol. 28, pp. 242 - 257

**(2014)**[Show Abstract]

We study the existence of approximate pure Nash equilibria in weighted congestion games and develop techniques to obtain approximate potential functions that prove the existence of alpha-approximate pure Nash equilibria and the convergence of alpha-improvement steps. Specifically, we show how to obtain upper bounds for approximation factor alpha for a given class of cost functions. For example for concave cost functions the factor is at most 3/2, for quadratic cost functions it is at most 4/3, and for polynomial cost functions of maximal degree d it is at at most d + 1. For games with two players we obtain tight bounds which are as small as for example 1.054 in the case of quadratic cost functions.

[Show BibTeX] @inproceedings{HKS14,

author = {Christoph Hansknecht AND Max Klimm AND Alexander Skopalik},

title = {Approximate pure Nash equilibria in weighted congestion games},

booktitle = {Proceedings of the 17th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)},

year = {2014},

pages = {242 - 257},

publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},

abstract = {We study the existence of approximate pure Nash equilibria in weighted congestion games and develop techniques to obtain approximate potential functions that prove the existence of alpha-approximate pure Nash equilibria and the convergence of alpha-improvement steps. Specifically, we show how to obtain upper bounds for approximation factor alpha for a given class of cost functions. For example for concave cost functions the factor is at most 3/2, for quadratic cost functions it is at most 4/3, and for polynomial cost functions of maximal degree d it is at at most d + 1. For games with two players we obtain tight bounds which are as small as for example 1.054 in the case of quadratic cost functions.},

series = {LIPIcs}

}

[DOI]
author = {Christoph Hansknecht AND Max Klimm AND Alexander Skopalik},

title = {Approximate pure Nash equilibria in weighted congestion games},

booktitle = {Proceedings of the 17th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)},

year = {2014},

pages = {242 - 257},

publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},

abstract = {We study the existence of approximate pure Nash equilibria in weighted congestion games and develop techniques to obtain approximate potential functions that prove the existence of alpha-approximate pure Nash equilibria and the convergence of alpha-improvement steps. Specifically, we show how to obtain upper bounds for approximation factor alpha for a given class of cost functions. For example for concave cost functions the factor is at most 3/2, for quadratic cost functions it is at most 4/3, and for polynomial cost functions of maximal degree d it is at at most d + 1. For games with two players we obtain tight bounds which are as small as for example 1.054 in the case of quadratic cost functions.},

series = {LIPIcs}

}

Martin Gairing, Grammateia Kotsialou, Alexander Skopalik:

In Proceedings of the 10th International Conference on Web and Internet Economics (WINE). Springer International Publishing Switzerland, LNCS, vol. 8877, pp. 480 - 485

[Show Abstract]

**Approximate pure Nash equilibria in Social Context Congestion Games**In Proceedings of the 10th International Conference on Web and Internet Economics (WINE). Springer International Publishing Switzerland, LNCS, vol. 8877, pp. 480 - 485

**(2014)**[Show Abstract]

We study the existence of approximate pure Nash equilibria

in social context congestion games. For any given set of allowed cost

functions F, we provide a threshold value μ(F), and show that for the

class of social context congestion games with cost functions from F, α-

Nash dynamics are guaranteed to converge to α-approximate pure Nash

equilibrium if and only if α > μ(F).

Interestingly, μ(F) is related and always upper bounded by Roughgarden’s

anarchy value [19].

[Show BibTeX] in social context congestion games. For any given set of allowed cost

functions F, we provide a threshold value μ(F), and show that for the

class of social context congestion games with cost functions from F, α-

Nash dynamics are guaranteed to converge to α-approximate pure Nash

equilibrium if and only if α > μ(F).

Interestingly, μ(F) is related and always upper bounded by Roughgarden’s

anarchy value [19].

@inproceedings{gks14,

author = {Martin Gairing AND Grammateia Kotsialou AND Alexander Skopalik},

title = {Approximate pure Nash equilibria in Social Context Congestion Games},

booktitle = {Proceedings of the 10th International Conference on Web and Internet Economics (WINE)},

year = {2014},

pages = {480 - 485},

publisher = {Springer International Publishing Switzerland},

abstract = {We study the existence of approximate pure Nash equilibriain social context congestion games. For any given set of allowed costfunctions F, we provide a threshold value μ(F), and show that for theclass of social context congestion games with cost functions from F, α-Nash dynamics are guaranteed to converge to α-approximate pure Nashequilibrium if and only if α > μ(F).Interestingly, μ(F) is related and always upper bounded by Roughgarden’sanarchy value [19].},

series = {LNCS}

}

[DOI]
author = {Martin Gairing AND Grammateia Kotsialou AND Alexander Skopalik},

title = {Approximate pure Nash equilibria in Social Context Congestion Games},

booktitle = {Proceedings of the 10th International Conference on Web and Internet Economics (WINE)},

year = {2014},

pages = {480 - 485},

publisher = {Springer International Publishing Switzerland},

abstract = {We study the existence of approximate pure Nash equilibriain social context congestion games. For any given set of allowed costfunctions F, we provide a threshold value μ(F), and show that for theclass of social context congestion games with cost functions from F, α-Nash dynamics are guaranteed to converge to α-approximate pure Nashequilibrium if and only if α > μ(F).Interestingly, μ(F) is related and always upper bounded by Roughgarden’sanarchy value [19].},

series = {LNCS}

}

Matthias Feldotto, Alexander Skopalik:

In Proceedings of the 4th International Conference on Simulation and Modeling Methodologies, Technologies and Applications (SIMULTECH 2014). SciTePress, pp. 625-630

[Show Abstract]

**A Simulation Framework for Analyzing Complex Infinitely Repeated Games**In Proceedings of the 4th International Conference on Simulation and Modeling Methodologies, Technologies and Applications (SIMULTECH 2014). SciTePress, pp. 625-630

**(2014)**[Show Abstract]

We discuss a technique to analyze complex infinitely repeated games using techniques from the fields of game theory and simulations. Our research is motivated by the analysis of electronic markets with thousands of participants and possibly complex strategic behavior. We consider an example of a global market of composed IT services to demonstrate the use of our simulation technique. We present our current work in this area and we want to discuss further approaches for the future.

[Show BibTeX] @inproceedings{FS2014SIMULTECH,

author = {Matthias Feldotto AND Alexander Skopalik},

title = {A Simulation Framework for Analyzing Complex Infinitely Repeated Games},

booktitle = {Proceedings of the 4th International Conference on Simulation and Modeling Methodologies, Technologies and Applications (SIMULTECH 2014)},

year = {2014},

pages = {625-630},

publisher = {SciTePress},

month = {August},

abstract = {We discuss a technique to analyze complex infinitely repeated games using techniques from the fields of game theory and simulations. Our research is motivated by the analysis of electronic markets with thousands of participants and possibly complex strategic behavior. We consider an example of a global market of composed IT services to demonstrate the use of our simulation technique. We present our current work in this area and we want to discuss further approaches for the future.}

}

[DOI]
author = {Matthias Feldotto AND Alexander Skopalik},

title = {A Simulation Framework for Analyzing Complex Infinitely Repeated Games},

booktitle = {Proceedings of the 4th International Conference on Simulation and Modeling Methodologies, Technologies and Applications (SIMULTECH 2014)},

year = {2014},

pages = {625-630},

publisher = {SciTePress},

month = {August},

abstract = {We discuss a technique to analyze complex infinitely repeated games using techniques from the fields of game theory and simulations. Our research is motivated by the analysis of electronic markets with thousands of participants and possibly complex strategic behavior. We consider an example of a global market of composed IT services to demonstrate the use of our simulation technique. We present our current work in this area and we want to discuss further approaches for the future.}

}

**2013** (6)

Nils Roehl:

Techreport UPB.

[Show Abstract]

**Two-Stage Allocation Procedures**Techreport UPB.

**(2013)**[Show Abstract]

Suppose some individuals are allowed to engage in different groups at the same time and they generate a certain welfare by cooperation. Finding appropriate ways for distributing this welfare is a non-trivial issue. The purpose of this work is to analyze two-stage allocation procedures where first each group receives a share of the welfare which is then, subsequently, distributed among the corresponding members. To study these procedures in a structured way, cooperative games and network games are combined in a general framework by using mathematical hypergraphs. Moreover, several convincing requirements on allocation procedures are discussed and formalized. Thereby it will be shown, for example, that the Position Value and iteratively applying the Myerson Value can be characterized by similar axiomatizations.

[Show BibTeX] @techreport{2StageRules13R,

author = {Nils Roehl},

title = {Two-Stage Allocation Procedures},

year = {2013},

type = {Techreport UPB},

abstract = {Suppose some individuals are allowed to engage in different groups at the same time and they generate a certain welfare by cooperation. Finding appropriate ways for distributing this welfare is a non-trivial issue. The purpose of this work is to analyze two-stage allocation procedures where first each group receives a share of the welfare which is then, subsequently, distributed among the corresponding members. To study these procedures in a structured way, cooperative games and network games are combined in a general framework by using mathematical hypergraphs. Moreover, several convincing requirements on allocation procedures are discussed and formalized. Thereby it will be shown, for example, that the Position Value and iteratively applying the Myerson Value can be characterized by similar axiomatizations.}

}

author = {Nils Roehl},

title = {Two-Stage Allocation Procedures},

year = {2013},

type = {Techreport UPB},

abstract = {Suppose some individuals are allowed to engage in different groups at the same time and they generate a certain welfare by cooperation. Finding appropriate ways for distributing this welfare is a non-trivial issue. The purpose of this work is to analyze two-stage allocation procedures where first each group receives a share of the welfare which is then, subsequently, distributed among the corresponding members. To study these procedures in a structured way, cooperative games and network games are combined in a general framework by using mathematical hypergraphs. Moreover, several convincing requirements on allocation procedures are discussed and formalized. Thereby it will be shown, for example, that the Position Value and iteratively applying the Myerson Value can be characterized by similar axiomatizations.}

}

Bernd Frick, Robert Simmons:

In

[Show Abstract]

**The Impact of Individual and Collective Reputation on Wine Prices: Empirical Evidence from the Mosel Valley**In

*Journal of Business Economics*, vol. 83, no. 2, pp. 101-119. Springer**(2013)**[Show Abstract]

Although of considerable practical importance, the separate impact of individual and collective reputation on firm performance (e.g. product prices) has not yet been convincingly demonstrated. We use a sample of some 70 different wineries offering more than 1,300 different Riesling wines from the Mosel valley to isolate the returns to individual reputation (measured by expert ratings in a highly respected wine guide) from the returns to collective reputation (measured by membership in two different professional associations where members are assumed to monitor each other very closely). We find that both effects are statistically significant and economically relevant with the latter being more important in quantitative terms than the former.

[Show BibTeX] @article{FS2012JoBE,

author = {Bernd Frick AND Robert Simmons},

title = {The Impact of Individual and Collective Reputation on Wine Prices: Empirical Evidence from the Mosel Valley},

journal = {Journal of Business Economics},

year = {2013},

volume = {83},

number = {2},

pages = {101-119},

abstract = {Although of considerable practical importance, the separate impact of individual and collective reputation on firm performance (e.g. product prices) has not yet been convincingly demonstrated. We use a sample of some 70 different wineries offering more than 1,300 different Riesling wines from the Mosel valley to isolate the returns to individual reputation (measured by expert ratings in a highly respected wine guide) from the returns to collective reputation (measured by membership in two different professional associations where members are assumed to monitor each other very closely). We find that both effects are statistically significant and economically relevant with the latter being more important in quantitative terms than the former.}

}

[DOI]
author = {Bernd Frick AND Robert Simmons},

title = {The Impact of Individual and Collective Reputation on Wine Prices: Empirical Evidence from the Mosel Valley},

journal = {Journal of Business Economics},

year = {2013},

volume = {83},

number = {2},

pages = {101-119},

abstract = {Although of considerable practical importance, the separate impact of individual and collective reputation on firm performance (e.g. product prices) has not yet been convincingly demonstrated. We use a sample of some 70 different wineries offering more than 1,300 different Riesling wines from the Mosel valley to isolate the returns to individual reputation (measured by expert ratings in a highly respected wine guide) from the returns to collective reputation (measured by membership in two different professional associations where members are assumed to monitor each other very closely). We find that both effects are statistically significant and economically relevant with the latter being more important in quantitative terms than the former.}

}

Berno Buechel, Nils Roehl:

Techreport UPB.

[Show Abstract]

**Robust Equilibria in Location Games**Techreport UPB.

**(2013)**[Show Abstract]

In the framework of spatial competition, two or more players strategically choose a location

in order to attract consumers. It is assumed standardly that consumers with the same favorite location fully agree on the ranking of all possible locations. To investigate the necessity of this questionable and restrictive assumption, we model heterogeneity in consumers’ distance perceptions by individual edge lengths of a given graph. A proﬁle of location choices is called a “robust equilibrium” if it is a Nash equilibrium in several games which diﬀer only by the consumers’ perceptions of distances. For a ﬁnite number of players and any distribution of consumers, we provide a full characterization of all robust equilibria and derive structural conditions for their existence. Furthermore, we discuss whether the classical observations of minimal diﬀerentiation and ineﬃciency are robust phenomena. Thereby, we ﬁnd strong support for an old conjecture that in equilibrium ﬁrms form local clusters.

[Show BibTeX] in order to attract consumers. It is assumed standardly that consumers with the same favorite location fully agree on the ranking of all possible locations. To investigate the necessity of this questionable and restrictive assumption, we model heterogeneity in consumers’ distance perceptions by individual edge lengths of a given graph. A proﬁle of location choices is called a “robust equilibrium” if it is a Nash equilibrium in several games which diﬀer only by the consumers’ perceptions of distances. For a ﬁnite number of players and any distribution of consumers, we provide a full characterization of all robust equilibria and derive structural conditions for their existence. Furthermore, we discuss whether the classical observations of minimal diﬀerentiation and ineﬃciency are robust phenomena. Thereby, we ﬁnd strong support for an old conjecture that in equilibrium ﬁrms form local clusters.

@techreport{Robust13BR,

author = {Berno Buechel AND Nils Roehl},

title = {Robust Equilibria in Location Games},

year = {2013},

type = {Techreport UPB},

abstract = {In the framework of spatial competition, two or more players strategically choose a locationin order to attract consumers. It is assumed standardly that consumers with the same favorite location fully agree on the ranking of all possible locations. To investigate the necessity of this questionable and restrictive assumption, we model heterogeneity in consumers’ distance perceptions by individual edge lengths of a given graph. A proﬁle of location choices is called a “robust equilibrium” if it is a Nash equilibrium in several games which diﬀer only by the consumers’ perceptions of distances. For a ﬁnite number of players and any distribution of consumers, we provide a full characterization of all robust equilibria and derive structural conditions for their existence. Furthermore, we discuss whether the classical observations of minimal diﬀerentiation and ineﬃciency are robust phenomena. Thereby, we ﬁnd strong support for an old conjecture that in equilibrium ﬁrms form local clusters.}

}

author = {Berno Buechel AND Nils Roehl},

title = {Robust Equilibria in Location Games},

year = {2013},

type = {Techreport UPB},

abstract = {In the framework of spatial competition, two or more players strategically choose a locationin order to attract consumers. It is assumed standardly that consumers with the same favorite location fully agree on the ranking of all possible locations. To investigate the necessity of this questionable and restrictive assumption, we model heterogeneity in consumers’ distance perceptions by individual edge lengths of a given graph. A proﬁle of location choices is called a “robust equilibrium” if it is a Nash equilibrium in several games which diﬀer only by the consumers’ perceptions of distances. For a ﬁnite number of players and any distribution of consumers, we provide a full characterization of all robust equilibria and derive structural conditions for their existence. Furthermore, we discuss whether the classical observations of minimal diﬀerentiation and ineﬃciency are robust phenomena. Thereby, we ﬁnd strong support for an old conjecture that in equilibrium ﬁrms form local clusters.}

}

Marios Mavronicolas, Burkhard Monien, Vicky Papadopoulou Lesta:

In

[Show Abstract]

**How many attackers can selfish defenders catch?**In

*Discrete Applied Mathematics*, vol. 161, pp. 2563-2586. Elsevier**(2013)**[Show Abstract]

In a distributed system with attacks and defenses, both attackers and defenders are self-interested entities. We assume a reward-sharing scheme among interdependent defenders; each defender wishes to (locally) maximize her own total fair share to the attackers extinguished due to her involvement (and possibly due to those of others). What is the maximum amount of protection achievable by a number of such defenders against a number of attackers while the system is in a Nash equilibrium? As a measure of system protection, we adopt the Defense-Ratio (Mavronicolas et al., 2008)[20], which provides the expected (inverse) proportion of attackers caught by the defenders. In a Defense-Optimal Nash equilibrium, the Defense-Ratio matches a simple lower bound.

We discover that the existence of Defense-Optimal Nash equilibria depends in a subtle way on how the number of defenders compares to two natural graph-theoretic thresholds we identify. In this vein, we obtain, through a combinatorial analysis of Nash equilibria, a collection of trade-off results:

• When the number of defenders is either sufficiently small or sufficiently large, Defense-Optimal Nash equilibria may exist. The corresponding decision problem is computationally tractable for a large number of defenders; the problem becomes NPNP-complete for a small number of defenders and the intractability is inherited from a previously unconsidered combinatorial problem in Fractional Graph Theory.

• Perhaps paradoxically, there is a middle range of values for the number of defenders where Defense-Optimal Nash equilibria do not exist.

[Show BibTeX] We discover that the existence of Defense-Optimal Nash equilibria depends in a subtle way on how the number of defenders compares to two natural graph-theoretic thresholds we identify. In this vein, we obtain, through a combinatorial analysis of Nash equilibria, a collection of trade-off results:

• When the number of defenders is either sufficiently small or sufficiently large, Defense-Optimal Nash equilibria may exist. The corresponding decision problem is computationally tractable for a large number of defenders; the problem becomes NPNP-complete for a small number of defenders and the intractability is inherited from a previously unconsidered combinatorial problem in Fractional Graph Theory.

• Perhaps paradoxically, there is a middle range of values for the number of defenders where Defense-Optimal Nash equilibria do not exist.

@article{MMP2013,

author = {Marios Mavronicolas AND Burkhard Monien AND Vicky Papadopoulou Lesta},

title = {How many attackers can selfish defenders catch?},

journal = {Discrete Applied Mathematics},

year = {2013},

volume = {161},

pages = {2563-2586},

abstract = {In a distributed system with attacks and defenses, both attackers and defenders are self-interested entities. We assume a reward-sharing scheme among interdependent defenders; each defender wishes to (locally) maximize her own total fair share to the attackers extinguished due to her involvement (and possibly due to those of others). What is the maximum amount of protection achievable by a number of such defenders against a number of attackers while the system is in a Nash equilibrium? As a measure of system protection, we adopt the Defense-Ratio (Mavronicolas et al., 2008)[20], which provides the expected (inverse) proportion of attackers caught by the defenders. In a Defense-Optimal Nash equilibrium, the Defense-Ratio matches a simple lower bound.We discover that the existence of Defense-Optimal Nash equilibria depends in a subtle way on how the number of defenders compares to two natural graph-theoretic thresholds we identify. In this vein, we obtain, through a combinatorial analysis of Nash equilibria, a collection of trade-off results:• When the number of defenders is either sufficiently small or sufficiently large, Defense-Optimal Nash equilibria may exist. The corresponding decision problem is computationally tractable for a large number of defenders; the problem becomes NPNP-complete for a small number of defenders and the intractability is inherited from a previously unconsidered combinatorial problem in Fractional Graph Theory.• Perhaps paradoxically, there is a middle range of values for the number of defenders where Defense-Optimal Nash equilibria do not exist.}

}

[DOI]
author = {Marios Mavronicolas AND Burkhard Monien AND Vicky Papadopoulou Lesta},

title = {How many attackers can selfish defenders catch?},

journal = {Discrete Applied Mathematics},

year = {2013},

volume = {161},

pages = {2563-2586},

abstract = {In a distributed system with attacks and defenses, both attackers and defenders are self-interested entities. We assume a reward-sharing scheme among interdependent defenders; each defender wishes to (locally) maximize her own total fair share to the attackers extinguished due to her involvement (and possibly due to those of others). What is the maximum amount of protection achievable by a number of such defenders against a number of attackers while the system is in a Nash equilibrium? As a measure of system protection, we adopt the Defense-Ratio (Mavronicolas et al., 2008)[20], which provides the expected (inverse) proportion of attackers caught by the defenders. In a Defense-Optimal Nash equilibrium, the Defense-Ratio matches a simple lower bound.We discover that the existence of Defense-Optimal Nash equilibria depends in a subtle way on how the number of defenders compares to two natural graph-theoretic thresholds we identify. In this vein, we obtain, through a combinatorial analysis of Nash equilibria, a collection of trade-off results:• When the number of defenders is either sufficiently small or sufficiently large, Defense-Optimal Nash equilibria may exist. The corresponding decision problem is computationally tractable for a large number of defenders; the problem becomes NPNP-complete for a small number of defenders and the intractability is inherited from a previously unconsidered combinatorial problem in Fractional Graph Theory.• Perhaps paradoxically, there is a middle range of values for the number of defenders where Defense-Optimal Nash equilibria do not exist.}

}

Sonja Brangewitz, Claus-Jochen Haake:

Techreport UPB.

[Show Abstract]

**Cooperative Transfer Price Negotiations under Incomplete Information**Techreport UPB.

**(2013)**[Show Abstract]

In this paper, we analyze a model in which two divisions negotiate over an intrarm transfer price for an intermediate product. Formally, we consider bargaining problems under incomplete information, since the upstream division's (seller's) costs and downstream division's (buyer's) revenues are supposed to be private information. Assuming two possible types for buyer and seller each, we rst establish that the bargaining problem is regular, regardless whether incentive and/or eciency constraints are imposed. This allows us to apply the generalized Nash bargaining solution to determine transfer payments and transfer probabilities. Furthermore, we derive general properties of this solution for the transfer pricing problem and compare the model developed here with the existing literature for negotiated transfer pricing under incomplete information. In particular, we focus on the models presented in Wagenhofer (1994).

[Show BibTeX] @techreport{BG12BG,

author = {Sonja Brangewitz AND Claus-Jochen Haake},

title = {Cooperative Transfer Price Negotiations under Incomplete Information},

year = {2013},

type = {Techreport UPB},

abstract = {In this paper, we analyze a model in which two divisions negotiate over an intrarm transfer price for an intermediate product. Formally, we consider bargaining problems under incomplete information, since the upstream division's (seller's) costs and downstream division's (buyer's) revenues are supposed to be private information. Assuming two possible types for buyer and seller each, we rst establish that the bargaining problem is regular, regardless whether incentive and/or eciency constraints are imposed. This allows us to apply the generalized Nash bargaining solution to determine transfer payments and transfer probabilities. Furthermore, we derive general properties of this solution for the transfer pricing problem and compare the model developed here with the existing literature for negotiated transfer pricing under incomplete information. In particular, we focus on the models presented in Wagenhofer (1994).}

}

author = {Sonja Brangewitz AND Claus-Jochen Haake},

title = {Cooperative Transfer Price Negotiations under Incomplete Information},

year = {2013},

type = {Techreport UPB},

abstract = {In this paper, we analyze a model in which two divisions negotiate over an intrarm transfer price for an intermediate product. Formally, we consider bargaining problems under incomplete information, since the upstream division's (seller's) costs and downstream division's (buyer's) revenues are supposed to be private information. Assuming two possible types for buyer and seller each, we rst establish that the bargaining problem is regular, regardless whether incentive and/or eciency constraints are imposed. This allows us to apply the generalized Nash bargaining solution to determine transfer payments and transfer probabilities. Furthermore, we derive general properties of this solution for the transfer pricing problem and compare the model developed here with the existing literature for negotiated transfer pricing under incomplete information. In particular, we focus on the models presented in Wagenhofer (1994).}

}

Sonja Brangewitz, Jan-Philip Gamp:

In

[Show Abstract]

**Asymmetric Nash bargaining solutions and competitive payoffs**In

*Economics Letters*, vol. 121, no. 2, pp. 224 - 227. Elsevier**(2013)**[Show Abstract]

We establish a link between cooperative and competitive behavior. For every possible vector of weights of an asymmetric Nash bargaining solution there exists a market that has this asymmetric Nash bargaining solution as its unique competitive payoff vector.

[Show BibTeX] @article{SBJG13,

author = {Sonja Brangewitz AND Jan-Philip Gamp},

title = {Asymmetric Nash bargaining solutions and competitive payoffs},

journal = {Economics Letters},

year = {2013},

volume = {121},

number = {2},

pages = {224 - 227},

abstract = {We establish a link between cooperative and competitive behavior. For every possible vector of weights of an asymmetric Nash bargaining solution there exists a market that has this asymmetric Nash bargaining solution as its unique competitive payoff vector.}

}

[DOI]
author = {Sonja Brangewitz AND Jan-Philip Gamp},

title = {Asymmetric Nash bargaining solutions and competitive payoffs},

journal = {Economics Letters},

year = {2013},

volume = {121},

number = {2},

pages = {224 - 227},

abstract = {We establish a link between cooperative and competitive behavior. For every possible vector of weights of an asymmetric Nash bargaining solution there exists a market that has this asymmetric Nash bargaining solution as its unique competitive payoff vector.}

}

**2012** (3)

Sonja Brangewitz, Sarah Brockhoff:

Techreport UPB.

[Show Abstract]

**Stability of Coalitional Equilibria within Repeated Tax Competition**Techreport UPB.

**(2012)**[Show Abstract]

This paper analyzes the stability of capital tax harmonization agreements in a stylized model where countries have formed coalitions which set a common tax rate in order to avoid the inefficient fully non-cooperative Nash equilibrium. In particular, for a given coalition structure we study to what extend the stability of tax agreements is affected by the coalitions that have formed. In our set-up, countries are symmetric, but coalitions can be of arbitrary size. We analyze stability by means of a repeated game setting employing simple trigger strategies and we allow a sub-coalition to deviate from the coalitional equilibrium. For a given form of punishment we are able to rank the stability of different coalition structures as long as the size of the largest coalition does not change. Our main results are: (1) singleton regions have the largest incentives to deviate, (2) the stability of cooperation depends on the degree of cooperative behavior ex-ante.

[Show BibTeX] @techreport{BR12BB,

author = {Sonja Brangewitz AND Sarah Brockhoff},

title = {Stability of Coalitional Equilibria within Repeated Tax Competition},

year = {2012},

type = {Techreport UPB},

abstract = {This paper analyzes the stability of capital tax harmonization agreements in a stylized model where countries have formed coalitions which set a common tax rate in order to avoid the inefficient fully non-cooperative Nash equilibrium. In particular, for a given coalition structure we study to what extend the stability of tax agreements is affected by the coalitions that have formed. In our set-up, countries are symmetric, but coalitions can be of arbitrary size. We analyze stability by means of a repeated game setting employing simple trigger strategies and we allow a sub-coalition to deviate from the coalitional equilibrium. For a given form of punishment we are able to rank the stability of different coalition structures as long as the size of the largest coalition does not change. Our main results are: (1) singleton regions have the largest incentives to deviate, (2) the stability of cooperation depends on the degree of cooperative behavior ex-ante.}

}

author = {Sonja Brangewitz AND Sarah Brockhoff},

title = {Stability of Coalitional Equilibria within Repeated Tax Competition},

year = {2012},

type = {Techreport UPB},

abstract = {This paper analyzes the stability of capital tax harmonization agreements in a stylized model where countries have formed coalitions which set a common tax rate in order to avoid the inefficient fully non-cooperative Nash equilibrium. In particular, for a given coalition structure we study to what extend the stability of tax agreements is affected by the coalitions that have formed. In our set-up, countries are symmetric, but coalitions can be of arbitrary size. We analyze stability by means of a repeated game setting employing simple trigger strategies and we allow a sub-coalition to deviate from the coalitional equilibrium. For a given form of punishment we are able to rank the stability of different coalition structures as long as the size of the largest coalition does not change. Our main results are: (1) singleton regions have the largest incentives to deviate, (2) the stability of cooperation depends on the degree of cooperative behavior ex-ante.}

}

Marios Mavronicolas, Burkhard Monien:

In Proceedings of the 5th International Symposium on Algorithmic Game Theory (SAGT). Springer, LNCS, vol. 7615, pp. 239-250

[Show Abstract]

**Minimizing Expectation Plus Variance**In Proceedings of the 5th International Symposium on Algorithmic Game Theory (SAGT). Springer, LNCS, vol. 7615, pp. 239-250

**(2012)**[Show Abstract]

We consider strategic games in which each player seeks a mixed strategy to minimize her cost evaluated by a concave valuation V (mapping probability distributions to reals); such valuations are used to model risk. In contrast to games with expectation-optimizer players where mixed equilibria always exist [15, 16], a mixed equilibrium for such games, called a V -equilibrium, may fail to exist, even though pure equilibria (if any) transfer over. What is the impact of such valuations on the existence, structure and complexity of mixed equilibria? We address this fundamental question for a particular concave valuation: expectation plus variance, denoted as RA, which stands for risk-averse; so, variance enters as a measure of risk and it is used as an additive adjustment to expectation. We obtain the following results about RA-equilibria:

- A collection of general structural properties of RA-equilibria connecting to (i) E-equilibria and Var-equilibria, which correspond to the expectation and variance valuations E and Var, respectively, and to (ii) other weaker or incomparable equilibrium properties.

- A second collection of (i) existence, (ii) equivalence and separation (with respect to E-equilibria), and (iii) characterization results for RA-equilibria in the new class of player-specific scheduling games. Using examples, we provide the first demonstration that going from E to RA may as well create new mixed (RA-)equilibria.

- A purification technique to transform a player-specific scheduling game on identical links into a player-specific scheduling game so that all non-pure RA-equilibria are eliminated while new pure equilibria cannot be created; so, a particular game on two identical links yields one with no RA-equilibrium. As a by-product, the first-completeness result for the computation of RA-equilibria follows.

[Show BibTeX] - A collection of general structural properties of RA-equilibria connecting to (i) E-equilibria and Var-equilibria, which correspond to the expectation and variance valuations E and Var, respectively, and to (ii) other weaker or incomparable equilibrium properties.

- A second collection of (i) existence, (ii) equivalence and separation (with respect to E-equilibria), and (iii) characterization results for RA-equilibria in the new class of player-specific scheduling games. Using examples, we provide the first demonstration that going from E to RA may as well create new mixed (RA-)equilibria.

- A purification technique to transform a player-specific scheduling game on identical links into a player-specific scheduling game so that all non-pure RA-equilibria are eliminated while new pure equilibria cannot be created; so, a particular game on two identical links yields one with no RA-equilibrium. As a by-product, the first-completeness result for the computation of RA-equilibria follows.

@inproceedings{MMBM-SAGT12,

author = {Marios Mavronicolas AND Burkhard Monien},

title = {Minimizing Expectation Plus Variance},

booktitle = {Proceedings of the 5th International Symposium on Algorithmic Game Theory (SAGT)},

year = {2012},

pages = {239-250},

publisher = {Springer},

abstract = {We consider strategic games in which each player seeks a mixed strategy to minimize her cost evaluated by a concave valuation V (mapping probability distributions to reals); such valuations are used to model risk. In contrast to games with expectation-optimizer players where mixed equilibria always exist [15, 16], a mixed equilibrium for such games, called a V -equilibrium, may fail to exist, even though pure equilibria (if any) transfer over. What is the impact of such valuations on the existence, structure and complexity of mixed equilibria? We address this fundamental question for a particular concave valuation: expectation plus variance, denoted as RA, which stands for risk-averse; so, variance enters as a measure of risk and it is used as an additive adjustment to expectation. We obtain the following results about RA-equilibria:- A collection of general structural properties of RA-equilibria connecting to (i) E-equilibria and Var-equilibria, which correspond to the expectation and variance valuations E and Var, respectively, and to (ii) other weaker or incomparable equilibrium properties.- A second collection of (i) existence, (ii) equivalence and separation (with respect to E-equilibria), and (iii) characterization results for RA-equilibria in the new class of player-specific scheduling games. Using examples, we provide the first demonstration that going from E to RA may as well create new mixed (RA-)equilibria.- A purification technique to transform a player-specific scheduling game on identical links into a player-specific scheduling game so that all non-pure RA-equilibria are eliminated while new pure equilibria cannot be created; so, a particular game on two identical links yields one with no RA-equilibrium. As a by-product, the first-completeness result for the computation of RA-equilibria follows.},

series = {LNCS}

}

[DOI]
author = {Marios Mavronicolas AND Burkhard Monien},

title = {Minimizing Expectation Plus Variance},

booktitle = {Proceedings of the 5th International Symposium on Algorithmic Game Theory (SAGT)},

year = {2012},

pages = {239-250},

publisher = {Springer},

abstract = {We consider strategic games in which each player seeks a mixed strategy to minimize her cost evaluated by a concave valuation V (mapping probability distributions to reals); such valuations are used to model risk. In contrast to games with expectation-optimizer players where mixed equilibria always exist [15, 16], a mixed equilibrium for such games, called a V -equilibrium, may fail to exist, even though pure equilibria (if any) transfer over. What is the impact of such valuations on the existence, structure and complexity of mixed equilibria? We address this fundamental question for a particular concave valuation: expectation plus variance, denoted as RA, which stands for risk-averse; so, variance enters as a measure of risk and it is used as an additive adjustment to expectation. We obtain the following results about RA-equilibria:- A collection of general structural properties of RA-equilibria connecting to (i) E-equilibria and Var-equilibria, which correspond to the expectation and variance valuations E and Var, respectively, and to (ii) other weaker or incomparable equilibrium properties.- A second collection of (i) existence, (ii) equivalence and separation (with respect to E-equilibria), and (iii) characterization results for RA-equilibria in the new class of player-specific scheduling games. Using examples, we provide the first demonstration that going from E to RA may as well create new mixed (RA-)equilibria.- A purification technique to transform a player-specific scheduling game on identical links into a player-specific scheduling game so that all non-pure RA-equilibria are eliminated while new pure equilibria cannot be created; so, a particular game on two identical links yields one with no RA-equilibrium. As a by-product, the first-completeness result for the computation of RA-equilibria follows.},

series = {LNCS}

}

Sonja Brangewitz, Gael Giraud:

Techreport UPB.

[Show Abstract]

**Learning by Trading in Infinite Horizon Strategic Market Games with Default**Techreport UPB.

**(2012)**[Show Abstract]

We study the consequences of dropping the perfect competition assumption in a standard infinite horizon model with infinitely-lived traders and real collateralized assets, together with one additional ingredient: information among players is asymmetric and monitoring is incomplete. The key insight is that trading assets is not only a way to hedge oneself against uncertainty and to smooth consumption across time: It also enables learning information. Conversely, defaulting now becomes strategic: Certain players may manipulate prices so as to provoke a default in order to prevent their opponents from learning. We focus on learning equilibria, at the end of which no player has incorrect beliefs — not because those players with heterogeneous beliefs were eliminated from the market (although default is possible at equilibrium) but because they have taken time to update their prior belief. We prove a partial Folk theorem à la Wiseman (2011) of the following form: For any function that maps each state of the world to a sequence of feasible and strongly individually rational allocations, and for any degree of precision, there is a perfect Bayesian equilibrium in which patient players learn the realized state with this degree of precision and achieve a payoff close to the one specified for each state.

[Show BibTeX] @techreport{BG12BG,

author = {Sonja Brangewitz AND Gael Giraud},

title = {Learning by Trading in Infinite Horizon Strategic Market Games with Default},

year = {2012},

type = {Techreport UPB},

abstract = {We study the consequences of dropping the perfect competition assumption in a standard infinite horizon model with infinitely-lived traders and real collateralized assets, together with one additional ingredient: information among players is asymmetric and monitoring is incomplete. The key insight is that trading assets is not only a way to hedge oneself against uncertainty and to smooth consumption across time: It also enables learning information. Conversely, defaulting now becomes strategic: Certain players may manipulate prices so as to provoke a default in order to prevent their opponents from learning. We focus on learning equilibria, at the end of which no player has incorrect beliefs — not because those players with heterogeneous beliefs were eliminated from the market (although default is possible at equilibrium) but because they have taken time to update their prior belief. We prove a partial Folk theorem à la Wiseman (2011) of the following form: For any function that maps each state of the world to a sequence of feasible and strongly individually rational allocations, and for any degree of precision, there is a perfect Bayesian equilibrium in which patient players learn the realized state with this degree of precision and achieve a payoff close to the one specified for each state.}

}

author = {Sonja Brangewitz AND Gael Giraud},

title = {Learning by Trading in Infinite Horizon Strategic Market Games with Default},

year = {2012},

type = {Techreport UPB},

abstract = {We study the consequences of dropping the perfect competition assumption in a standard infinite horizon model with infinitely-lived traders and real collateralized assets, together with one additional ingredient: information among players is asymmetric and monitoring is incomplete. The key insight is that trading assets is not only a way to hedge oneself against uncertainty and to smooth consumption across time: It also enables learning information. Conversely, defaulting now becomes strategic: Certain players may manipulate prices so as to provoke a default in order to prevent their opponents from learning. We focus on learning equilibria, at the end of which no player has incorrect beliefs — not because those players with heterogeneous beliefs were eliminated from the market (although default is possible at equilibrium) but because they have taken time to update their prior belief. We prove a partial Folk theorem à la Wiseman (2011) of the following form: For any function that maps each state of the world to a sequence of feasible and strongly individually rational allocations, and for any degree of precision, there is a perfect Bayesian equilibrium in which patient players learn the realized state with this degree of precision and achieve a payoff close to the one specified for each state.}

}

**2011** (1)

Daniel Kaimann:

Techreport UPB.

[Show Abstract]

**"To infinity and beyond!" - A genre-specific film analysis of movie success mechanisms**Techreport UPB.

**(2011)**[Show Abstract]

The objective of this study is the analysis of movie success mechanisms in a genre-specific context. Instead of the examination of all time box office champions, we focus on the two film genres of computer animated and comic book based films. By introducing the concept of the motion-picture marketing mix, which represents a set of tactical marketing tools in order to strengthen a company’s strategic customer orientation, we are able to systematically identify key movie success factors. We conduct a cross-sectional empirical analysis across regional distinctions based on dataset that covers a time horizon of more than 30 years. We find empirical evidence that actors with ex ante popularity, award nominations and the production budget represent key movie success mechanisms and significantly influence a movie’s commercial appeal. Additionally, word-of-mouth creates reputation effects that also significantly affects box office gross.

[Show BibTeX] @techreport{DK11,

author = {Daniel Kaimann},

title = {"To infinity and beyond!" - A genre-specific film analysis of movie success mechanisms},

year = {2011},

type = {Techreport UPB},

abstract = {The objective of this study is the analysis of movie success mechanisms in a genre-specific context. Instead of the examination of all time box office champions, we focus on the two film genres of computer animated and comic book based films. By introducing the concept of the motion-picture marketing mix, which represents a set of tactical marketing tools in order to strengthen a company’s strategic customer orientation, we are able to systematically identify key movie success factors. We conduct a cross-sectional empirical analysis across regional distinctions based on dataset that covers a time horizon of more than 30 years. We find empirical evidence that actors with ex ante popularity, award nominations and the production budget represent key movie success mechanisms and significantly influence a movie’s commercial appeal. Additionally, word-of-mouth creates reputation effects that also significantly affects box office gross.}

}

author = {Daniel Kaimann},

title = {"To infinity and beyond!" - A genre-specific film analysis of movie success mechanisms},

year = {2011},

type = {Techreport UPB},

abstract = {The objective of this study is the analysis of movie success mechanisms in a genre-specific context. Instead of the examination of all time box office champions, we focus on the two film genres of computer animated and comic book based films. By introducing the concept of the motion-picture marketing mix, which represents a set of tactical marketing tools in order to strengthen a company’s strategic customer orientation, we are able to systematically identify key movie success factors. We conduct a cross-sectional empirical analysis across regional distinctions based on dataset that covers a time horizon of more than 30 years. We find empirical evidence that actors with ex ante popularity, award nominations and the production budget represent key movie success mechanisms and significantly influence a movie’s commercial appeal. Additionally, word-of-mouth creates reputation effects that also significantly affects box office gross.}

}