Multi Agent Fixed Cost Transportation Game

Problema

O problema do Fixed Cost Transportation consiste em um grafo bipartido no qual deseja-se transmitir um conjunto de produtos de um mesmo tipo através das arestas, de forma a minimizar o custo e atender a demanda. O custo é definido pelo preço variável cobrado por produto transportado somado ao custo fixo pago por usar determinada aresta. A formulação matemática é dada por:

fctp_img2

Onde: $x_{ij}$ – fluxo, $c_{ij}$ – custo variável, $F_{ij}$ – custo fixo (atualizar)

Jogo

No jogo o problema original é transformado para um problema de transporte comum $T$ mas com o custo variável multiplicado por um fator constante $k > 1$ (e.g. $k = 20$ )

O jogo consiste de dois rounds onde cada jogador pode fazer ofertas de custo variável para um subconjunto de arestas, o payoff de cada jogador é a soma do lucro obtido nos dois rounds como especificado a seguir

fctp_img3

Round 1

Em cada round, cada jogador deve oferecer um valor de custo variável $a_{ij}$ entre $c_{ij}$ e $k \times c_{ij}$ para um subconjunto de arestas. Se esse jogador apostar sozinho em alguma aresta o valor dela é substituído no grafo do problema $T$ e ele “ganha”:

$a_{ij} \times$ fluxo na aresta $(i,j) - F_{ij}$ fctp_img4

Se mais de um jogador apostar na mesma aresta todos pagam uma porção igual do custo fixo $F_{ij}$ mas apenas aquele com a menor oferta ganha o lucro:

$2c_{ij} \times x_{ij} - F_{ij}/2$

$-F_{ij}/2$

fctp_img5

Para determinar o fluxo em cada aresta basta resolver o problema de transporte comum com os custos das ofertas vencedoras nas arestas apostadas e com o custo aumentado nas demais.

fctp_img6

Round 2

No fim da primeira rodada cada jogador terá um conjunto de arestas e seu respectivo lucro por elemento transportado continua, se ele ainda tiver a menor oferta. As pessoas que já apostaram em uma aresta não terão que pagar pelo custo fixo daquela aresta uma segunda vez.

$2c_{ij} \times x_{ij}$

Se um agente apostar em uma aresta que já foi disputada no round anterior por $R$ jogadores mas não por ele, então ele deve pagar $F_{ij}/(R+1)$ como custo fixo para participar, esse valor será distribuído uniformemente entre os agentes que apostaram naquela aresta anteriormente.

$1.1c_{ij} \times x_{ij} - F_{ij}/3$

$F_{ij}/6$

fctp_img7

Por fim, o número total de arestas ofertadas pelos jogadores não deve ultrapassar uma quantia $C$ fixa por round. Se um jogador apostar menos arestas do que $C$ no primeiro round elas não contarão como extra no segundo, se ofertar mais, apenas as primeiras $C$ serão consideradas

fctp_img8

Instâncias:

Instâncias disponíveis no servidor. Descrição do formato (README).

Para a leitura das instâncias, utilize os seguintes critérios:

Na seção ARCS serão usadas apenas as primeiras 4 colunas: 0-source 1-sink 2-varCost 3-fixedCost.
A Seção S define os resources (supply, produtos) dos nós source.
A Seção D define as demandas (demands) para os nós sink.

Dev Kits

Java 1.6+
- Game Client API (javadoc) – API para conexão ao servidor
- Game Bot Example (javadoc) – Exemplo de agente com decisão aleatória
C# .net 4.0+
- Game Client API – API para conexão ao servidor
- Game Bot Example – Exemplo de agente com decisão aleatória

Dinâmica do servidor:

O servidor utiliza um protocolo texto simples para as comunicações e é implementado utilizando um Socket TCP/IP ouvindo a porta “7777”. Os parâmetros são separados utilizando o símbolo ponto e virgula (“;”). A maioria dos comandos não requer parâmetros.

O servidor possui cinco estados:

Ready: 30 segundos para os agentes se prepararem ou conectarem;
Game: jogo em andamento. 5 minutos para todos os jogadores enviarem suas ofertas;
Processing: processamento das ofertas;
Intermission: 30 segundos de intervalo entre os rounds para que os agentes processem o resultado parcial da partida;
Gameover: 30 segundos para que os agentes processem os resultados finais da partida;

Durante os estados Ready, Processing, Intermission e Gameover somente os comandos básicos do servidor estarão disponíveis (scoreboard, estados do jogo, troca de nome, troca de cor e chat). Os demais comandos do agente são desabilitados.

Comandos do Servidor:

Os comandos do servidor estarão disponíveis através de métodos implementados na classe disponibilizada pelo devkit. Segue uma lista de comandos e seus métodos equivalentes:

bid sendPostBid(); – enviar oferta (nome da instancia, vértice x, vértice y, valor)
cancel sendCancelBid(); – cancelar oferta (nome da instancia, vértice x, vértice y)
book sendRequestBookedBids(); – receber a lista de ofertas enviadas
clear sendClearBook(); – apagar a lista de ofertas enviadas
done sendBidsDone(); – finalizar o envio de ofertas

instance sendRequestInstanceList(); – receber a lista de instâncias disponíveis
gamestatus sendRequestGameStatus(); – receber o status do jogo (estado, round, tempo atual)
playerstatus sendRequestUserStatus(); – receber status do usuário (posição, estado do agente, pontos e energia)
scorelist sendRequestScoreboard(); – lista de usuários logados e pontos
quit sendGoodbye(); – desconectar do jogo

name params[1]: name sendName – trocar de nome
say params[1]: msg sendSay – enviar mensagem
color params[3]: r(0-255), g(0-255), b(0-255) sendColor, sendColor(color) – trocar de cor