Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Potluck Problem
117
0
0.0
(
0
)
Added by
Shrisha Rao
Publication date
2009
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
This paper proposes the Potluck Problem as a model for the behavior of independent producers and consumers under standard economic assumptions, as a problem of resource allocation in a multi-agent system in which there is no explicit communication among the agents.
rate research
Read More
We study secretary problems in settings with multiple agents. In the standard secretary problem, a sequence of arbitrary awards arrive online, in a random order, and a single decision maker makes an immediate and irrevocable decision whether to accept each award upon its arrival. The requirement to make immediate decisions arises in many cases due to an implicit assumption regarding competition. Namely, if the decision maker does not take the offered award immediately, it will be taken by someone else. The novelty in this paper is in introducing a multi-agent model in which the competition is endogenous. In our model, multiple agents compete over the arriving awards, but the decisions need not be immediate; instead, agents may select previous awards as long as they are available (i.e., not taken by another agent). If an award is selected by multiple agents, ties are broken either randomly or according to a global ranking. This induces a multi-agent game in which the time of selection is not enforced by the rules of the games, rather it is an important component of the agents strategy. We study the structure and performance of equilibria in this game. For random tie breaking, we characterize the equilibria of the game, and show that the expected social welfare in equilibrium is nearly optimal, despite competition among the agents. For ranked tie breaking, we give a full characterization of equilibria in the 3-agent game, and show that as the number of agents grows, the winning probability of every agent under non-immediate selections approaches her winning probability under immediate selections.
We investigate two systems of fully proportional representation suggested by Chamberlin Courant and Monroe. Both systems assign a representative to each voter so that the sum of misrepresentations is minimized. The winner determination problem for both systems is known to be NP-hard, hence this work aims at investigating whether there are variants of the proposed rules and/or specific electorates for which these problems can be solved efficiently. As a variation of these rules, instead of minimizing the sum of misrepresentations, we considered minimizing the maximal misrepresentation introducing effectively two new rules. In the general case these minimax
In this paper, we introduce a game that allows one to assess the potential loss of efficiency induced by a decentralized control or local management of a global epidemic. Each player typically represents a region or a country which is assumed to choose its control action to implement a tradeoff between socioeconomic aspects and the health aspect. We conduct the Nash equilibrium analysis of this game. Since the analysis is not trivial in general, sufficient conditions for existence and uniqueness are provided. Then we quantify through numerical results the loss induced by decentralization, measured in terms of price of anarchy (PoA) and price of connectedness (PoC). These results allow one to clearly identify scenarios where decentralization is acceptable or not regarding to the retained global efficiency measures.
In an adversarial environment, a hostile player performing a task may behave like a non-hostile one in order not to reveal its identity to an opponent. To model such a scenario, we define identity concealment games: zero-sum stochastic reachability games with a zero-sum objective of identity concealment. To measure the identity concealment of the player, we introduce the notion of an average player. The average players policy represents the expected behavior of a non-hostile player. We show that there exists an equilibrium policy pair for every identity concealment game and give the optimality equations to synthesize an equilibrium policy pair. If the players opponent follows a non-equilibrium policy, the player can hide its identity better. For this reason, we study how the hostile player may learn the opponents policy. Since learning via exploration policies would quickly reveal the hostile players identity to the opponent, we consider the problem of learning a near-optimal policy for the hostile player using the game runs collected under the average players policy. Consequently, we propose an algorithm that provably learns a near-optimal policy and give an upper bound on the number of sample runs to be collected.
The Ad Types Problem (without gap rules) is a special case of the assignment problem in which there are $k$ types of nodes on one side (the ads), and an ordered set of nodes on the other side (the slots). The edge weight of an ad $i$ of type $theta$ to slot $j$ is $v_icdot alpha^{theta}_j$ where $v_i$ is an advertiser-specific value and each ad type $theta$ has a discount curve $alpha^{(theta)}_{1} ge alpha^{(theta)}_{2} ge ... ge 0$ over the slots that is common for ads of type $theta$. We present two contributions for this problem: 1) we give an algorithm that finds the maximum weight matching that runs in $O(n^2(k + log n))$ time for $n$ slots and $n$ ads of each type---cf. $O(kn^3)$ when using the Hungarian algorithm---, and 2) we show to do VCG pricing in asymptotically the same time, namely $O(n^2(k + log n))$, and apply reserve prices in $O(n^3(k + log n))$. The Ad Types Problem (with gap rules) includes a matrix $G$ such that after we show an ad of type $theta_i$, the next $G_{ij}$ slots cannot show an ad of type $theta_j$. We show that the problem is hard to approximate within $k^{1- epsilon}$ for any $epsilon > 0$ (even without discount curves) by reduction from Maximum Independent Set. On the positive side, we show a Dynamic Program formulation that solves the problem (including discount curves) optimally and runs in $O(kcdot n^{2k + 1})$ time.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
